排序算法

排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
直接插入排序	有序：$O(n)$	$O(n^2)$	逆序：$O(n^2)$	$O(1)$	稳定
希尔排序	复杂度未得到证明	$O(n^{1.3-2})$	d=1：$O(n^2)$	$O(1)$	不稳定
冒泡排序	有序：$O(n)$	$O(n^2)$	逆序：$O(n^2)$	$O(1)$	稳定
快速排序	划分均匀：$O(nlog_2n)$	$O(nlog_2n)$	有序：$O(n^2)$	$O(log_2n\sim n)$	不稳定
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不稳定
归并排序			$O(nlog_2n)$	$O(n)$	稳定
基数排序			$O(d(r+n))$	$O(r)$	稳定

1 直接插入排序（Insertion Sort）

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

优化：先用折半查找找到应该插入的位置，再移动元素。

2 希尔排序（Shell Sort）

先将待排序表分割成若干形如$L[i,i+d,i+2d,...,i+kd]$的特殊子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。（希尔本人建议：d初始值为n，然后每次将增量缩小一半）

适用性：仅适用于顺序表，不适用于链表

3 冒泡排序（Bubble Sort）

冒泡排序是一种交换排序，它的思路就是在待排序的数据中，两两比较相邻元素的大小，看是否满足大小顺序的要求，如果满足则不动，如果不满足则让它们互换。然后继续与下一个相邻元素的比较，一直到一次遍历完成。一次遍历的过程就被成为一次冒泡，一次冒泡的结束至少会让一个元素移动到了正确的位置。所以要想让所有元素都排序好，一次冒泡还不行，我们得重复N次去冒泡，这样最终就完成了N个数据的排序过程。

对一个长度为 $n$ 的排列 $p[i]$ 进行一轮冒泡排序的伪代码如下：

for i = 1 to n-1:
	if p[i] > p[i + 1]:
		swap(p[i], p[i + 1])

4 快速排序（Quck Sort）

快速排序是一种交换排序，它的思路：在待排序表$L[1...n]$中任取一个元素 pivot 作为枢轴（或基准，通常取首元素），通过一趟排序表划分为独立的两部分$L[1...k-1]$和$L[k+1...n]$，使得$L[1...k-1]$中的所有元素小于 pivot，$L[k+1...n]$中的所有元素大于等于 pivot，则 pivot放在了其最终位置$L[k]$上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

若每一次选中的“枢轴”将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高。

优化：

1. 选头、中、尾、三个位置的元素，取中间值作为枢轴元素；
2. 随机选一个元素作为枢轴元素。

5 简单选择排序（Selection Sort）

选择排序：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。

适用性：既可以用于顺序表，也可用于链表

6 堆排序（Heap Sort）

堆排序是选择排序的一种，思路：每一趟将堆顶元素加入到有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素序列再次调整为大根堆（小元素不断下坠）

什么是堆？

若$n$个关键字序列$L[1..n]$满足下面某一条性质，则称为堆（Heap）：

1. 若满足：L(i)≥L(2i)且L(i)≥L(2i+1)，$(1 \leq i \leq n / 2)$——大根堆（大顶堆）
2. 若满足：L(i)≤L(2i)且L(i)≤L(2i+1)，$(1 \leq i \leq n / 2)$——小根堆（小顶堆）

建立大根堆：

1. 把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足则进行调整
2. 检查当前结点是否满足根节点>=左、右，若不满足，将当前结点与更大的一个孩子互换
3. 若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断“下坠”）

建堆$O(n)$，排序$O(nlogn)$

在堆中插入新元素：

1. 对于大根堆，新元素放到表尾，与父结点相比，若新元素比父节点更大，则将二者互换。新元素就这样一路上升，直到无法继续上升。

在堆中删除元素：

1. 被删除元素用堆底元素代替，然后让该元素不断下坠，直到无法下坠为止。

7 归并排序（Merge Sort）

把两个或多个已经有序的序列合并成一个。

核心操作：把数组内的两个有序序列归并为一个。

8 基数排序（Radix Sort）

假设长度为$n$的线性表中每个结点$a$的关键字由$d$元组$\left(k_{j}^{d-1}, k_{j}^{d-2}, k_{j}^{d-3}, \ldots, k_{j}^{1}, k_{j}^{0}\right)$组成，其中，$0 \leq k_{j}^{i} \leq r-1 \quad(0 \leq j<n, 0 \leq i \leq d-1)$，$r$称为基数。

基数排序得到递减序列的过程如下：

1. 初始化：设置$r$个空队列，Q_{r-1}，Q_{r-2}...Q_0
2. 按照各个关键字位权重递增的次序（个、十、百），对$d$个关键字位分别做“分配”和“收集”
3. 分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入$Q_x$队尾
4. 收集：把Q_{r-1}，Q_{r-2}...Q_0各个队列中的结点依次出队并链接

注意：

1. 基数排序不是基于比较的排序算法；基数排序通常基于链式存储实现。
2. 需要$r$个辅助队列，空间复杂度为$O(r)$，其中$r$为基数；
3. 一趟分配$O(n)$，一趟收集$O(r)$，总共$d$趟分配、收集，总的时间复杂度=$O(d(n+r))$

基数排序擅长解决的问题：

1. 数据元素的关键字可以方便地拆分成$d$组，且$d$较小；
2. 每组的关键字的取值范围不大，即$r$较小
3. 数据元素个数$n$较大

9 外部排序

外部排序原理：

外部排序：数据元素太多，无法一次全部读入内存进行排序。

使用归并排序的方法，最少只需在内存中分配3块大小的缓冲区即可对任意一个大文件进行排序。

步骤：

1. 构造初始归并段：归并排序要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘；
2. 第一趟归并：将两个归并段归并为一个，缓冲区1/2空了就要立即用归并段1/2的下一块补上
3. 第二趟归并：与第一趟类似…

时间开销分析：

1. 外部排序时间开销=读写外存时间+内部排序所需时间+内部归并所需时间

优化：

1. 多路归并：采用多路归并可以减少归并趟数，从而减少磁盘I/O(读写)次数
2. 减少初始归并段数量：生成初始归并段的“内存工作区”越大，初始归并段越长，则可减少初始归并段数量r

代码实现

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
 
int arr[maxn] = {0, 53, 17, 78, 9, 45, 65, 87, 32};//下标从1开始 
int n;//数组长度 

//直接插入排序
void insert_sort() {
	int i, j, tmp;
	for (i = 2; i <= n; i++) {
		tmp = arr[i];
		for (j = i - 1; j >= 1; j--) {
			if (arr[j] > tmp) {
				arr[j + 1] = arr[j];
			} else {
				break;
			}
		}
		arr[j + 1] = tmp;
	}
} 
//希尔排序
void shell_sort() {
	int i, j, tmp, d;
	for (d = n / 2; d >= 1; d /= 2) {//增量 
		for (i = 1 + d; i <= n; i++) {
			tmp = arr[i];
			for (j = i - d; j >= d; j -= d) {
				if (arr[j] > tmp) {
					arr[j + d] = arr[j];
				} else {
					break;
				}
			}
			arr[j + d] = tmp;
		}	
	} 
} 
//冒泡排序 
void bubble_sort() {
	for (int i = 1; i <= n - 1; i++) {
		bool flag = false;
		for (int j = 1; j <= n - i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
				flag = true;
			}
		}
		if (flag == false) {//无交换，表已经有序 
			break;
		}
	}
} 
//快速排序——用arr[low]将子表划分
int partition(int low, int high) {
	int pivot = arr[low];//第一个元素作为枢轴元素 
	while (low < high) {//用low、high搜索枢轴的最终位置 
		while (low < high && arr[high] >= pivot) {
			high--;
		} 
		arr[low] = arr[high];//比枢轴小的元素移动到左边 
		while (low < high && arr[low] <= pivot) {
			low++;
		} 
		arr[high] = arr[low];//比枢轴大的元素移动到左边 
	}
	arr[low] = pivot;//枢轴元素存放的最终位置
	return low;//返回存放枢轴的最终位置 
} 
//快速排序
void quck_sort(int low, int high) {
	if (low < high) {
		int pivot_pos = partition(low, high);
		quck_sort(low, pivot_pos - 1);
		quck_sort(pivot_pos + 1, high);
	} 
} 
//简单选择排序
void select_sort() {
	for (int i = 1; i <= n - 1; i++) {//进行n-1趟 
		int mini = i;//记录最小元素位置 
		for (int j = i + 1; j <= n; j++) {//在arr[i+1...n]中选择最小元素 
			if (arr[j] < arr[mini]) {
				mini = j;
			}
		}
		if (mini != i) {
			swap(arr[i], arr[mini]);
		}
	}
} 
//堆排序——将以 k 为根的子树调整为大根堆
void heap_adjust(int k, int len) {
	arr[0] = arr[k];//arr[0]暂存子树的根节点 
	for (int i = 2 * k; i <= len; i *= 2) {//沿key较大的子节点向下筛选 
		if (i < len && arr[i] < arr[i + 1]) {//比较左右孩子结点大小 
			i++;//取key较大的子节点下标 
		}
		if (arr[0] >= arr[i]) {//筛选结束 
			break;
		} else {
			arr[k] = arr[i];//将arr[i]调整到双亲结点上 
			k = i;//修改k，以便继续向下筛选 
		} 
	} 
	arr[k] = arr[0];//被筛选节点的值放入最终位置 
} 
//堆排序——建立大根堆
void build_max_heap(int len) {
	for (int i = len / 2; i > 0; i--) {//从后往前调整非终端结点 
		heap_adjust(i, len);
	}
} 
//堆排序
void heap_sort() {
	build_max_heap(n);
	for (int i = n; i > 1; i--) {
		swap(arr[i], arr[1]);
		heap_adjust(1, i - 1);
	}
} 

int *b = (int *)malloc(n * sizeof(int));//辅助数组 
//归并排序——arr[low...mid]与arr[mid+1...high]各自有序，将两者合并
void merge(int low, int mid, int high) {
	int i, j, k;
	for (k = low; k <= high; k++) {//将arr中所有元素复制到b 
		b[k] = arr[k];
	}
	//合并 
	for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
		if (b[i] < b[j]) {
			arr[k] = b[i++];
		} else {
			arr[k] = b[j++];
		}
	}
	//没有归并完的部分复制到尾部 
	while (i <= mid) arr[k++] = b[i++];
	while (j <= high) arr[k++] = b[j++]; 
} 
//归并排序
void merge_sort(int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;//从中间拆开 
		merge_sort(low, mid);//对左半部分归并排序 
		merge_sort(mid + 1, high);//对右半部分归并排序 
		merge(low, mid, high);//归并 
	}
} 

int main() {
//	cin>> n;
	n = 8;
	merge_sort(1, n);
	for (int i = 1; i <= n; i++) {
		cout<< arr[i]<< " ";
	}
	return 0;
}

练习