# 排序

# 0、前言

我们常用的排序算法有十种。
通常分为以下两类：
- 比较类排序： 通过比较来决定元素间的次序，时间复杂度为 O (nlogn)~O ( $n^2$ )。
- 非比较类排序： 不通过比较来决定元素间的相对次序，时间复杂度可以突破 O (nlogn)，以线性时间运行。
排序算法的稳定性:
排序算法的稳定性是指在排序过程中，如果两个元素相等，它们在排序前后的相对位置是否保持不变。稳定的排序算法可以保证相等元素的相对顺序不变，而不稳定的排序算法则可能会改变相等元素的相对顺序。

说明
以下讲解排序时，目的都是为了从左往右越来越大。

# 1. 冒泡排序

指越小的元素会经由交换慢慢 “浮” 到数列的顶端。

# 1.1 描述

从左到右依次比较相邻元素大小，更大的元素交换到右边。
从最左边走到最右边的过程中，是一定能找到一个最大数的。
多轮重复从左到右，而前一轮所排出来的数不参与比较，所以需要记录经过了几轮。
根据上述规则，每一轮结束都会减少一个元素参与比较（即已排好序），直到未排序的元素个数为 $0$ 。

# 1.2 动图演示

# 1.3 代码实现

	void init(){
	for(int i=1;i<=n;i++){
	for(int j=1;j<=n-i+1;j++){
	if(a[j]>a[j+1]){
	swap(a[j],a[j+1]);
	}
	}
	}
	}

# 1.4 算法分析

冒泡排序属于交换排序，稳定性取决于代码怎么写，复杂度为 $O(n^2)$ , 空间复杂度为 $O(1)$ 。
复杂度最差为 $O(n^2)$ ，最好为 $O(n)$
最好的时需要记录当前元素有没有被移动过，没有被移动过，说明在此之前的都是已经排序好的（已经是正序了）, 那就没有必要从头再来。
** 注意：** 用记录的做法，虽然最优复杂度是 O (n), 但只能说该代码的最优是 O (n), 最差仍是 O (n^{2)，但不写记录的做法，对于任何数据都是 O (n}2) 的复杂度。

	void init(){
	bool flag;
	for(int i=1;i<=n;i++){
	flag=false;
	for(int j=1;j<=n-i+1;j++){
	if(a[j]>a[j+1]){
	swap(a[j],a[j+1]);
	flag=true;
	}
	}
	if(!flag){
	return;
	}
	}
	}

# 2. 选择排序

总共执行 n 轮，每次找到剩下数中最小的那一个数，并放在第 i 位（第 i 轮时）。

# 2.1 描述

对于第一个在未排序序列中找到最小（大）的元素，存放到排序序列中起始位置，即第一位。
对于第 $i$ 次在未排序序列中找到最小（大）的元素，存放到排序序列的第 $i$ 个位置。

# 2.2 动图演示

# 2.3 代码实现

	void init(){
	for(int i=1;i<=n;i++){
	int x=0x3fffffff,y=0;
	for(int j=i;j<=n;j++){
	if(a[j]<x){
	y=j;
	x=a[j];
	}
	}
	if(y==0){
	continue;
	}
	swap(a[i],a[y]);
	}
	}

# 2.4 算法分析

选择排序是一个 不稳定排序 （代码书写不得当的时候？）。
缺点：算法复杂度固定为 $O(n^2)$ 复杂度太高。
优点：不会占用额外的内存空间。
一般来说，算法计算都不会考选择排序（~~这其实就是个暴力算法感觉~~）。

# 3. 插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

# 3.1 算法描述

在一开始，将第一个元素当作一个有序数列，其他元素当作无序数列。
将扫描到的每个元素与有序序列的每个元素进行比较，小于哪个有序序列的元素就进行交换，相当于插入到该元素索引位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

# 3.2 动图演示

# 3.3 代码实现

	for(int i=2;i<=n;i++){
	int num=a[i];
	for(int j=i-1;j>=0;j--){
	if(a[j]<=a[i]){
	for(int k=i;k>j+1;k--){
	a[k]=a[k-1];
	}
	a[j+1]=num;
	break;
	}
	}
	}

# 3.4 算法分析

好处：

只需要额外的一个单位的空间大小.
在小规模数据或部分有序的数据上，插入排序的性能可能相对较好。此外，插入排序的实现非常简单，代码易于理解和编写。

坏处：可以被一些数据卡成 $O(n^2)$ 的复杂度。

# 4. 希尔排序

希尔排序是将数据分组，将每一组进行插入排序。
每一组排成有序后，最后整体就变有序了。
希尔排序又叫缩小增量排序。

# 4.1 算法描述

确定一个分组 $gap$ ，每隔 $gap$ 个的数为一组，例如 $gap=3$ 则 1 和 4 是一组。
在一个组内的，使用插入排序使其有序。
按增量序列个数 $gap$ ，对序列进行 $gap$ 趟排序。

# 4.2 动图演示

# 4.3 代码实现

	for(int i=n/2;i>0;i/=2){
	int gap=i;
	for(int j=gap;j<=n;j++){
	int tmp=a[i];
	int k=j;
	while(k-gap>=1&&tmp<a[k-gap]){
	a[k]=a[k-gap];
	k-=gap;
	}
	a[k]=tmp;
	}
	}

# 4.4 算法分析

希尔排序算法减少了移动元素和比较元素大小的次数，从而提高了排序效率。
虽然可能还是被卡成插入排序的复杂度，但是肯定要比插入排序要优的。

# 5. 归并排序

采用分治的思想，进行排序。

# 5.1 算法描述