1.排序的概念

1.1排序的概念

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

2.常见排序算法的实现

2.1 插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

2.1.1直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

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;}}a[end + 1] = tmp;//将待排序数据放在合适位置}
}

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

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

2.1.2希尔排序

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

• 希尔排序是对直接插入排序的优化。
  当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，在使用直接插入排序，这样就会很快。这样整体而言，可以达到优化的效果。

• 在初始时，gap通常选择 n/2 或 n/3+1(n为数据的个数)

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//gap = gap / 3 + 1;gap = gap / 2;//gap趟for (int j = 0; j < gap; j++){//一趟的for (int i = j; i < n - gap; i+=gap)//每次跳跃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;}}}
}

上面的代码可以进行优化，不需要单独排每一趟，直接可将gap趟一次排。

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//gap = gap / 3 + 1;gap = gap / 2;//gap趟一起排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. 时间复杂度：O(N^1.3)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

2.2选择排序

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

2.2.1直接选择排序:

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void SelectSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int m = i;//记录当前数的下标for (int j = i + 1; j < n; j++){if (a[j] < a[m])//将当前数与其后的数对比{m = j;//记录较小值的下标}}//较小值不是当前数，交换if (m != i){Swap(&a[i], &a[m]);}}
}

优化：一趟遍历找出最大与最小值。

void SelectSort(int* a, int n)
{int left = 0;int right = n - 1;while(left < right){int max = left;int min = left;for (int i = left; i <= right; i++){//找最大值if (a[i] > a[max])max = i;//找最小值if (a[i] < a[min])min = i;}Swap(&a[min], &a[left]);//若最大值在最左侧，其会被换到最小值位置if (max == left){max = min;}Swap(&a[max], &a[right]);left++;right--;}
}

选择排序的特性总结：

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

2.2.2堆排序

堆排序在前面已经写过，点击链接跳转至堆排序

排序的特性总结：

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

2.3交换排序

• 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
• 交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序

冒泡排序相信大家都非常熟悉了，直接上代码吧。

void BubbleSort(int* a, int n)
{//进行多少趟比较for (int i = 0; i < n - 1; i++){//每趟比较的次数for (int j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}Print(a, n);}
}

冒泡排序的特性总结：

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

2.3.2快速排序

Hoare法

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

如图所示：
right从右往左找小于key的；left从左往右找大于key的，然后二者交换。继续找，直到二者相遇；相遇以后，需要和key位置数交换，此时key位置的数就处在了排序完成后应该在的位置。
然后再对key位置左边与右边进行上述相同的操作即可完成排序。

为什么二者相遇的位置一定比key小呢？
此处就是该算法的精髓，因为是right先走，right停下来的位置一定比key小，或者right到了key位置。、

void QuickSort(int* a, int left,int right)
{//若区间只有一个数，则已经有序if (left >= right)return;int begin = left;int end = right;int key = left;//基准值while (left < right){//从右往左，找比key位置小的，不小就左移while (left < right && a[right] >= a[key]){right--;}//从左往右，找比key位置大的，不大就右移while (left < right && a[left] <= a[key]){left++;}//left位置比key大，right位置比key小。交换Swap(&a[left], &a[right]);}//left与right相遇，那就与key交换Swap(&a[key], &a[right]);key = left;//递归左右区间//[begin,key-1] key [key+1,end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}

我们都知道快排很快，它的时间复杂度为O(N*logN)，但真的是这样吗？

思考：若数据有序或已经接近有序，该算法还快吗？

如果是这种情况，那么这个基准值每次都会选到最小的值，此时它的时间复杂度就是N^2。那有什么解决办法吗？
使用随机取key法或三数取中法。

• 随机数选key就是每次选的key都不一定，但有时可以避免最坏情况

	int begin = left;int end = right;//使随机数的范围再[left,rihgt]中int randk = rand() % (right - left);randk += left;//为了我们后面代码的逻辑不改变，将randk位置与left位置交换Swap(&a[left], &a[randk]);int key = left;//基准值

• 三数取中法
  这里的取中并不是取中间的数，而是三个数中，位于中间大小的数。

int GetMid(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[mid] < a[right]){if (a[mid] > a[left]){//left < mid < rightreturn mid;}else if (a[left] < a[right]){//mid < left < rightreturn left;}else{	//left < right < midreturn right;}}else//a[mid] > a[right]{if (a[mid] < a[left]){//right < mid < leftreturn mid;}else if (a[left] > a[right]){//right < left < midreturn left;}else{//left < right < midreturn right;}}
}void QuickSort(int* a, int left,int right)
{//若区间只有一个数，则已经有序if (left >= right)return;int begin = left;int end = right;使随机数的范围再[left,rihgt]中//int randk = rand() % (right - left);//randk += left;为了我们后面代码的逻辑不改变，将randk位置与left位置交换//Swap(&a[left], &a[randk]);int midk = GetMid(a, left, right);Swap(&a[left], &a[midk]);int key = left;//基准值while (left < right){//从右往左，找比key位置小的，不小就左移while (left < right && a[right] >= a[key]){right--;}//从左往右，找比key位置大的，不大就右移while (left < right && a[left] <= a[key]){left++;}//left位置比key大，right位置比key小。交换Swap(&a[left], &a[right]);}//left与right相遇，那就与key交换Swap(&a[key], &a[right]);key = left;//递归左右区间//[begin,key-1] key [key+1,end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}

• 小区间优化
  当快排进行到数据元素比较少的时候，使用快速排序走递归的消耗是比较大的，最后一层的递归占整个递归的80%-%90。是不值当的，如下图这种情况：

对于这种情况，我们给出小区间优化的方式。即当递归进入待排序数字只剩下10个左右时，直接使用插入排序。

	//小区间优化if (right - left + 1 < 10){//进行插入排序InsertSort(a + left, right - left - 1);}else{//继续进行递归}

前后指针法

先看一下动图演示

此方法与第一种方法不同之处在于，它不是一左一右了。使用前后指针，cur指针为前指针，它找比key小的，找到以后，先让prev++，然后二者在交换，最后自己在++；当cur超出范围时，prev位置小于key，将prev与key交换，本轮排序结束。

void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int prev = left;int cur = prev + 1;int key = left;//当前值比key小，先++prev,然后交换while (cur <= right){if (a[cur] < a[key]){++prev;Swap(&a[prev], &a[cur]);}cur++;}//使key位于正确位置Swap(&a[key], &a[prev]);key = prev;//递归左右区间QuickSort2(a, left, key - 1);QuickSort2(a, key + 1, right);
}

为了避免自己与自己进行无意义的交换，代码也可以写成这样：

void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int prev = left;int cur = prev + 1;int key = left;//当前值比key小，先++prev,然后交换/*while (cur <= right){if (a[cur] < a[key]){++prev;Swap(&a[prev], &a[cur]);}cur++;}*/while (cur <= right){if (a[cur] < a[key] && ++prev != cur){Swap(&a[prev], &a[cur]);}cur++;}//使key位于正确位置Swap(&a[key], &a[prev]);key = prev;//递归左右区间QuickSort2(a, left, key - 1);QuickSort2(a, key + 1, right);
}

挖坑法

挖坑法与Hoare法类似

将步骤拆解下来就是下面这样

void QuickSort3(int* a, int left, int right)
{if (left >= right)return;int begin = left;int end = right;int key = a[left];int pos = left;//选定坑位while (left < right){while (left <  right && a[right]>= key){right--;}//从右边找，找到了比key小的，数据变化，坑位变化a[pos] = a[right];pos = right;//换坑while (left < right && a[left] <= key){left++;}//从左边找，找到了比key大的，数据变化，坑位变化a[pos] = a[left];pos = left;}//此时left与right相遇a[pos] = key;//[begin,pos-1] pos [pos+1,end]QuickSort3(a, begin, pos - 1);QuickSort3(a, pos + 1, end);
}

非递归版本

如果待排序的数据量非常大时，会递归很多次，可能会导致栈溢出，所以非递归版本也是我们必须掌握的。
其实非递归版本也是利用栈后进先出的特性，模拟出的递归的效果。

void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(&st);//左右区间先入栈StackPush(&st, right);StackPush(&st, left); //栈不为空，就取栈顶元素排序while (!StackEmpty(&st)){int begin = StackTopElement(&st);StackPop(&st);int end = StackTopElement(&st);StackPop(&st);//前后指针法，进行单趟排int prev = begin;int cur = prev + 1;int key = begin;while (cur <= end){if (a[cur] < a[key] && ++prev != cur){Swap(&a[prev], &a[cur]);}cur++;}//使key位于正确位置Swap(&a[key], &a[prev]);key = prev;//[begin,key-1] key [key+1,end]//继续入栈,先入右，再入左if (key + 1 < end){StackPush(&st, end);StackPush(&st, key + 1);}if (key - 1 > begin){StackPush(&st, key - 1);StackPush(&st, begin);}}StackDestroy(&st);
}

快速排序的特性总结：

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

3. 空间复杂度：O(logN)
4. 稳定性：不稳定

2.4归并排序

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

归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。

1. 将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
2. 将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表

分的过程就是将数据拆到只有一个数据时，此时该数据自身有序。
什么时候就拆好了呢？
当数据的左右边界相等时，就只剩下一个数据，此时可以合并了，如下图：

那它的合并又是怎么合的呢？难道在原数组上合并吗？
肯定不是这样的，如果在原数组上合并的话，那数据就乱套了。
因此，我们需要借助一个临时数组来保存数据，待数据合并后，在将临时数组中的数据拷回到原数组中。

动图演示：

递归版本

#include<string.h>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);//两区间已经有序，进行合并int left1 = begin, right1 = mid;int left2 = mid + 1, right2 = end;int tmpi = begin;//往tmp数组存放位置的下标//两区间均未遍历完while (left1 <= right1 && left2 <= right2){//按序存放进tmp数组if (a[left1] < a[left2]){tmp[tmpi++] = a[left1++];}else{tmp[tmpi++] = a[left2++];}}//有一个遍历完了while (left1 <= right1){tmp[tmpi++] = a[left1++];}while (left2 <= right2){tmp[tmpi++] = a[left2++];}//tmp数组中的数据已经有序，拷贝回原数组//注意数据拷贝元素的位置memcpy(a + begin, tmp + begin, sizeof(int) * (tmpi - begin));
}void MergeSort(int* a, int n)
{//开辟临时数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

非递归版本

该方法的思想和递归相似。

void MergeSortNonR(int* a, int n)
{//开辟临时数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1; //最开始为 1个一组,每组均有序while (gap < n){//gap个分为一组,每次分两组，然后取小进行尾插for (int i = 0; i < n; i += 2*gap){int left1 = i, right1 = left1 + gap - 1;int left2 = left1 + gap, right2 = left2 + gap - 1;int tmpi = i;while (left1 <= right1 && left2 <= right2){//按序存放进tmp数组if (a[left1] < a[left2]){tmp[tmpi++] = a[left1++];}else{tmp[tmpi++] = a[left2++];}}//有一个遍历完了while (left1 <= right1){tmp[tmpi++] = a[left1++];}while (left2 <= right2){tmp[tmpi++] = a[left2++];}//将临时数组拷回原数组memcpy(a + i, tmp + i, sizeof(int) * tmpi - i);}gap *= 2;}free(tmp);tmp = NULL;
}

运行上述代码，我们会发现会出现越界问题

我们分析一下：

• 首先，我们的left1=i，i<n，所以left1不可能越界
• right1可能越界，如果right1越界那说明数组已经有序了，不需要进行排序
• left2可能越界，如果right2越界那说明数组也已经有序了，不需要进行排序
• right2也可能越界，当right2越界时，[left2,未越界] right2，那么我们需要对未越界的部分进行排序。

	if (right1 >= n || left1 >= n){break;}if (right2 >= n){right2 = n - 1;}

到此，我们的归并排序就算完美了。

void MergeSortNonR(int* a, int n)
{//开辟临时数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1; //最开始为1个一组,每组均有序while (gap < n){//gap个分为一组,每次分两组for (int i = 0; i < n; i += 2*gap){int left1 = i, right1 = left1 + gap - 1;int left2 = left1 + gap, right2 = left2 + gap - 1;//printf("[%d,%d][%d,%d] ", left1, right1, left2, right2);//无需再排if (right1 >= n || left1 >= n){break;}//部分要排if (right2 >= n){right2 = n - 1;}int tmpi = i;while (left1 <= right1 && left2 <= right2){//按序存放进tmp数组if (a[left1] < a[left2]){tmp[tmpi++] = a[left1++];}else{tmp[tmpi++] = a[left2++];}}//有一个遍历完了while (left1 <= right1){tmp[tmpi++] = a[left1++];}while (left2 <= right2){tmp[tmpi++] = a[left2++];}//将临时数组拷回原数组memcpy(a + i, tmp + i, sizeof(int) * (tmpi - i));}gap *= 2;//printf("\n");}free(tmp);tmp = NULL;
}

归并排序的特性总结：

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

2.5计数排序

计数排序属于非比较排序，那什么较非比较排序呢？–排序的关键逻辑不是比较出来的。
那具体是如何实现的呢？

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

动图演示：

从图中我们可以看出，它是将数据的个数收集到一个临时数组中，最后根据临时数组的内容有序放回到原数组中。
但我们这个临时数组开多大呢？和原数组一样大吗？那未免有点太浪费了。
我们只需要找出数据中的最大与最小值，数组大小开最大-最小+1就够了。

例如：假设数组元素大小为100-200之间的数据，那就只需要开100+1个空间。 由于数组下标是从0开始的，而我最小的数据是100，那101就越界了，所以我们需要将待排序数据减去所有数组中的最小值再放进临时数组中。

void CountSort(int* a, int n)
{int max = a[0];int min = a[0];for (int i = 0; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}//所开数组的大小int range = max - min + 1;int* tmp = (int*)calloc(range, sizeof(int));if (tmp == NULL){perror("calloc fail");return;}//统计各数据的个数for (int i = 0; i < n; i++){tmp[a[i]-min]++;}int j = 0;for (int i = 0; i < range; i++){//当前数组元素不为0，还有为排序元素while (tmp[i]--){a[j++] = i + min;}}
}

计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

3.排序的比较

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n2)	O(n)（有序）	O(n2)	O(1)	稳定
简单选择排序	O(n2)	O(2)	O(n2)	O(1)	不稳定
直接插入排序	O(n2)	O(n)（有序）	O(n2)	O(1)	稳定
希尔排序	O(nlogn)~O(n2)	O(n1.3)	O(n2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(nlogn)	O(logn)~O(n)（递归）	不稳定
计数排序	O(Max(n,范围))	O(Min(n,范围))	O(Max(n,范围))	O(范围)	不稳定

稳定性：

若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定的都好理解，不稳定的如下：