【数据结构与算法】常见的排序算法

文章目录

  • 排序的概念
  • 冒泡排序（Bubble Sort）
  • 插入排序（Insert Sort）
  • 选择排序（Select Sort）
  • 希尔排序（Shell Sort）
    • 写法一
    • 写法二
  • 快速排序（Quick Sort）
    • hoare版本（左右指针法）
    • 挖坑法
      • 递归法
      • 非递归法
    • 前后指针法
  • 堆排序
  • 归并排序

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

冒泡排序（Bubble Sort）

优点：简单，易实现，稳定且不需要额外空间
缺点：效率低
升序思路：
两两比较，相邻的两个元素比较，第一个元素比第二个大就交换。此时最大的元素在最右边，再循环这个动作（最后一个元素不进入循环），直到循环截止，该数组为有序。

动图演示如下：
在这里插入图片描述
核心代码如下：

Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){for (int i = 0; i < n - j-1; i++){if (a[i + 1] < a[i]){Swap(&a[i + 1], &a[i]);}}}
}

冒泡排序的特性总结：

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：最坏情况是O(N^2)， 最好情况是O(N)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

插入排序（Insert Sort）

优点：效率略高于冒泡和选择排序，稳定
缺点：效率不高

升序思路：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
步骤：
1.从第一个元素开始（默认第一个元素为有序）
2.取下一个元素，从已有的有序元素中从左往右扫描
3.如果该元素大于新插进来的元素，则将该元素移动到下一个位置
4.重复步骤3，直到有序元素中找到小于或等于新元素的元素
5.将新元素插入到该元素后面
6.若有序元素全都大于新元素，则将新元素插入到第一位，即下标为0的位置

动图演示如下：
在这里插入图片描述
核心代码：

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; i++){//记录最后一个元素下标int end = i;//待插入的元素int tmp = a[end + 1];//单趟排序while (end >= 0){//若该元素比插进来的数大就后移一位if (tmp < a[end]){a[end + 1] = a[end];--end;}//比该元素小就退出循环else{break;}}//把tmp元素插入到end后面一个（即插入到小的数后面一个）a[end + 1] = tmp;}
}

直接插入排序的特性总结：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定

选择排序（Select Sort）

优点：表现最稳定，时间复杂度永远O(N^2)，不需要额外空间
缺点：稳定上讲，不稳定，效率低

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

动图演示如下：
在这里插入图片描述
但我觉得这样稍微有一丢丢慢，可以优化一下，我们可以一次选两个值，一个最小值，一个最大值，分别将其放到序列开头和末尾处。

步骤：
1.首先在序列（未排序）中找到最小的值，放到序列起始位置
2.再找序列中最大的值，放到序列末尾处
3.重复以上动作，直到所有元素有序（即begin和end相遇停止）

核心代码:

void SelectSort(int* a, int n)
{//记录第一个和最后一个下标int begin = 0;int end = n - 1;while (begin < end){//保存最大值，最小值下标int mini = begin;int maxi = begin;//找出最大值和最小值的下标for (int i = begin; i <= end; i++){//找到最小值，将mini最小值下标更新为i位置if (a[i] < a[mini]){mini = i;}//找到最大值，将maxi最大值下标更新为i位置if (a[i] > a[maxi]){maxi = i;}}//此时最小值为序列开头处Swap(&a[mini], &a[begin]);//考虑到万一最大值在begin位置被mini换走，所以增加判断if (begin == maxi){maxi = mini;}//此时最大值在序列末尾处Swap(&a[maxi], &a[end]);//begin往前后，不断更新++begin;//end往前走，不断更新--end;}
}

直接选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：最好情况和最坏情况都是O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

希尔排序（Shell Sort）

优点：效率高于三种简单排序，不需要额外空间
缺点：不稳定

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

步骤：
1.选择一个增量序列，通常为初始增量为数组长度的一半，然后逐步减小增量直至为1。
2.根据选定的增量对数组进行分组，每个分组包含间隔为增量的元素。
3.对每个分组进行插入排序，即将每个元素插入到正确的位置上，使得每个分组内的元素有序。
4.逐步减小增量，重复上述步骤，直到增量为1时完成最后一次插入排序。
5.最终得到一个有序数组。

动图演示如下：
在这里插入图片描述

写法一

思路图：
gap > 1 时是预排序，目的是让它接近有序
gap == 1 时是直接插入排序，目的是为了让它有序
在这里插入图片描述
核心代码：

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//循环躺数gap = gap / 3 + 1;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}a[end + gap] = tmp;}}}}
}

写法二

多组并排
核心代码：

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

希尔排序的特性总结：

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

时间复杂度：
在这里插入图片描述
空间复杂度：O(1)

快速排序（Quick Sort）

hoare版本（左右指针法）

步骤：
1.选出一个key，一般选最左边或者最右边的。（男左女右，这里我就选最左边的了）。
2.定义一个begin和一个end，begin从左往右走，end从右往左走。
注：若你选的key在左边，那右边的end就要先走，反之右边，则左边的begin需要先
3.假设end先走，往左走，在行走过程中，若end遇到小于key的值就停下来，这时候begin走，往右走，当begin遇到大于key的值也停下来，然后将begin和end内容交换，然后再end走…反复这样走直到begin和end相遇，将他们相遇的下标内容与key进行交换。
4.这时候key的左边都是小于key的，而key的右边都是大于key的。
5.以key为划分点，将它的左序列和右序列分别进行上面这种排序，直到左右序列都只剩一个数值，或者不存在数值，就停止。
在这里插入图片描述
核心代码：

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int left = begin;int right = end;int keyi = begin;while (left < right){//选的key为左边，所以右边先走，右边找比key小的，&&前面的判断是为了防止left和right越界，或者说互相错过while (left < right && a[right] >= a[keyi]){--right;}//右边走完左边走，左边找大，找比key大的值，和上面的循环一样while (left < right && a[left] <= a[keyi]){++left;}//交换，目的是要把比key大的值都放key的左边，比key小的值都放key的右边Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;//区间//[begin,keyi-1] keyi [keyi+1,end]//递归QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

挖坑法

递归法

步骤：
1.选出一个数据，一般选最左边或者最右边的，思想与hoare版本类似，选出的数存在变量key中，此时，原来的位置就会形成一个空位坑位，所以叫做挖坑法。
2. 依旧是定义两个变量，一个往左走，一个往右走，和上面方法一样，若你的坑位在左边，右边就先走，否则左边先走。
…思路与hoare一样的
在这里插入图片描述

int PartSort2(int* a, int begin, int end)
{int keyi = a[begin];int hole = begin;while (begin < end){//右边找小，填到左边的坑while (begin < end && a[end] >= keyi){--end;}a[hole] = a[end];hole = end;//左边找到，填到右边的坑while (begin < end && a[begin] <= keyi){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = keyi;return keyi;
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

非递归法

核心代码：

void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);STPush(&s, end);STPush(&s, begin);while (!STEmpty(&s)){int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);int keyi = PartSort3(a, left, right);// [left, keyi-1] keyi [keyi+1, right]if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}}STDestroy(&s);
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

前后指针法

步骤：
还是一样的
1.选出一个key，选最左边的或者最右边的
2.首先定义prev指针在序列起始位置，然后定义指针cur在prev的下一个，即prev+1
3.cur遇到比key大的值，++cur
4.cur遇到比key小的值，++prev，交换prev和cur位置的值，再++cur
在这里插入图片描述
核心代码：

int PartSort3(int* a, int begin, int end)
{int prev = begin;int cur = prev + 1;int keyi = begin;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[keyi], &a[prev]);keyi = prev;return prev;
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定

堆排序

这个排序我们之前讲过的，这里我就不再复习啦~
需要的老铁请点这里----->堆、堆排序

堆排序的特性总结：

  1. 堆排序使用堆来选数，效率就高了很多。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

步骤：
1.分解：将待排序的序列分解成若干个子序列，每个子序列包含1个元素。
2.合并：将相邻的子序列两两合并，形成新的有序子序列，直到无法再合并。
3.重复合并步骤直到得到最终的排序结果。

在这里插入图片描述
动态演示如下：

在这里插入图片描述
核心代码：

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);//[begin,mid] [mid+1,end]归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin+1));
}
//归并排序
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/324125.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

数据挖掘（二）数据预处理

数据挖掘（二）数据预处理

前言 基于国防科技大学 丁兆云老师的《数据挖掘》 数据挖掘 数据挖掘&#xff08;一&#xff09;数据类型与统计 2、数据预处理 2.1数据清理 缺失值处理&#xff1a; from sklearn.impute import SimpleImputer# 创建一个SimpleImputer对象&#xff0c;指定缺失值的处理策略…
阅读更多...
网络编程——Socket——模拟用户登录

网络编程——Socket——模拟用户登录

功能一&#xff1a;模拟用户登录 功能二&#xff1a;实现客户发送登录用户信息&#xff0c;服务器端显示登录信息并响应给客户端登录成功 这里设置的用户登录信息为&#xff1a;admin&#xff0c;123456 实现&#xff1a; 1.首先&#xff0c;服务端创建并启动服务器&#x…
阅读更多...
Android 14 变更及适配攻略

Android 14 变更及适配攻略

准备工作 首先将我们项目中的 targetSdkVersion和compileSdkVersion 升至 34。 影响Android 14上所有应用 1.最低可安装的目标 API 级别 从 Android 14 开始&#xff0c;targetSdkVersion 低于 23 的应用无法安装。要求应用满足这些最低目标 API 级别要求有助于提高用户的安…
阅读更多...
单调栈：（C++）

单调栈：（C++）

在题目的要求中&#xff0c;存在先进后出&#xff08;即在前面的数据需要遍历到后面的某一数据时才能确定计算值&#xff09;单调栈在一部分解题场景中避免了暴力解法的高时间复杂度问题&#xff0c;但是在做题过程中视情况而定&#xff0c;有些题目的最优解不一定使用单调栈&a…
阅读更多...
AI图书推荐：ChatGPT全面指南—用AI帮你更健康、更富有、更智慧

AI图书推荐：ChatGPT全面指南—用AI帮你更健康、更富有、更智慧

你是否在努力改善你的健康&#xff1f; 你是否长期遭受财务困难&#xff1f; 你想丰富你的思想、身体和灵魂吗&#xff1f; 如果是这样&#xff0c;那么这本书就是为你准备的。 《ChatGPT全面指南—用AI帮你更健康、更富有、更智慧》&#xff08;CHATGPT Chronicles AQuick…
阅读更多...
Java入门基础学习笔记4——开发Helloworld入门程序

Java入门基础学习笔记4——开发Helloworld入门程序

Java程序开发的三个步骤&#xff1a; 1&#xff09;编写代码 2&#xff09;编译代码 3&#xff09;运行代码 注意事项&#xff1a; 第一个java程序建议使用记事本来编写。 建议代码文件名全英文、首字母大写、满足驼峰模式&#xff0c;源代码文件的后缀必须是.java 注意&a…
阅读更多...
netty配置SSL、netty配置https（开发）

netty配置SSL、netty配置https（开发）

netty配置SSL、netty配置https&#xff08;开发&#xff09; 我们在开发下使用ssl&#xff0c;所用的证书将不被客户端信任。 转自&#xff1a;https://lingkang.top/archives/netty-pei-zhi-ssl 方案一 快速。使用netty提供的临时签发证书 private static SslContext sslC…
阅读更多...
小程序（三）

小程序（三）

十三、自定义组件 &#xff08;二&#xff09;数据方法声明位置 在js文件中 A、数据声明位置&#xff1a;data中 B、方法声明位置methods中&#xff0c;这点和普通页面不同&#xff01; Component({/*** 组件的属性列表*/properties: {},/*** 组件的初始数据*/data: {isCh…
阅读更多...
TCP 连接，一端断电和进程崩溃有什么区别？

TCP 连接，一端断电和进程崩溃有什么区别？

TCP 连接&#xff0c;一端断电和进程崩溃有什么区别&#xff1f; 前言主机崩溃进程崩溃有数据传输的场景客户端主机宕机&#xff0c;又迅速重启客户端主机宕机&#xff0c;一直没有重启 总结 前言 有的小伙伴在面试腾讯的时候&#xff0c;遇到了这么个问题&#xff1a; 这个属…
阅读更多...
cocos中的meta文件有什么用？如何生成？

cocos中的meta文件有什么用？如何生成？

cocos中的.meta文件有什么用&#xff1f;如何生成&#xff1f; 1. .meta文件有什么用&#xff1f; Cocos Creator 会为 assets 目录下的每一个文件和目录生成一个同名的 meta 文件 示例 {"ver": "4.0.23", // 版本"importer": "typescr…
阅读更多...
基于ESP32和ESP8266的物联网开发过程（二）

基于ESP32和ESP8266的物联网开发过程（二）

在做这个项目前&#xff0c;也做了一些调研。项目的初衷是想要用于智能家居。我比较了小米IoT、阿里云、ESPHOME、巴沙云、点灯科技和ONENET等几个平台。最终选择了Onenet&#xff0c;部分原因是之前用过它的多协议版本&#xff0c;但现在这个版本已经下线了。 小米IoT的公测名…
阅读更多...
Linux - make与makefile

Linux - make与makefile

文章目录 什么是make和makefile如何使用依赖关系 和 依赖方法伪目标 写个程序-进度条换行和回车的区别 什么是make和makefile make是一个命令 makefile是一个文件 这就是make和makefile的本质 make和 ll , pwd ,su 一样都是命令 makefile和 test &#xff0c; test.c 一样都是…
阅读更多...
GPT+Python近红外光谱数据分析

GPT+Python近红外光谱数据分析

原文链接&#xff1a;GPTPython近红外光谱数据分析https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247603913&idx1&sn6eb8fd6f1abcdd8160815997a13eb03d&chksmfa82172ecdf59e389a860547a238bb86c7f38ae3baa14e97c7490a52ef2a2c206f88d503a5eb&token…
阅读更多...
【WPF学习笔记（一）】WPF应用程序的组成及Window类介绍

【WPF学习笔记（一）】WPF应用程序的组成及Window类介绍

WPF应用程序的组成及Window类介绍 WPF应用程序的组成及Window类介绍前言正文1、WPF介绍1.1 什么是WPF1.2 WPF的特点1.3 WPF的控件分类 2、XAML介绍2.1 XAML的定义2.2 XAML的特点2.3 XAML的命名空间 3、WPF应用程序组成3.1 App.config3.2 App.xaml3.3 App.xaml.cs3.4 MainWindow…
阅读更多...
分布式存储CephFS最佳实践

分布式存储CephFS最佳实践

文章来源于知乎文章&#xff1a; 分布式存储CephFS最佳实践 背景 近日&#xff0c;一朋友说他们企业内部想落地CephFS&#xff0c;让我帮忙写一份能落地的CephFS最佳实践。然后就顺便把文章整理到了这里。因能力水平以及认知有限&#xff0c;如有错漏烦请指正。 简介 CephF…
阅读更多...
IP 地理定位神话与事实

IP 地理定位神话与事实

ip地理定位是一项技术&#xff0c;用于通过访问设备的ip地址来获取地理位置信息&#xff0c;例如国家、城市、经纬度等。该技术广泛应用于网站内容自定义、广告定位、网络安全和用户分析等领域。它通过与包含ip地址和地理位置映射的大型数据库进行查询来工作&#xff0c;但在准…
阅读更多...
聊聊测试团队管理

聊聊测试团队管理

管理测试团队是一个复杂但至关重要的任务&#xff0c;它不仅关乎于保证软件产品的质量&#xff0c;还涉及到团队建设、流程优化、技能提升等多个方面。以下是一些关键策略&#xff0c;可以帮助您有效地管理测试团队&#xff0c;比如“持续培训和技术支持&#xff0c;明确目标&a…
阅读更多...
99、技巧-下一个排列

99、技巧-下一个排列

这个问题要求生成一个数组的下一个排列。所谓“下一个排列”指的是&#xff0c;在所有数字相同但顺序不同的排列中&#xff0c;找出数字序列中刚好比当前序列大的下一个序列。如果当前序列已经是这些排列中的最大值&#xff0c;则下一个排列应该是最小的排列。 思路解释 要解…
阅读更多...
QML 本地存储（Setting,sqlite）

QML 本地存储（Setting,sqlite）

Qt hello - 专注于Qt的技术分享平台 QML 原生的储存方有两种&#xff1a; 1&#xff0c;Settings 跟QWidget 中的QSettings 一样&#xff0c;可以简单的存储一些配置。 2&#xff0c;Sqlite sqlite数据库。可以存储一些复杂的数据。 一&#xff0c;Settings 我们以一个按钮的位…
阅读更多...
【机器学习300问】81、什么是动量梯度下降算法？

【机器学习300问】81、什么是动量梯度下降算法？

动量梯度下降算法&#xff08;Momentum&#xff09;是利用指数加权移动平均的思想来实现梯度下降的算法。让我们先来回顾一下基础的梯度下降方法以及看看它有哪些不足之处。接着引出动量梯度下降算法&#xff0c;在理解了它的原理后看看它是如何规避之前方法的不足的。 如果不知…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023