初阶5 排序

本章重点

1. 排序的概念
2. 常见排序的算法思想和实现
3. 排序算法的复杂度以及稳定性分析

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]插入，原来位置上的元素顺序后移

性能总结：

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

void InsertSort(int* a, int n)
{//两层循环    第一层是用来确顶当前该比较哪个位置的数，用tmp来记录//		     第二层是用来进行从end到0方向的下标位置比较，//                  用tmp与之前的所有位置的数进行比较for (int i = 1; i < n ; i++){int end = i-1;int tmp = a[i];while (end >= 0){if (tmp > a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

2.1.2 希尔排序(缩小增量法)

基本思想：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

性能总结：

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

void ShellSort(int* a, int n)
{// 三层循环，第一层：对gap的递减，达成预排序//			 第二层和第三层的方法就和直接插入排序一样了// // gap > 1 预排序// gap == 1 直接插入排序int gap = n;while (gap > 1){gap = gap / 2;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;}}
}

2.2 选择排序

2.2.1 直接选择排序

基本思想：

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

也可以一次循环直接将最小和最大都选出来（如下面代码中那样）

步骤：

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

特性总结：

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

直接选择排序在任何情况都是O(N^2) 包括有序或接近有序，
所以它的排序效率还没有直接插入排序的效率高

//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);// 这里是防止maxi和begin相等时，由于换位而导致maxi的交换发生错误if (maxi == begin){	maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

2.2.2 堆排序

基本思想：

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

特性总结：

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

//交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//像下调整(建大堆)（数组、数组大小、父节点下标）
void AdjustDown(int* a, int n, int parent)
{//默认认为左孩子大int child = parent * 2 + 1;//超过数组大小while (child < n){//确认child指向大的孩子if (child + 1 < n && a[child + 1] > a[child]) //第一处：a[child + 1] > a[child]{++child;}//孩子大于父亲，交换,继续调整//这里换为 > 是大堆的创建if (a[child] > a[parent])  //第二处：a[child] > a[parent]{swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}//将第一处和第二处的>换为<则是建小堆
}
//堆排序
void HeapSort(int* a, int size)
{// 向下调整建堆 -- O(N)// 升序：建大堆for (int i = (size - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, size, i);}int end = size - 1;//(end表示数组需要与array[0]交换的下标位置)while (end > 0){Swap(&a[0], &a[end]);//交换array[0]和array[end]的位置AdjustDown(a, end, 0);//向下调整end--;}
}

2.3 交换排序

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1 冒泡排序

基本思想:

用当前的和前一个进行比较，将值大的往后移动，值小的往前移动。

冒泡排序也时最简单，最常学习的排序，缺点就是排序效率比较差

特性总结：

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

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

2.3.2 快速排序

基本思想：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

单趟排序的作用：

1. 使得key到了准确的位置
2. 使得key左边的数都小于key，key右边的数都大于key

然后再对其递归排序数组key的左边和右边，最终就可排好序

注意的点：

• 左边和右边都可以做key，但是
• 左边做key，右边要先走
• 右边做key，左边要先走
• 这是为了保证相遇的位置，一定比key要小（左边做key的情况下）

三个坑：

1. 越界
   修改:
   while (a[right] > a[keyi])改为
   while (left < right && a[right] > a[keyi])

2. 死循环(存在与key相同数)
   修改:
   while (left < right && a[right] > a[keyi])改为
   while (left < right && a[right] >= a[keyi])

3. 交换失败
   修改:
   Swap(&a[left], &key)改为
   Swap(&a[left], &a[keyi])

原因:

• 未改变原数组值
• 能适应更多类型的值

void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int left = begin, right = end;int keyi = left;while (left < right){// 右边先走，找小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, keyi-1]  keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}

快速排序的优化

1. 三数取中优化

原理：

选择最左边，最中间，最右边的三个数作比较，选出最小的数作为key

//快排改进：key选值的三数取中
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end]){return mid;}else if (a[begin] > a[end]){return begin;}else{return end;}}else // a[begin] > a[mid]{if (a[mid] > a[end]){return mid;}else if (a[begin] < a[end]){return begin;}else{return end;}}
}
void MidQuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int keyi = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= a[key]){--right;}// 左边再走，找大while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1]  key [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

2. 小区间优化（主要对空间进行优化）：

到最后10个数的时候，用递归的话，可以看到还需要4层深度的递归
对最后一小段区域的排序，我们用直接插入排序就行

//小区间优化（优化空间）
void SpaceQuickSort(int* a, int begin, int end)
{if (begin >= end){return;}if ((end - begin + 1) < 10){// 小区间用直接插入替代，减少递归调用次数InsertSort(a + begin, end - begin + 1);}else{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int keyi = left;while (left < right){// 右边先走，找小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, keyi-1]  keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

快速排序的其他版本

1. Hoare
   以上

2. 挖坑法
   

void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int left = begin, right = end;int key = a[left];int hole = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;// 左边再走，找大while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;QuickSort(a, begin, hole - 1);QuickSort(a, hole + 1, end);
}

3. 快慢指针法

void PointQuickSort(int* a, int begin, int end)
{if (begin > end){return;}//小区间优化if ((end - begin + 1) < 10){// 小区间用直接插入替代，减少递归调用次数InsertSort(a + begin, end - begin + 1);}else{//三数选中间优化int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);//开始int prev = begin, cur = begin + 1;int keyi = prev;while (cur <= end){while (cur <= end){if (a[cur] >= a[keyi] && ++prev != cur)//++prev和cur的下标如果相等，就不要进行交换{Swap(&a[++prev], &a[cur]); //一定是先++prev，在用prev }cur++;}}Swap(&a[prev], &a[keyi]);PointQuickSort(a, begin, keyi -1 );PointQuickSort(a, keyi + 1, end);}
}

快速排序的非递归(栈)

//快速排序（非递归）
//利用堆实现的叫做深度优先
void QuickSortNonR(int* a, int begin, int end)
{ST st;StackInit(&st);StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)){int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);//进行一次快排int prev = left, cur = left + 1;int key = left;while (cur <= right){//++prev和cur的下标如果相等，就可以不用进行交换if (a[cur] < a[key] && ++prev != cur){Swap(&a[prev], &a[cur]); }cur++;}Swap(&a[prev], &a[key]);key = prev;// [left, key-1] keyi [key+1, right]if (key + 1 < right){StackPush(&st, key + 1);StackPush(&st, right);}if (left < key - 1){StackPush(&st, left);StackPush(&st, key - 1);}}StackDestroy(&st);
}

2.4 归并排序

基本思想：

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

原理图：
分解合并

第一层将一个数组分两个大组，
第二层再继续分，直到分成每组都只有一个为止
分解完了之后就是进行合并，每两个小数组，按顺序合并成一个大的数组
最终，合并称为一个有序的集合

归并排序是在原数组上进行的，用一个临时数组来做归并，把归并好的元素复制回原数组

//归并排序（递归实现）//归并子函数
//（在遇到需要malloc扩容的函数时，将malloc代码放入主函数，另写一个子函数用来完成递归）
void _MergeSort(int* a, int begin ,int end, int* temp)
{//最后只剩下一个数的时候就说明begin=end，返回if (begin >= end){return;}int mid = (begin + end) / 2;//[begin, mid] [mid+1, end] 递归让子区间都有序_MergeSort(a, begin, mid, temp);    //递归左半区_MergeSort(a, mid+1, end, temp);    //递归右半区//归并int begin1 = begin, end1 = mid;     //左区间[begin1, end1]int begin2 = mid + 1, end2 = end;   //右区间[begin2, end2]int i = begin;//如果左右两个区间都没有结束就继续，只要有一个区间结束就终止while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){temp[i++] = a[begin1++]; }else{temp[i++] = a[begin2++];}}//将没走到头的区间按顺序放到后面while (begin1 <= end1){temp[i++] = a[begin1++];}while (begin2 <= end2){temp[i++] = a[begin2++];}//将临时区间的数据拷贝回原数组memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}//归并主函数
void MergeSort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n-1, temp);free(temp);temp = NULL;
}

归并排序的非递归写法
数据有 4 种情况

1. 数的个数是4的倍数
2. end1 越界
3. begin2 越界
4. end2 越界

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}// 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并int rangeN = 1;while (rangeN < n) {for (int i = 0; i < n; i += 2 * rangeN){// [begin1,end1][begin2,end2] 归并int begin1 = i, end1 = i + rangeN - 1;int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;int j = i;// end1 begin2 end2 越界的三种情况//一定需要按顺序进行判断，不然会出错//end1越界，情况1，//解决：直接退出本次循环，可以不让后面的进行归并，再下一次循环时再排序if (end1 >= n){break;}//begin2出界，情况2，//解决：直接退出本次循环，可以不让后面的进行归并，再下一次循环时再排序else if (begin2 >= n){break;}//end2越界，情况3//解决：让end2等于数组最后的下标else if (end2 >= n){end2 = n - 1;}//开始按顺序归并while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}// 归并一部分，拷贝一部分memcpy(a + i, tmp + i, sizeof(int)*(end2 - i + 1));}rangeN *= 2;}free(tmp);tmp = NULL;
}

如果一次性拷贝

{......//修正路线if (end1 >= n){end1 = n - 1;begin2 = n;end2 = n - 1;}else if (begin2 >= n){begin2 = n;end2 = n - 1;}else if (end2 >= n){end2 = n - 1;}......
}

特性总结：

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

3.非比较排序

3.1 计数排序

基本思想：
之前学习的排序，无论是希尔排序，还是堆排序，都用的是比较两个数大小的方式进行的排序

而计数排序不是用比较的方法来进行排序的，它利用的是数组下标的计数来进行的排序

具体实现方法如下：

算法原理：
现假设有一组0~4的数据需要排序：{ 2，3，3，4，0，3，2，4，3 }

创建一个临时数组temp来依次记录每个数的出现次数

原数组中，

   0出现了1次，就在temp下标为0的位置记录11没有出现，  就在temp下标为1的位置记录02出现了2次，就在temp下标为0的位置记录23出现了4次，就在temp下标为0的位置记录34出现了2次，就在temp下标为0的位置记录2

数组每一个下标位置的值，代表了数列中对应整数出现的次数。

有了这个 “统计结果”，排序就很简单了。
直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

这样就能得到一个有序序列了

这就是计数排序的过程，因为他没有进行数与数之间的比较，
所以他的性能甚至快过那些O( log N) 的排序

可以看到上面的排序是一种特殊情况，那如果我们要排序的数组是 9000~9009，那么是不是得浪费前九千多个空间？

又或者是在原数组里面有负数的情况下是不是九不能进行计数排序了？

这就要对现有的算法进行一些小小的升级了

算法升级
例如我们有一组这样的数：9004，9001，9002，9005，9004，9001

这个数组，最大是9005，但最小的数是9001，如果用长度为9005的数组，那么按照上面的方法排序，肯定会太过浪费

事实上我们只需要开辟大小为5的数组即可（最大数 - 最小数 + 1）9005 - 9001 +1 = 5

用下标为0的记录9001，用下标为4的记录9005

当然，对于负数也一样可以使用，这里就不一一展示了

性能特点：

• 稳定性：稳定
• 时间复杂度：O（n+k）
• 空间复杂度：O（n+k）
• 对于数据率不是很大，并且数据比较集中时，计数排序是一个很有效的排序算法

计数排序的局限性：

不能对小数进行排序，只适用于整数

分4步实现

• 找到数组中的最大最小值
• 计算范围，开辟临时数组空间
• 统计相同元素出现次数
• 根据计数结果将序列依次放回原来的数组中

//计数排序
void CountSort(int* a, int n)
{//确定数组里面的最大最小值int max = a[0], min = a[0];for (int i = 1;i < n;i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}//范围 = 最大值 - 最小值 + 1//比如从 0 到 9 有10个数int range = max - min + 1;//用calloc开辟range个大小为int的空间，并给每个元素赋值为0int* countA = (int*)calloc(range, sizeof(int));if (countA == NULL){perror("calloc fail");exit(-1);}//统计相同元素出现的次数for (int i = 0;i < n;i++){//a[i] - min 是a[i]下标在countA里面对应的相对位置countA[a[i] - min]++;}//排序，根据计数结果将序列依次放回原来的数组中int k = 0;for (int j = 0;j < range;j++){while (countA[j]--){//j + min 就是数组元素的大小a[k++] = j + min;}}free(countA);
}

排序算法复杂度及稳定性分析

稳定性

稳定性的价值：

比如再考试排名的时候，第三名种有三个人的成绩相同，那么如果先交卷的人是第三名的话，就要去再成绩排序的时候保证其稳定性

各种常见排序算法的总结