快速排序（交换范式）
// 一趟快排就是找到第一个元素的位置使得左边比它小右边比它大
int _quicksort(int *a, int low, int high) {
int mid_value = a[low];
while(low < high) {
while(low < high && a[high] >= mid_value) high--;
a[low] = a[high];
while(low < high && a[low] <= mid_value) low++;
a[high] = a[low];
}
a[low] = mid_value;
return low;
}
void quicksort(int *a, int low, int high) {
if (low < high) {
int mid = _quicksort(a, low, high);
quicksort(a, low, mid-1);
quicksort(a, mid+1, high);
}
}
冒泡排序（交换范式）
void bubblesort(int *a, int n) {
for (int i = 0; i < n - 1; i++) {
int flag = 0;
for (int j = n - 1; j > i; j--) {
if (a[j - 1] > a[j]) {
swap(a[j], a[j - 1]);
flag = 1;
}
}
if (!flag) return;
}
}
直接插入排序（插入范式）
从数组a的第二个元素开始往后迭代，找到一个值后插入到前面使整个数组有序。
void insertsort(int *a, int n) {
for (int i = 1; i < n; i++) {
int temp = a[i], j;
for (j = i - 1; j >= 0; j--) {
if (temp < a[j]) a[j + 1] = a[j];
else break;
}
a[j + 1] = temp;
}
}
选择排序（选择范式）
如果从小到大排，从索引0开始到结束，每一步选择后面最小的放在当前索引位置。
void selectsort(int *a, int n) {
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min_idx]) min_idx = j;
if (min_idx != i) swap(a[i], a[min_idx]);
}
}
希尔排序（插入范式）
举例一趟增量为3排序子过程：
第0步 15 9 7 8 20 -1 4
第1步 15 8 4 -> 4 8 5
第2步 9 20 -> 9 20
第3步 7 -1 -> -1 7
（每一步都用直接插入排序获取）
第一趟得到: 4 9 -1 8 20 7 5
在此基础上，希尔排序遵循如下过程：
从增量为n/2开始，逐趟增量减少一半进行上述操作，直到增量最终为1那一趟结束。
void shellsort(int *a, int n) {
const int reduce_factor = 2;
int gap = n / reduce_factor;
while (gap) {
for (int i = gap; i < n; i++) {
int temp = a[i], j;
for (j = i - gap; j >= 0; j -= gap) {
if (temp < a[j]) a[j + gap] = a[j];
else break;
}
a[j + gap] = temp;
}
gap /= reduce_factor;
}
}
堆排序（选择范式）
推排序把数组看作一颗完全二叉树，大根堆意思是这颗二叉树的任何父节点永远大于子节点。
完全二叉树就是数组的每个元素依次填入一个完整的二叉树。
建大根堆过程：
- 从最后一个非叶结点开始，自底向上调整每一个非叶节点（从右向左从下到上）
- 调整操作：如果当前节点比两个儿子都大无需调整，否则找到最大的那个儿子把值与自己交换，再调整那个儿子直到叶结点。
堆排序代码：
void heap_adjust(int *a, int i, int size) {
int lchild = 2 * i, rchild = 2 * i + 1;
if (i > size / 2) return; // leaf
int max_idx = i;
if (lchild <= size && a[lchild - 1] > a[max_idx - 1]) max_idx = lchild;
if (rchild <= size && a[rchild - 1] > a[max_idx - 1]) max_idx = rchild;
if (max_idx != i) {
swap(a[i - 1], a[max_idx - 1]);
heap_adjust(a, max_idx, size);
}
}
void heap_buildmax(int *a, int size) {
for (int i = size / 2; i >= 1; i--) heap_adjust(a, i, size);
}
void heap_sort(int *a, int n) {
heap_buildmax(a, n);
for (int i = n; i >= 2; i--) {
// 从后往前迭代，每次将堆顶输出到当前位置, 排序后为从小到大
swap(a[1 - 1], a[i - 1]);
heap_adjust(a, 1, i - 1);
}
}
归并排序
归并算法还是比较重要的，建议背一下，其功能是归并两个本来就有序的数组，使输出有序。
void merge(int *a, int low, int mid, int high, int *buffer) {
// a[low:mid] 与 a[mid+1:high] 各自有序, 现在要输出一个有序的a[low:high]
int i, j, k;
copy(a + low, a + high + 1, buffer + low);
for (i=low, j=mid+1, k=low; i<=mid && j<=high; k++) {
// i,j为两个有序数组的扫描指针, k为当前输出指针
if (buffer[i] <= buffer[j]) a[k] = buffer[i++];
else a[k] = buffer[j++];
}
while(i<=mid) a[k++] = buffer[i++];
while(j<=high) a[k++] = buffer[j++];
}
int *buffer = new int[n] // 需要开一个和输入一样大的数组
void mergesort(int *a, int low, int high) {
if (low<high) {
int mid = (low+high)/2;
mergesort(a, low, mid);
mergesort(a, mid+1, high);
merge(a, low, mid, high, buffer); //归并放最后，这个算法是自底向上的
}
}
基数排序
十进制基，优先低位基数排序过程：
- 建立10个桶
- 按照输入所有数最后一位（%10），放入这些桶（比如123就放入3号队列队尾）
- 从0~10将各个桶里的值输出
- 再按照倒数第二位放入桶（与2操作相似）
- 从0~10将各个桶里的值输出
- 一直继续直到最高位操作结束
int maxbit(int *a, int n, int radix) {
int res = -1;
for (int i = 0; i < n; i++) {
int p = a[i], c = 0;
while (p) {
c++;
p /= radix;
}
res = max(res, c);
}
return res;
}
const int radix = 10;
int radix_count[radix];
int radix_buffer[radix];
void radixsort(int *a, int n) {
int max_bit = maxbit(a, n, radix);
int r = 1;
for (int i = 0; i < max_bit; i++) {
memset(radix_count, 0, radix * sizeof(int));
for (int j = 0; j < n; j++)
radix_count[a[j] / r % radix]++; // 每个桶容纳数目
for (int j = 1; j < radix; j++) // 每个桶输出位置
radix_count[j] += radix_count[j - 1];
for (int j = n - 1; j >= 0; j--) {
int v = a[j] / r % radix;
radix_buffer[radix_count[v] - 1] = a[j];
radix_count[v]--;
}
memcpy(a, radix_buffer, radix * sizeof(int));
r *= radix;
}
}
排序算法特性表
| 算法 | 最好复杂度 | 平均复杂度 | 最坏复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | Y |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | Y |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | |
| 希尔排序 | O(1) | ||||
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | |
| 2路归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Y |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | Y |