简介
- 原地排序：就是指空间复杂度为O(1)的排序算法。
- 稳定性：如果待排序的序列中存在值等的元素，经过排序之后，相等元素之间原有的先后顺序不变，就说明这个排序算法时稳定的。
| 排序类型 | 时间复杂度 | 是否稳定 | 是否原地排序 | 适应场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | 是 | 是 | |
| 插入排序 | O(n^2) | 是 | 是 | |
| 选择排序 | O(n^2) | 否 | 是 | |
| 快速排序 | O(nlogn) | 否 | 是 | |
| 归并排序 | O(nlogn) | 是 | 否 | |
| 桶排序 | O(n) | 是 | 否 | |
| 计数排序 | O(n+k)，k是数据范围 | 是 | 否 | |
| 基数排序 | O(dn)，d是纬度 | 是 | 否 |
冒泡排序
基本思想：
1）冒泡排序只会操作相邻的两个数据。
2）对相邻两个数据进行比较，看是否满足大小关系要求，若不满足让它俩互换。
3）一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
4）优化：若某次冒泡不存在数据交换，则说明已经达到完全有序，所以终止冒泡。
代码实现
void bubbleSort(int nums[], int n) {
if (n <= 1) {
return;
}
for (int i = 0; i < n; i++) {
bool flag = false;
for (int j = 0; j < n - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int tmp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = tmp;
flag = true;
}
}
// 无数据交换
if (!flag) {
break;
}
}
}
插入排序
基本思想
首先，我们将数组中的数据分为2个区间，即已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间中的元素一直有序。重复这个过程，直到未排序中元素为空，算法结束。
代码实现
void insertSort(int nums[], int n) {
if (n <= 1) {
return;
}
for (int i = 1; i < n; i++) {
int tmp = nums[i];
int j = i - 1;
for (; j >= 0; j--) {
if (nums[j] > tmp) {
nums[j + 1] = nums[j];
} else {
break;
}
}
nums[j + 1] = tmp;
}
}
选择排序
基本思想
选择排序算法也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，并将其放置到已排序区间的末尾。
代码实现
void selectSort(int nums[], int n) {
if (n <= 1) {
return;
}
for (int i = 0; i < n - 1; i++) {
int idx = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[idx]) {
idx = j;
}
}
if (idx == i) {
continue;
}
int tmp = nums[i];
nums[i] = nums[idx];
nums[idx] = tmp;
}
}
快速排序
基本思想
如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。然后遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将povit放到中间。经过这一步之后，数组p到r之间的数据就分成了3部分，前面p到q-1之间都是小于povit的，中间是povit，后面的q+1到r之间是大于povit的。根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。
代码实现
void arraySwap(int nums[], int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
int partition(int nums[], int p, int r) {
int pivot = nums[r];
int i = p;
for (int j = p; j < r; j++) {
if (nums[j] < pivot) {
arraySwap(nums, i, j);
i++;
}
}
arraySwap(nums, i, r);
return i;
}
void quickSortC(int nums[], int p, int r) {
if (p >= r) {
return;
}
int q = partition(nums, p, r);
quickSortC(nums, p, q - 1);
quickSortC(nums, q + 1, r);
}
void quickSort(int nums[], int n) {
quickSortC(nums, 0, n - 1);
}
关于取分区点优化
- 三数取中法
- 随机法
应用
- 查找第K大元素
归并排序
基本思想
先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分合并到一起，这样整个数组就有序了。
代码实现
void arrayMerge(int nums[], int p, int q, int r) {
int i = p;
int j = q + 1;
int k = 0;
int* tmp = new int[r - p + 1];
while (i <= q && j <= r) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
while (i <= q) {
tmp[k++] = nums[i++];
}
while (j <= r) {
tmp[k++] = nums[j++];
}
for (int i = 0; i < r - p + 1; i++) {
nums[p + i] = tmp[i];
}
delete [] tmp;
}
void mergeSortC(int nums[], int p, int r) {
if (p >= r) {
return;
}
int q = (p + r) / 2;
mergeSortC(nums, p, q);
mergeSortC(nums, q + 1, r);
arrayMerge(nums, p, q, r);
}
void mergeSort(int nums[], int n) {
mergeSortC(nums, 0, n - 1);
}
桶排序
基本原理
1）将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。
2）桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
代码实现
struct barrel {
int node[10];
int count;
};
int partitionBucket(int *arr, int left, int right) {
int i = left;
int j = right;
int key = arr[left];
while (i < j) {
while ((i < j) && (arr[j] >= key)) {
j--;
}
if (i < j) {
arr[i] = arr[j];
}
while ((i < j) && (arr[j] <= key)) {
i++;
}
if (i < j) {
arr[j] = arr[i];
}
}
arr[i] = key;
return i;
}
void quickSortBucket(int *arr, int left, int right) {
if (left >= right) {
return;
}
int q = partitionBucket(arr, left, right);
quickSortBucket(arr, left, (q - 1));
quickSortBucket(arr, (q + 1), right);
}
void bucketSort(int *arr, int size) {
int max;
int min;
max = min = arr[0];
for (int i = 0; i < size; i++) {
if (arr[i] > max) {
max = arr[i];
}
else if (arr[i] < min) {
min = arr[i];
}
}
int num = (max - min + 1) / 10 + 1;
struct barrel *pBarrel = (struct barrel*)malloc(sizeof(struct barrel) * num);
memset(pBarrel, 0, sizeof(struct barrel) * num);
for (int i = 0; i < size; i++) {
int k = (arr[i] - min + 1) / 10;
(pBarrel + k)->node[(pBarrel + k)->count] = arr[i];
(pBarrel + k)->count++;
}
int pos = 0;
for (int i = 0; i < num; i++) {
if ((pBarrel + i)->count != 0) {
quickSortBucket((pBarrel + i)->node, 0, (pBarrel + i)->count - 1);
for (int j = 0; j < (pBarrel + i)->count; j++) {
arr[pos++] = (pBarrel + i)->node[j];
}
}
}
free(pBarrel);
}
使用条件
1）要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序。
2）数据在各个桶之间分布是均匀的。
- 适用场景
1）桶排序比较适合用在外部排序中。
2）外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。
应用案例
1）需求描述：
有10GB的订单数据，需按订单金额（假设金额都是正整数）进行排序但内存有限，仅几百MB。
2）解决思路：
扫描一遍文件，看订单金额所处数据范围，比如1元-10万元，那么就分100个桶。
第一个桶存储金额1-1000元之内的订单，第二个桶存1001-2000元之内的订单，依次类推。
每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。
将100个小文件依次放入内存并用快排排序。
所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。
3）注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。
计数排序
基本原理
1）计数其实就是桶排序的一种特殊情况。
2）当要排序的n个数据所处范围并不大时，比如最大值为k，则分成k个桶
3）每个桶内的数据值都是相同的，就省掉了桶内排序的时间。
代码实现
void countSort(int *arr, int size) {
int max = 0;
for (int i = 0; i < size; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int *count = (int *)malloc(sizeof(int) * (max + 1));
memset(count, 0, sizeof(int) * (max + 1));
for (int i = 0; i < size; i++) {
count[arr[i]]++;
}
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
int *res = (int *)malloc(sizeof(int) * size);
for (int i = size - 1; i >= 0; i--) {
res[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
memcpy(arr, res, sizeof(int) * size);
free(res);
free(count);
}
案例分析
假设只有8个考生分数在0-5分之间，成绩存于数组A[8] = [2，5，3，0，2，3，0，3]。
使用大小为6的数组C[6]表示桶，下标对应分数，即0，1，2，3，4，5。
C[6]存储的是考生人数，只需遍历一边考生分数，就可以得到C[6] = [2，0，2，3，0，1]。
对C[6]数组顺序求和则C[6]=[2，2，4，7，7，8]，c[k]存储的是小于等于分数k的考生个数。
数组R[8] = [0，0，2，2，3，3，3，5]存储考生名次。那么如何得到R[8]的呢？
从后到前依次扫描数组A，比如扫描到3时，可以从数组C中取出下标为3的值7，也就是说，到目前为止，包括自己在内，分数小于等于3的考生有7个，也就是说3是数组R的第7个元素（也就是数组R中下标为6的位置）。当3放入数组R后，小于等于3的元素就剩下6个了，相应的C[3]要减1变成6。
以此类推，当扫描到第二个分数为3的考生时，就会把它放入数组R中第6个元素的位置（也就是下标为5的位置）。当扫描完数组A后，数组R内的数据就是按照分数从小到大排列的了。
使用条件
1）只能用在数据范围不大的场景中，若数据范围k比要排序的数据n大很多，就不适合用计数排序；
2）计数排序只能给非负整数排序，其他类型需要在不改变相对大小情况下，转换为非负整数；
3）比如如果考试成绩精确到小数后一位，就需要将所有分数乘以10，转换为整数。
基数排序
基本原理（以排序10万个手机号为例来说明）
1）比较两个手机号码a，b的大小，如果在前面几位中a已经比b大了，那后面几位就不用看了。
2）借助稳定排序算法的思想，可以先按照最后一位来排序手机号码，然后再按照倒数第二位来重新排序，以此类推，最后按照第一个位重新排序。
3）经过11次排序后，手机号码就变为有序的了。
4）每次排序有序数据范围较小，可以使用桶排序或计数排序来完成。
代码实现
#define NUM_OF_POS(a,pval) ((a)/pval)%10
void radixSort(int *arr, int size, int numCount) {
int *pres = (int *)malloc(sizeof(int) * size);
int index = 0;
int breakFlag = 0;
int count[10] = {0};
for (int i = 0; i < numCount; i++) {
memset(count, 0, sizeof(int) * 10);
//求当前的基数
int pval = pow(10, i);
//计数
for (int j = 0; j < size; j++) {
index = NUM_OF_POS(arr[j], pval);
count[index]++;
}
//小的优化，可能位数最大的就1，其他的位数差很多
if (count[0] == 9) {
breakFlag++;
}
if (breakFlag >= 2) {
break;
}
//累加
for (int j = 1; j < 10; j++) {
count[j] += count[j - 1];
}
//排序必须从后往前，否则不是稳定排序
for (int j = size - 1; j >= 0; j--) {
index = NUM_OF_POS(arr[j], pval);
pres[count[index] - 1] = arr[j];
count[index]--;
}
//本轮排序好的，拷贝到a中
memcpy(arr, pres, sizeof(int) * size);
}
}
使用条件
1）要求数据可以分割独立的“位”来比较；
2）位之间由递进关系，如果a数据的高位比b数据大，那么剩下的地位就不用比较了；
3）每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到O(n)。
通用排序函数实现技巧
- 数据量不大时，可以采取用时间换空间的思路。
- 数据量大时，优化快排分区点的选择。
- 防止堆栈溢出，可以选择在堆上手动模拟调用栈解决。
- 在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序。
- 用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致。