阅读量:0
本篇将介绍七大常见排序底层逻辑，有助于我们更好地理解不同排序的适用场景和效率上的差别。
🌈个人主页：是店小二呀
🌈C语言笔记专栏：C语言笔记
🌈C++笔记专栏： C++笔记
🌈初阶数据结构笔记专栏： 初阶数据结构笔记
🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
文章目录
一、排序的概念及其运用
1.1 排序的概念
排序是指使用一串记录，按照其中或某些关键字的大小，递增或递减的排序起来的操作(记录是指待排序的具体数据项)。
其中关于排序可以划分为：
外部排序:数据元素全部放在内存中的排序
内部排序:数据元素太多不能同时放在内存中，根据排序过程的要求不能再内外存之间移动数据的排序
1.2 排序的稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
1.3 排序的运用
二、常见的排序算法
2.1 排序实现的接口
#pragma once #include <time.h> #include<stdlib.h> #include <stdio.h> // 排序实现的接口 // 插入排序 void InsertSort(int* a, int n); // 希尔排序 void ShellSort(int* a, int n); // 选择排序 void SelectSort(int* a, int n); // 堆排序 void AdjustDwon(int* a, int n, int root); void HeapSort(int* a, int n); // 冒泡排序 void BubbleSort(int* a, int n) // 快速排序递归实现 // 快速排序hoare版本 int PartSort1(int* a, int left, int right); // 快速排序挖坑法 int PartSort2(int* a, int left, int right); // 快速排序前后指针法 int PartSort3(int* a, int left, int right); void QuickSort(int* a, int left, int right); // 快速排序 非递归实现 void QuickSortNonR(int* a, int left, int right) // 归并排序递归实现 void MergeSort(int* a, int n) // 归并排序非递归实现 void MergeSortNonR(int* a, int n) // 计数排序 void CountSort(int* a, int n) // 测试排序的性能对比 void TestOP() { srand(time(0)); const int N = 100000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); } 三、常见排序算法的实现
关于排序算法，我们都是通过先局部(单趟)再整体去理解整段逻辑。
3.1 插入排序（InsertSort）
基本思路:将待排序的数值，根据序列中大小关系，逐渐插入到一个已经有序序列中，直到所有数据插入完为止，得到新的有序序列。实际中玩扑克牌时，就用了插入排序的思想
void InsertSort(int* a, int n) { //[0,end] end+1//下标的意思 //循环结束的条件 end>0或者找到插入目标 //end从0开始[0,0] for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end >= 0 && tmp < a[end])//当出现大于前面有序的数据停下，>就是倒过来 { a[end + 1] = a[end]; end--; } a[end + 1] = tmp; } }; 过程解析:
我们可以通过扑克牌排序的过程去理解插入排序，比如现在我们手上有一副扑克牌可以分为两个部分：有序部分和所需插入记录。
将这两个部分划分区间得到[0, end] [end + 1 , size_max-1]，代码逻辑是将待插入元素用临时变量tmp记录起来，通过条判断进行数组元素覆盖移动，为待插入元素找到合适的位置。这里需要注意的部分为循环条件是到[0, n - 2]属于有序部分，关于n-1为最后待插入数据。
这里我们还需要考虑下越界访问的情况，由于待插入数据为当前有序区间中最小数值，在匹配过程中不能单纯从大小判断去完成移动，同时需要对end>=0的限制，表示完成了有序区间内数据的比较，结果为最小值需要在最前面插入。
直接插入排序的特点总结:
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度:逆序O(N2)、顺序有序O(N)
- 空间复杂度: O(1)
- 稳定性:稳定
3.2 希尔排序(缩小增量排序)
基本思路:通过预排序使得无序接近有序序列，大体流程:先选定一个整数gap，将待排序序列中所有记录分组，所有距离为gap记录分在同一组，并对每一组记录进行排序，重复上述分组和排序的工作(gap不断缩小)，当gap到达1，此时记录已经接近有序，最后整体进行插入排序，使得记录排好序。
希尔排序分为两部分:
预排序:分布对每组进行插入排序，当gap>1时，目的让他接近有序
直接插入排序:当gap==1时，目的是让他有序
关于gap的取数，有两种选择:
gap=gap/2;
gap=gap/3+1;
3.2.1 预排序
单组排序:
int gap=3;//规定每隔三个空为一组，单独插入排序 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; } } 这里使用下标(N- gap) -1作为分界线，是为了方便大家理解这里内层循环条件为什么这样子写，而实际中分组是通过数据去划分的，需要大家从下标转化到对应数值中。关于第二层循环i<n-gap，这里是根据(n - gap - 1)+ gap = n - 1为最后一个待排序元，比如红色、蓝色、绿最后一个元素超过了当前分界线说明这就是它们分组的最后一个元素，如果继续i+=gap就会发生越界访问。
希尔排序是对于插入排序的优化，对此逻辑上跟插入排序没有太大区别。区别在于希尔排序先用了预排序使得无序序列变得接近有序序列，
多组同时排序(每组并不是单独阶段完全处理)
int gap=3;//规定每隔三个空为一组，单独插入排序 for(int i=j;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; } 
过程解析:
- gap越大，大的值越快调到后面，小的值可以更快的调到前面，越不接近有序
- gap越小，跳得越慢，但是越接近有序。如果gap==1就是直接插入排序
整理过程（上述属于单躺排序)
int gap = n; while (gap > 1) { //gap不断发生变换 gap =gap / 3 + 1; for (int i = 0; i < n - gap; i++)//多组 { int end = i; int tmp = a[end + gap]; while (end >= 0 && tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } a[end + gap] = tmp; } } } 每次预排序都会产生作用，意味着上一组预排序会影响下一组预排序导致影响时间复杂度.
希尔排序的特点总结:
- 希尔排序是对直接插入排序的优化。
- 当gap>1时都是属于预排序，目的是让数组更接近有序。
- 当gap=1时，数据已经接近有序，就是简单插入排序，直接插入排序算法的时间效率越高
- 稳定性:不稳定
3.2.2 关于希尔排序时间复杂度
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都是不固定的
《数据结构(C语言版)》— 严蔚敏
《数据结构-用面相对象方法与C++描述》— 殷人昆 
小总结:
- 插入排序:数据量小或已经部分排序，足够好且实现简单
- 希尔排序：数据量大，希尔排序通常能提供更好的性能
3.4 选择排序（暴力选数）
基本思想:每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
单趟排序:
void SelectSort(int* a, int n) { int begin = 0,end = n - 1; int max = begin, min = begin; //max为0，已经参与比较当中，这里begin+1防止冗余 for (int i = begin + 1; i <= end; i++)//i从下一次开始 { if (a[i] > a[max]) { max = i; } if (a[i] < a[min]) { min = i; } } Swap(&a[begin], &a[min]); Swap(&a[end], &a[max]); } 过程解析:这里属于单躺选择排序，将最小(或最大)放在最左边(或最右边)，同时begin和end表示最左边(或最右边)的位置发生改变。
瑕疵版本:
void SelectSort(int* a, int n) { int begin = 0,end = n - 1; int max = begin, min = begin; while (end > begin) { for (int i = begin + 1; i <= end; i++)//i从下一次开始 { if (a[i] > a[max]) { max = i; } if (a[i] < a[min]) { min = i; } } Swap(&a[begin], &a[min]); Swap(&a[end], &a[max]); begin++; end--; } } 注意:这里需要注意当最大的数据在首元素，那么当第一次Swap把最大的数据，放在其他地方，导致了第二次Swap中max为下标的数据不是最大的数据。
进行两次交换会导致两个位置的数值所对应的索引发生改变，会对下一次交换产生影响，需要提前判断。
完整版本:
void SelectSort(int* a, int n) { int begin = 0,end = n - 1; int max = begin, min = begin; while (end > begin) { for (int i = begin + 1; i <= end; i++)//i从下一次开始 { if (a[i] > a[max]) { max = i; } if (a[i] < a[min]) { min = i; } } Swap(&a[begin], &a[min]); if (begin == max) { max = min; } Swap(&a[end], &a[max]); begin++; end--; } } 选择排序的特点总结:
- 选择排序思想非常好理解，但是效率不是很好。(实际中很少使用)
- 时间复杂度: O(N2)
- 空间复杂度: O(1)
- 稳定性:不稳定
3.4 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
void HeapSort(int *a,int n) { //O(N*logN) //for(int i=0;i<n;i++) //{ // AdjustUp(a,i); // } //O(N) for(int i=(n-1-1)/2;i>=0;--i) { AdjustDown(a,n,i);//从倒数的第一个非叶子，也就是最后一个结点的父亲 } int end=n-1;//下标--同时调整后，最后一个元素不再改动 //O(N*logN) while(end>0)//利用堆删除思想进行排序 { Swap(&a[0],&a[end]); AdjustDown(a,end,0);//要清楚为什么要向下调整 --end; } } 堆排序的特性总结:
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
3.5 冒泡排序
基本思想:比较两个相邻的元素，当不满足某一条件时，发生相邻元素的交换，直到整个序列有序为止。
原始版本:
int main() { int arr[10] = { 0 }; int sz = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < sz; i++) { scanf("%d ", &arr[i]);///输入数据 } int tap = 0; for (int i = 0; i < sz - 1; i++) {//注意只需要sz-1趟就行，最后一次是两个相邻最后的排序 for (int j = 0; j < sz - 1 - i; j++) {//完成一趟，少一个元素参与排序所以-i，-1是下标的原因 if (arr[j] > arr[j + 1])//判断条件 {//进行交换 tap = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tap; } } } for (int i = 0; i < sz; i++) { printf("%d ", arr[i]);//打印数据 } return 0; } 过程解析:序列中两个相邻元素进行比较，当满足条件发生交换操作，导致最小或大元素放到后面位置，不断重复该过程，直到有序。
不足点:目的是直到有序就停下来，但是上面的逻辑是地毯式查找，对此我们需要设置一个标识变量去标识是否有序，如果不需要交换说明有序直接退出。
优化版本:
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> int main() { int arr[10] = { 0 }; int sz = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < sz; i++) { scanf("%d ", &arr[i]);///输入数据 } int tap = 0; for (int i = 0; i < sz - 1; i++) { int flag=1; for (int j = 0; j < sz - 1 - i; j++) { if (arr[j] > arr[j + 1]) { tap = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tap; flag=0; } } if(flag==1) { break; } } for (int i = 0; i < sz; i++) { printf("%d ", arr[i]);//打印数据 } return 0; } 冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度: O (N2)
- 空间复杂度: O(1)
- 稳定性：稳定
小总结:选择排序与冒泡排序
选择和冒泡时间复杂度都是N2这个量级，但是还是有区别的
- 选择排序是：n n-2 n-4
- 冒泡排序是：n n-1 n-2
选择排序的每一轮都包含了选择和交换两个操作。虽然交换是实现排序的具体操作，但选择是排序策略的核心。
3.6 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法(属于前序遍历)
基本思想；任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排序都排序在相应位置上为止。（保证相遇位置为最小值，这点会专门验证）
3.6.1 三数取中
一般对于基准值keyi取最左值，但是序列是接近有序的话，可能会导致递归程度太深会栈溢出而程序奔溃。对于相对默认直接以最左值作为基准值，更倾向于采用随机数取值或者三数取中(不是最大最小值)，这里采用三数取中。
关于keyi还是在最左边取，通过三数取中将得到适合的数与keyi交换。
实现三数取中:
int Getmidi(int* a, int begin, int end) { int midi = (begin + end) + 2; if (a[begin] > a[end]) { if (a[midi] > a[begin]) return begin; else if (a[midi] > a[end]) return midi; else end; } else//a[begin] < a[end] { if (a[midi] > a[end]) return end; else if (a[midi] > a[begin]) return midi; else begin; } }; 在实现过程中，需要以第一个条件为前提，再进行下一条语句判断。
3.6.2 小区间优化
面使用递归的方法很像满二叉树，关于满二叉树倒数几层节点占整颗满二叉树大部分。对此到一定数据时，可以不使用递归的方式，采用插入排序会更好一些(付出的代价更少点)。
3.6.3 hoare版本(坑多)
void PartSort1(int* a, int begin, int end) { if (begin >= end) { return; } int midi = GetMidi(a, begin, end);//将第一个元素大小取为不大也不小的数 Swap(&a[midi], &a[begin]); int keyi = begin;//得到第一个元素的下标 int left = begin; int right = end; while(right > left)//单趟 { // 右边找小 while (left < right && a[right] >= a[keyi]) { --right; } // 左边找大 while (left < right && a[left] <= a[keyi]) { ++left; } Swap(&a[left], &a[right]); } Swap(&a[left], &a[keyi]); keyi = left; //这里导致了begin和end的位置，不是最左或者最右 PartSort1(a, begin,keyi-1); PartSort1(a, keyi+1,end); } 过程解析:涉及到二叉树前序遍历方法，使用分治思想将一个整体不断分为两个部分去看待，当所有若干个小部分有序(只存在一个数，一定有序)，则整体有序。在每一阶段递归过程中，将基准值keyi对应数值使用三数取中进行Swap交换语句进行调整。
关于内层循环添加right > left条件判断为了保证在查找数据的时候，导致可能出现left和right超过，导致交换数据位置不理想，同时要求left和right相遇时，需要停止跟a[kayi]交换，跟a[keyi]相等的数据，放在哪个位置是无所谓的，没有影响。
3.6.4 相遇位置比keyi小推理(重点)
总结:不断缩小范围或者某一方向找不到，直到相遇的情况。但是相遇位置都是小，如果keyi在右边的话，那么只需要左边先走就可以了。
3.6.5 挖坑法
void PartSort2(int* a, int left, int right) { if (left >= right) { return; } int midi = GetMidi(a, left, right);//将首位大小取为不大也不小的数 Swap(&a[midi], &a[left]); int keyi = a[left]; int hole = left; int begin = left; int end = right; while (right > left) { while (a[right] >= keyi && right > left)//找小 { right--; } a[hole] = a[right];//移数值 hole = right; while (a[left] <= keyi && right > left)//找大 { left++; } a[hole] = a[left]; hole = left; } a[hole] = keyi; PartSort1(a, begin, hole - 1); PartSort1(a, hole + 1, end); } 跟hoare思想是相同的，在实现方面更加便捷。
过程解析：先将第一个数据存放在临时变量keyi中，形成一个坑位，同样L找大、R找小，当L(或R)停下来时，交换停下位置和当前坑位的数据，并且当前位置形成新的坑位，不断重复该过程，直到L和R相遇，将keyi赋值给该坑位。
3.6.6 前后指针法
void PartSort3(int* a, int begin, int end) { if (begin >= end) { return; } //编译器优化很厉害，可以不使用 if (end - begin + 1 <= 10)//小区间优化 { InsertSort(a + begin, end - begin + 1); } int midi = GetMidi(a, begin, end);//将第一个元素大小取为不大也不小的数 Swap(&a[midi], &a[begin]); int keyi = begin; int prev = begin; int cur = prev + 1; while (cur <= end)//等于也是要换的 { if (a[cur] < a[keyi] && ++prev != cur) { //避免无效交换 Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); keyi = prev; PartSort1(a, begin, keyi - 1); PartSort1(a, keyi + 1, end); return 0; } 过程解析:这里使用同相双指针法，具体可以通过动图推导规律。
cur遇到比keyi大的值，++curcur遇到比keyi小的值，++prev，交换prev和cur位置的值，++cur
小总结:
对于不同的方法，单趟的结果都是不一样的。当有多选题时，可以使用不同方式选出答案。对此三个方法，如果需要使用快速排序，推荐使用后面两个方法更快（将两个调用自身函数注释掉，就是单趟排序）。
3.4 归并排序
基本思想:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序序列即先使每个子序列有序，再使子序列间有序。若加你个两个有序表合并成一个有序表，称为二路归并。
实现过程；
void MergeSort(int *a,int n) { int *tmp=(int *)malloc(sizeof(int)*n); if(tmp==NULL) { perror("malloc fail!"); return 1; } _MergeSort(a,0,n-1,tmp); free(tmp) tmp=NULL; } void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) { return; } int mid = (begin + end) / 2; //[begin,mid][mid+1,end] _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp);//后序递归 //左边有序 右边有效 合在一起-->合并有序数组问题 int begin1 = begin; int begin2 = 1+ mid; int end1 = mid; int 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));//可能是右边归并 } 过程解析:这里同快速排序使用了分治思想，但是不同于快速排序采用前序遍历根 左子树 右子树，而是采用后序遍历左子树 右子树 根。归并排序主要是通过已有序的子序列合并，得到完全有序的序列。那么将已有序的左右子树得到完全有序的根序列，完成这项操作需要借助一块空间完成合并，再使用内存函数复制或转移到原本序列中。
注意:将合并好序列拷贝到源序列中，如果为右边归并，开头元素下标需要匹配到相对应的位置，只要a+begin和tmp+begin就可以解决这个问题
归并排序的特点总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的使解决在磁盘中的外排序问题。
- 时间复杂度: O(N*logN)
- 空间复杂度: O(N)
- 稳定性:稳定
- 没有进行交换，更加适合外排序
3.5 计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
void CountSort(int* a, int n) { int min = a[0], max = a[0]; for (int i = 1; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } int range = max - min + 1; int* count = (int*)calloc(range, sizeof(int)); if (count == NULL) { printf("calloc fail\n"); return; } // 统计次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } // 排序 int i = 0; for (int j = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min;//加回去 } } } 过程解析:将待排序中数据和新数组中下标对应，并且在记录出现的次数。当数据很大时，很难去把握，因此使用相对映射比较好count[a[i]-min]++;
局限性:
- 不适合分散的数据，更适合集中数据
- 不适合浮点数，字符串、结构体数据排序、只适合整数
计数排序的特性总结：
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
四、排序算法复杂度及稳定性分析
以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二初阶数据结构笔记，希望对你在学习初阶数据结构中有所帮助！
