| 【数据结构】八大经典排序（两万字大总结） | 您所在的位置：网站首页 › 数据结构中排序的定义怎么理解 › 【数据结构】八大经典排序（两万字大总结） |
【数据结构】八大经典排序（两万字大总结）
|
文章目录排序的基础知识1. 排序的概念2. 常见排序分类3. 排序的运用常见排序算法的实现1. 直接插入排序1.1 排序思想1.2 代码实现1.3 复杂度及稳定性1.4 特性总结2. 希尔排序2.1 排序思想2.2 代码实现2.3 复杂度及稳定性2.4 特性总结3. 直接选择排序3.1 排序思想3.2 代码实现3.3 复杂度及稳定性3.4 特性总结4. 堆排序4.1 排序思想4.2 排序实现4.3 复杂度与稳定性4.4 特性总结5. 冒泡排序5.1 排序思想5.2 代码实现5.3 复杂度及稳定性5.4 特性总结6. 快速排序 (重点)6.1 排序思想6.2 快排递归版本6.3 hoare 法6.4 挖坑法6.5 前后指针法6.6 快排递归版本完整代码6.7 快排非递归版本6.8 复杂度及稳定性6.9 特性总结7. 归并排序 (重点)7.1 排序思想7.2 归并排序递归版本7.3 归并排序非递归版本7.4 复杂度及稳定性7.5 排序特性8. 计数排序8.1 排序思想8.2 代码实现8.3 计数排序的缺陷8.4 特性总结9. 排序总结排序的基础知识1. 排序的概念 什么是排序：所谓排序，就是使一串记录按照其中的某个或某些关键字的大小，按递增或递减方式排列起来的操作。 排序的稳定性：假定在待排序的记录序列中存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为该排序算法是不稳定的。 为什么要关注排序的稳定性： 在知道排序稳定性的概念之后，很多同学可能都会产生一个疑问：我们为什么要注重排序算法的稳定性呢？这里我以高考成绩排名的例子来阐述。 我们知道，由于高考人数众多，出现几个人或者几十个人成绩相同的情况是完全有可能的，那么对成绩相同的同学我们如何进行排名呢？答案是按科目成绩科目进行排名。 假设我们规定，当高考成绩相同时，语文成绩高者排前面；那么我们在对高考成绩进行排名时，就可以先按所有考生的语文成绩进行一次排序，将语文成绩高的排在前面，然后再按总成绩进行一次排序，得出最终排名，那么这里就对排序的稳定性提出要求了，如果我们使用的排序算法不稳定，那么成绩总相同的两个人的排名就可能出现错误。当然，这里只是拿高考排名举例，具体高考成绩怎么排名我们不用关心。 所以，在特殊场景下，对排序的稳定性是有要求的；另外，排序的稳定性在校招中也被经常考查。 内部排序：数据元素全部放在内存中的排序；我们的插入排序、选择排序以及交换排序都是内部排序。 外部排序：由于待排序的记录太多，不能同时放入内存中，而是需要将待排序的记录存储在外存中，待排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换；这种排序方法就称为外部排序；我们的归并排序既可以用于内部排序，也可以用于外部排序。 比较排序：通过比较两个元素的大小来确定元素在内存中的次序，我们常见的入选择排序、插入排序、比较排序与归并排序都属于比较排序。 非比较排序：通过确定每个元素之前，应该有多少个元素来排序，常见的非比较排序有基数排序、计数排序与桶排序。 2. 常见排序分类生活中常见的排序算法可以分为以下五类：  image-202209112136379663. 排序的运用排序在我们的日常生活中是非常常见的，比如我们在京东/淘宝上购物商品时，可以选择按销量排序、按价格排序、按评论排序，又比如世界500强企业，中国前50所高校等等，这些地方都需要用到排序。  image-20220911214144355 image-20220911214246447常见排序算法的实现注：本文章所有的排序算法都以升序为例。 1. 直接插入排序1.1 排序思想直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。 实际中我们玩扑克牌时，就运用了插入排序的思想：  image-20220911214955717动图演示 如图：当我们插入第 i (i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。  1.2 代码实现代码语言：javascript复制// 直接插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1]; //记录最后一个元素
//当目标元素为最小元素，end为-1时退出循环
while (end >= 0)
{
//如果大于tmp中的数据，就往后挪并--end
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
//如果小于等于tmp中的数据，就跳出循环准备插入
else
{
break;
}
}
//将数据插入到end的后一个位置
a[end + 1] = tmp;
}
}注意事项 1、对于单趟排序来说，假设该趟数组共有 m 个数据，我们认为前 m-1 个数据是有序的，我们只需要将最后一个数据插入并且仍然保存数组有序即可； 2、比较过程中需要挪动数据，这里我们从数组倒数第二个元素开始比较，如果该元素大于目标元素就把数组往后移动一位，最后当 a[end] 1时代表预排序，gap==1时代表直接插入排序 // while (gap > 1) // { // gap = gap / 3 + 1; // //对所有组数据进行排序 // for (int i = 0; i < gap; i++) // { // //对一组数据进行插入排序 // for (int j = i; j < n - gap; j += gap) // { // int end = j; // int tmp = a[end + gap]; // while (end >= 0) // { // if (a[end] > tmp) // { // a[end + gap] = a[end]; // end -= gap; // } // else // { // break; // } // } // a[end + gap] = tmp; // } // } // } //} // 希尔排序 -- 版本2（两层循环） void ShellSort(int* a, int n) { int gap = n; //gap>1时代表预排序，gap==1时代表直接插入排序 while (gap > 1) { gap = gap / 3 + 1; //i++：i每次加1，而不是加gap，表示对所有组进行并排(所有组同时进行插入排序) for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } 注意事项 1、关于 gap 的取值：我们知道，gap 越大，大的数据就能越快的到后面去，小的数据能越快的到前面来，但数据的有序性较低；gap 越小，大的数据到后面和小的数据到前面和后面的速度较慢，但是数据的有序性就越高；所以综合二者考虑，为了提高效率，大佬Knuth提出了 gap 随数据个数和排序次数变化的思路，即 gap 最开始对于元素个数 n，之后每预排一组数据，gap 就减小2倍或者3倍 (这里采取的是每次减小3倍)； 2、对于版本1来说，我们每次只排序一组数据，当这一组排完之后再排序下一组数据，所以我们需要用两层 for 循环嵌套来保证每一组数据都被排序；但对于版本2来说，我们每次让 i 加1，即让所有组数据同时进行排序 (第一组插入一个元素后让第二组插入一个元素，然后第三组，… …，当所有组都插入一个元素后再插入第一组的下一个元素，… …)，所以只需要使用一个 for 循环。 3、当 gap 等于1时，相当于对整体进行直接插入排序 ； 4、无论 gap = n 为奇数还是偶数，gap 经过不断除3加1后，进行最后一趟排序时 gap 一定等于1 (大家可以带几个值进去试一下)，这也是 gap 每次除3后都加1的目的，此趟排序使得数组全部元素有序。 2.3 复杂度及稳定性时间复杂度 在希尔排序中，因为 gap 的取值方法不唯一，导致其时间复杂度很难去计算，因此在一些优秀的数据结构书籍中给出的希尔排序的时间复杂度也都不固定：  image-20220911233922806 image-20220911233957180因为我们的 gap 是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照蓝色框的时间复杂度来算，可以大概记忆为：O(N1.3)； 空间复杂度 希尔排序没有额外的内存消耗，空间复杂度为：O(1)； 稳定性 和直接插入排序不同，希尔排序是不稳定的：因为在预排序过程中，数值相同的元素可能会被分配到不同组中，不同组进行插入排序之后，数值相同的元素的相对位置就可能会发生改变，所以不稳定。 2.4 特性总结希尔排序是对直接插入排序的优化；当 gap > 1时都是预排序，目的是让数组更接近于有序；当gap == 1时，数组已经接近有序的了，这使得最后一次的插入排序效率很高，从而达到整体效率优化的效果；时间复杂度：O(N1.3) (不准确)；空间复杂度：O(1)；稳定性：不稳定3. 直接选择排序3.1 排序思想 直接选择排序即每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序数据元素排完；这里我们对其做一些简单的优化 – 每次选两个数，选出最小的放在最前面，选出最大的放在最后面。 动图演示 (未优化) 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，然后在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。  3.2 代码实现代码语言：javascript复制// 交换两个数据
void Swap(int* e1, int* e2)
{
int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
// 直接选择排序
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
//一次选两个数，把最小的放前面，最大的放后面
int mini = begin, maxi = begin;
for (int i = begin + 1; i a[maxi])
maxi = i;
}
Swap(&a[begin], &a[mini]);
//当最大的数在最前面时，我们需要修正maxi，放在其被覆盖
if (maxi == begin)
maxi = mini;
Swap(&a[end], &a[maxi]);
//迭代
begin++;
end--;
}
}注意事项 优化后的直接选择排序存在一个隐藏的 bug：当最大的数位于数组最前面 (maxi == begin) 时，a[begin] 和 a[mini] 交换后会使得最大数 a[begin] 被移动到 mini 下标处，此时我们需要修正 maxi，使得程序能够选出最大的数。 3.3 复杂度及稳定性时间复杂度 不同于插入排序，对于直接选择排序来说，数据有序或者无序并不会改变排序的效率，因为它始终是通过遍历比较数组元素来求得最大值或者最小值，时间复杂度：O(N^2)； 空间复杂度 直接选择排序没有额外的内存消耗，空间复杂度为：O(1)； 稳定性 直接选择排序给我们的直观感受是稳定的，因为它每次选择元素时，只有当遇到比自己小的元素时才更新 mini，与自己相等的元素并不会更新 mini，所以相等元素间的相对位置不会发生改变，但其实它是不稳定的； 我们以 8 9 8 5 5 为例，我们第一次排序发现 5 为最小元素，所以 mini = 3，然后交换 a[0] 与 a[mini]，第一次排序之后的数组为：5 9 8 8 5，大家仔细对比第一次排序前和排序后的数组，发现了什么问题？没错，8 和 8 之间的相对位置发生了改变，所以说直接选择排序其实是不稳定的。（注：这里为了方便理解，我们以未优化的直接选择排序为例） 3.4 特性总结直接选择排序思想非常好理解，但是效率不好，实际中很少使用；时间复杂度：O(N^2)空间复杂度：O(1)稳定性：不稳定4. 堆排序4.1 排序思想 堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种；它通过堆来进行选择数据；需要注意的是排升序要建大堆，排降序建小堆。 4.2 排序实现关于堆排序我前面单独写了文章来介绍，具体细节请移步至：【数据结构】堆的应用 – 堆排序和TopK问题 4.3 复杂度与稳定性时间复杂度 堆排序建堆的时间复杂度为 O(N)，选数的时间复杂度为 O(N*logN)，所以堆排序的时间复杂度为：O(N*logN)； 空间复杂度 堆排序直接在原数组上进行建堆和选数操作，没有额外的内存消耗，空间复杂度为：O(1)； 稳定性 由于堆排序中相同的数据做父节点还是孩子节点，做左孩子还是做右孩子，这些都没有规定，所以堆排序也是不稳定的。 4.4 特性总结相比于直接选择排序，堆排序使用堆来选数，效率提高了很多；时间复杂度：O(N*logN)；空间复杂度：O(1)；稳定性：不稳定；5. 冒泡排序5.1 排序思想 交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。 冒泡排序的基本思想：冒泡排序是交换排序中一种简单的排序方法，它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆顺（a[j]>a[j+1]），则将其交换，最终达到有序的目的。 由于冒泡排序本身并不知道待排序的数据是否是有序的，所以即便目标数据已经有序，它还是会继续进行比较，知道循环达到循环截止条件；所以为了提高效率，我们可以对冒泡排序进行简单的优化 – 增加一个有序判断，使得当目标数据有序时冒泡排序能够跳出循环，停止排序。 动图演示  5.2 代码实现代码语言：javascript复制// 冒泡排序
void BubbleSort(int* a, int n)
{
int i = 0;
int j = 0;
for (i = 0; i < n - 1; i++)
{
int exchange = 0;
for (j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
exchange = 1;
}
}
if (exchange == 0) //如果数组已经有序，则直接跳出循环，不再排序
break;
}
}5.3 复杂度及稳定性时间复杂度 最坏情况：数据是逆序的，第一趟排序要交换n-1个数据，第二趟要交换n-2个数据… …，最后一趟要交换1个数据，所以交换的次数合计也是一个等差数列，时间复杂度为 O(N^2)； 最好情况：对于未优化的冒泡排序来说，数据是否有序并不会影响排序的效率，时间复杂度都为 O(N^2)；但对于优化后的冒泡排序来说，当数据是有序的情况下，其时间复杂度可以达到 O(N)； 所以时间复杂度：O(N^2)； 空间复杂度 冒泡排序没有额外的内存消耗，空间复杂度为：O(1)； 稳定性 冒泡排序每趟排序过程中，只有当前一个元素大于后一个元素时才会发生交换，当二者相等时并不会发生交换，所以相等元素间的相对位置不会发生改变，稳定。 5.4 特性总结冒泡排序是一种非常容易简单且理解的排序；时间复杂度：O(N^2)；空间复杂度：O(1)；稳定性：稳定；6. 快速排序 (重点)6.1 排序思想 快速排序是 Hoare 于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 6.2 快排递归版本在了解快排的思想之后，我们会发现快速排序的排序过程是这样的：先选定一个 key 做基准值，经过单趟排序后 key 左边位置的元素都小于 key，右边位置的元素都大于 key，这就使得 key 的位置被最终确定，即我们一趟排序可以确定一个元素的位置；现在我们只需要对 key 的左区间和右区间再进行单趟排序即可；key 的左区间经过单趟排序之后又会确定一个元素的位置，然后再对该元素的左右区间进行单趟排序，直到 key 的左右区间只有一个元素 (一个元素本身就有序，不需要再进行排序) 或者不存在左右区间时说明排序完成。 经过上面的分析我们发现，快排的排序过程和二叉树的前序遍历十分相似，我们每趟排序可以确定一个元素的位置，然后我们就只需要排序该位置的左右区间即可，左右区间又可以被划分为左右区间，即不断被划分为子问题，这就是递归的思想。 代码语言：javascript复制// 快速排序递归实现 void QuickSort(int* a, int left, int right) { //如果左右区间相等或者右区间小于左区间直接返回 if (right a[right] ? a[mid] : a[right]; int min = max1 < max2 ? max1 : max2; //返回居中值对应的下标 if (min == a[left]) return left; else if (min == a[mid]) return mid; else return right; }优化后的单趟排序代码 代码语言：javascript复制// 快速排序hoare版本 int PartSort1(int* a, int left, int right) { //三值取中做key int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int keyi = left; while (left < right) { //右先走，找小 //left=：避免死循环 while (left < right && a[right] >= a[keyi]) { right--; } //左后走，找大 while (left < right && a[left] a[right] ? a[mid] : a[right]; int min = max1 < max2 ? max1 : max2; //返回居中值对应的下标 if (min == a[left]) return left; else if (min == a[mid]) return mid; else return right; } // 快速排序hoare版本 int PartSort1(int* a, int left, int right) { //三值取中做key int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int keyi = left; while (left < right) { //右先走，找小 //left=：避免死循环 while (left < right && a[right] >= a[keyi]) { right--; } //左后走，找大 while (left < right && a[left] = right) return; int mid = left + (right - left) / 2; //递归左区间有序 _MergeSort(a, left, mid, tmp); //递归右区间有序 _MergeSort(a, mid + 1, right, tmp); //当左右区间都有序时开始归并 -- 取小的尾插 int left1 = left, right1 = mid; //左区间 int left2 = mid + 1, right2 = right; //右区间 //在tmp数组中的相应位置尾插 int i = left; while (left1 |
【本文地址】