【探索排序算法的魅力：优化、性能与实用技巧】（中）：https://developer.aliyun.com/article/1425258
根据上面的算法，要排序的数是一组数据量极大的重复数字，此时就是上面的第二种写法，此时一直++cur就可以排序好这个数组，时间复杂度就是O(N)。
void PartSort(int *a,int left,int right) { if(left >= left) return; // 三数取中 int midi = GetMidi(a,left,right); Swap(&a[midi],&a[left]); int begin = left; int end = right; int key = left; int cur = left; while(cur <= right) { if(a[key] > a[cur]) { Swap(&a[key],&a[left]); ++cur; ++left; } else if(a[key == a[cur]) { ++cur; } else { Swap(&a[key],&a[right]); --right; } } // [begin,left-1][left,right][right+1,end] PartSort(a,begin,left-1); PartSort(a,right+1,end); }
我们现在再来想一下快排的效率，当数组的数据每次交换后，key就是中间位置，那么此时的时间复杂度就是O(N*logN)，但是当数组数据有序的时候，key每次就是第一个位置，那么此时的时间复杂度就是O(N^2)，那么此时怎么优化呢？？？
1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
三数取中法选key：有了三数取中，快排就不会出现最坏情况。
//三数取中 int GetMidi(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[right] > a[mid]) { return mid; } else if(a[right] < a[left]) //mid最大 { return left; } else { return right; } } else //a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] > a[right]) //mid最小 { return right; } else { return left; } } } int PartSort(int* a, int left, int right) { int midi = GetMidi(a, left, right); Swap(&a[left], &a[midi]); ......//三种PartSort任意一种 }
根据完全二叉树的特点，最后一层的节点个数占总数的50%。对比到快速排序的递归而言，递归层数越深，每层递归的次数变多，消耗也是越大的。我们拿10个数据对比一下：
我们要快速排序10个数，就要递归3层，消耗太多，非常的不划算。因此递归到小的子区间时，可以考虑使用插入排序。该小区间就可以设置为只剩下10个数时候开始使用直接插入排序，最后一层的节点个数占总数的50%，倒数第二层的节点个数占总数的25%，倒数第三层的节点个数占总数的12.5%，根据上面的计算，能优化87.5%递归算法。
递归到小的子区间时，可以考虑使用直接插入排序。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序 void QuickSort(int array[], int left, int right) { //= 代表只剩下一个值 if (left >= right) return; //将剩下的10个元素进行直接插入排序 if ((right - left + 1) > 10) { // 按照基准值对array数组的 [left, right)区间中的元素进行划分 int div = PartSort(array, left, right); // 划分成功后以div为边界形成了左右两部分 [left, div-1) 和 [div+1, right) // 递归排[left, div-1) QuickSort(array, left, div - 1); // 递归排[div+1, right) QuickSort(array, div + 1, right); } else { //指针+-跳过指向类型大小 InsertSort(array + left, right - left + 1); } }
掌握了递归思路的快速排序，我们再来掌握一下非递归思路的快速排序，非递归的快速排序需要使用栈来解决。我们先处理左边数据，再处理右边数据，根据栈先进后出的特点，因此右边数据先入栈，左边数据再入栈。这里也可以使用队列实现，不过队列不是先处理左边数据，再处理右边数据而是是一层一层处理，所以这里我们不用队列，使用栈能更好体现非递归的思路。
//导入之前写的栈实现接口 #include "Stack.h" void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(&st); //先进后出，先入右，再入左 StackPush(&st, right); StackPush(&st, left); while (!StackEmpty(&st)) { int left = StackTop(&st); StackPop(&st); int right = StackTop(&st); StackPop(&st); int keyi = PartSort(a, left, right); //分为三个区间：[left,keyi-1] keyi [keyi+1，right] //先入右区间，再入左区间 if (keyi + 1 < right) { StackPush(&st, right); StackPush(&st, keyi + 1); } if (left < keyi - 1) { StackPush(&st, keyi - 1); StackPush(&st, left); } } StackDestroy(&st); }
这里提出一个问题：递归是使用的系统栈，而上面的栈是使用的人工栈，栈的深度不是一样的嘛，有什么区别？？？
人工栈是通过数组实现，是在堆上开辟的，而递归使用的系统栈，系统会自动为每个函数调用分配一帧。递归的栈深度受系统栈的限制，通常比人工栈小得多，系统栈很容易满栈。
#include <stdio.h> int Func(int n) { if (n == 0) return 0; return Func(n - 1) + n; } int main() { printf("%d\n", Func(10000)); return 0; }
我们可以看到当n为5215时，我们的系统栈就满了，递归是由消耗的，所以掌握非递归的快速排序是非常有意义的。
快速排序的特性总结：
- 1.快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 2.时间复杂度：O(N*logN)
- 3.空间复杂度：O(logN)
- 4.稳定性：不稳定
2.4 归并排序
2.4.1基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
2.4.2归并排序
我们这里的归并是让小区间数据有序，先将数组分为若干小区间，然后将小区间的数按照从小到大的顺序尾插到tmp数组中，再拷贝回原数组，之后再让两个小区间的数尾插插到tmp数组中，再拷贝回原数组......依次，直至整个数组有序。
//为防止每次递归调用都会malloc空间，这里写一个子函数 void _MergeSort(int* a, int left, int right, int* tmp) { if (right <= left) return; int mid = (right + left) / 2; //分割 //[left,mid] [mid+1,right] _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); //归并到tmp数组，再拷贝回去 // a->[left,mid] [mid+1,right]->tmp int begin1= left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //把tmp的数组归并到原数组上 memcpy(a + left, tmp + left, (right - left + 1) * sizeof(int)); } 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); }
递归图：
上面的快速排序我们写了非递归的写法，它是一种很明显的前序方法，左边排完序就不需要再管了，而这里的归并是否也有非递归的写法呢？很明显，归并排序当人也有非递归的写法，但是我们这里的归并是一种后序，排完左边的序列还需要回到根，比如上面的 10 6 7 1，左边排序完是 6 10，右边排序完是 1 7，其序列还未有序，需要回到根后再排序，比较麻烦，这里我们就不使用栈的方法呢？这里我们可以借鉴一下斐波那契数列的非递归的方法。
我们怎么才能实现上面的归并呢？我们可以定义一个gap，通过gap确定每次排序的区间。我们先来实现一下一一归并的写法。
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; //i的位置依次是0，2，4...... for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1;//[0,0] int begin2 = i + gap,end2 = i + 2 * gap - 1;//[1,1] //第一次一一归并的两个区间[0,0] [1,1] //第二次一一归并的两个区间[2,2] [3,3] int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //拷贝回原数组 memcpy(a + i, tmp + i, 2 * gap * sizeof(int)); } free(tmp); }
所以我们只需要控制gap就可以实现非递归的归并排序。gap的取值是1，2，4.......当gap小于数组的元素就停止。
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { //i的位置依次是0，2，4...... for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1;//[0,0] int begin2 = i + gap, end2 = i + 2 * gap - 1;//[1,1] //第一次一一归并的两个区间[0,0] [1,1] //第二次一一归并的两个区间[2,2] [3,3] int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //拷贝回原数组 memcpy(a + i, tmp + i, 2 * gap * sizeof(int)); } gap *=2; } free(tmp); }
上面的数据刚好是2的整个倍，可是如果数据是9个呢？
此时我们再进行归并就会出现越界的问题。数据个数为9，下标为9及以上的都是越界。
此时每次归并上都出现了越界的问题，越界的问题都出现再end1,begin2和end2上面。这里我们需要想一个问题，我们每次排序的数据必须成对出现才能归并嘛？其实，如果数据不成对出现，我们就不要归并这数据，因为它本身就是独自出现，本身就可以当作有序。所以我们只用加下面的代码就可以了。如果越界了，这组数据就不用管了，直接退出即可。但是当只有end2越界的时候，此时需要归并，因为此时有两组数据需要归并。
//如果第二组不存在，这一组就不用归并了 if (end1 >= n) { break; } //如果第二组的右边界越界，修正下标 if (end2 >= n) { //此时需要归并,只用修改下标即可 end2 = n - 1; }
同时我们还需要改一下memcpy拷贝的个数
memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
归并排序的特性总结：
- 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 2. 时间复杂度：O(N*logN)
- 3. 空间复杂度：O(N)
- 4. 稳定性：稳定
2.5 非比较排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 1. 统计相同元素出现次数
- 2. 根据统计的结果将序列回收到原来的序列中
上面的这种就是我们的计数排序，如果我们的数据是101、105、199，我们再通过上面的方法就要开辟200个空间大小的数组，就会存在很大的空间浪费，所以我们就要不能使用绝对映射（一个数据存在对应的下标下面），这里需要使用我们的相对映射（最大值-最小值获取区间）（根据a[i] - min）就只用开辟相对较少的空间。
void CountSort(int* a, int n) { int max = a[0]; int min = 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*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); return; } memset(count, 0, sizeof(int) * range); //统计数据出现的次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } //排序 int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } } }
计数排序的特性总结：
- 1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 2. 时间复杂度：O(MAX(N,范围))
- 3. 空间复杂度：O(范围)
- 4. 稳定性：稳定
- 5.局限性：只能排序整型数据
2.6内排序和外排序
内排序和外排序是计算机科学中与排序算法相关的两个重要概念。
- 内排序（In-Place Sorting）：
- 内排序是指在排序过程中，所有数据都存储在计算机的内存中进行排序的方法。
- 这意味着排序算法不需要使用外部存储（如硬盘或其他存储设备）来存储数据。
- 内排序的优点是速度较快，因为内存访问通常比外部存储快得多。
- 常见的内排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。
- 外排序（External Sorting）：
- 外排序是指排序的数据量太大，无法完全放入计算机的内存中，因此需要使用外部存储设备来辅助排序的方法。
- 外排序通常涉及到将大量数据分割成较小的块，分别在内存和外部存储之间进行排序，然后再将这些排序好的块合并起来以获得最终的有序结果。
- 外排序的主要应用场景是处理大型数据集，如数据库排序、外部存储设备上的大文件排序等。
- 常见的外排序算法包括归并排序、多路归并排序等。
假设我们当前的内存是1G，当我们要排序一个10亿个整型数据的时候，要怎么排序呢？
- 10亿个整型数据 = 1024 * 1024 *1024 Byte * 4 = 4G > 内存1G，在内存中无法排序。
- 4G的整型数据太大而无法一次性加载到内存中，需要使用外排序。
- 外排序通常涉及将数据分成多个小块，每个小块可以适应内存大小。
- 首先，将数据分块并逐块加载到内存中，对每个块使用内排序算法进行排序。
- 排序后的块可以写回磁盘或者合并成更大的块。
- 最后，进行块之间的合并操作，以获得最终排序结果。
3.排序算法复杂度及稳定性分析
稳定性：相同的数据进行排序后，其相对位置没有发生变化，就说明该排序具有稳定性。
4.选择题练习
1. 快速排序算法是基于（ ）的一个排序算法。
A分治法
B贪心法
C递归法
D动态规划法
解析：快速排序是基于分治法的一个排序算法。
2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较（ ）次？（采用从后往前比较）
A 3
B 4
C 5
D 6
解析：第8个记录45插入到有序表时，前7个数据已经有序（15,23,38,54,60,72,96)，次数依次向前比较，需要比较5次。
3.以下排序方式中占用O（n）辅助存储空间的是
A 简单排序
B 快速排序
C 堆排序
D 归并排序
解析：归并排序需要将小区间排序的结果保存下来，然后再拷贝到原数组上
4.下列排序算法中稳定且时间复杂度为O(n2)的是（ ）
A 快速排序
B 冒泡排序
C 直接选择排序
D 归并排序
5.关于排序，下面说法不正确的是
A 快排时间复杂度为O(N*logN)，空间复杂度为O(logN)
B 归并排序是一种稳定的排序,堆排序和快排均不稳定
C 序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
6.下列排序法中，最坏情况下时间复杂度最小的是（ ）
A 堆排序
B 快速排序
C 希尔排序
D 冒泡排序
7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排序结果是（）
A 34，56，25，65，86，99，72，66
B 25，34，56，65，99，86，72，66
C 34，56，25，65，66，99，86，72
D 34，56，25，65，99，86，72，66
解析：这里采用的是挖坑法，右边先找小，左边再找到，最后将关键字65放到坑位。
