1. 插入排序

（1）思想

• 将待排序的记录按关键字插入前面已排序的序列中。
  
• 注意：
  ①只有比前一个元素[i-1]小的关键字才需要移位。
  ②从后向前遍历排序号的序列，将大于当前关键字的元素后移，然后将关键字插入空出的位置。

void InsertSort(int A[], int n) {
	int i, j, temp;
	for(int i=1; i<n; i++) {
		temp = A[i];
		for(int j=i-1;j>=0 && A[j] >temp; j--) {
			A[j+1] = A[j];	// 元素后移
		}
		A[j+1] = temp; 
	}
}
1
2
3
4
5
6
7
8
9
10

（2）效率

• 时间复杂度：
  ①最好的情况：$O(1)$，原本有序的情况。
  ②最坏的情况：$O(n^2)$
• 空间复杂度：$O(n)$
• 算法稳定性：稳定

2. 希尔排序

（1）思想

• 将待排序表划分为步长为d的子表，对每个子表内进行插入排序。缩小长度d，重复上述步骤，直到d=1为止。

• 注意
  ①对于每个子表都采用插入排序，因此排序前需要比较$[i],[i-d]$的大小。仅当$a[i]<a[i-d]$时才需要对表内采取插入排序。
  ②数组元素A[0]作为暂存单元。

void ShellSort(int A[], int n) {
	int d, i, j;
	for(d =n/2;d >=1; d=d/2) {
		for(int i=d+1; i<=n; i++) {	// i =d+1保证了前d个元素可被查找
			// 开始插入排序
			if(A[i] <A[i-d]) {
				A[0] = A[i];
				for(int j=i-d;j >0 && A[0] <A[j]; j=j-d) {
					A[j+d] = A[j];
				}
				A[j+d] = A[0];
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2）算法性能

• 空间复杂度：O(1)
• 时间复杂度：
  ①最坏时间复杂度：$O(n^2)$
  ②当n在某个范围内，可达$O(n^{1.3})$
  因此希尔排序比直接插入排序还是要优秀不少。
• 算法稳定性：不稳定
  
• 适用性：仅适用于顺序表，不可采用链表。

---

希尔排序是对插入排序的优化。插入排序是对整个待排序数组，从头到尾将每个元素插入到前面有序的子数组中。希尔排序相对于插入排序而言，会先对步长为d的子数组进行排序。通过逐渐减小d值，最终实现对整个数组的插入排序。采用这样的方法，是为了避免插入排序最坏的情况，即原数组是按照降序排列的，对于每个元素都需要与已排序序列中所有元素比较。

3. 冒泡排序

（1）思想

• 每一趟排序从后往前两两比较，交换元素的值。最多需要执行n-1次，如果一轮中没有任何元素交换则算法结束。

void BubbleSort(int A[], int n) {
	for(int i=0; i <n-1; i++) {
		bool flag = false;
		for(int j=n-1; j>i; j--) {
			if(A[j-1] >A[j]) {
				swap(A[j], A[j-1]);
				flag = true;
			}
		}
		if(flag == true)
			return;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

（2）算法性能

• 空间复杂度：O(1)
• 时间复杂度：
  ①最好情况下：$O(n)$，带排序序列原本有序。
  ②最坏情况：$O(n^2)$，待排序序列原本逆序。
• 稳定性：稳定

4. 快速排序

（1）思想

• 选择第一个元素作为基准将待排序序列划分为两个部分，使得左边小于基准，右边大于基准。
• 对左右两个子表按照相同步骤划分，直至每个部分只有一个元素或空为止。

快速排序算法主要分为两个步骤：①获取基准值并使左边小于基准，右边大于基准。②递归

int Partition(int A[], int low, int high) {
	int pivot = A[low];	// 选择最左作为基准值
	while(low <high) {
		//1. 找到第一个右侧大于和左侧小于pivot的元素，并交换两个元素。
		while(low<high&&A[high] >pivot)
			high--;
		A[low] = A[high];
		while(low<high&&A[low] <pivot)
			low++;
		A[high] = A[low];
	}
	A[low] = pivot;
	return low;
}

void QuickSort(int A[], int low, int high) {
	if(low <high) {
		int pivotpos = Partition(A, low, high);
		QuickSort(A, low, pivotpos-1);
		QuickSort(A, pivotpos+1, high);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（2）算法效率

• 时间复杂度：$O(n\log n)$
  ①最好情况下：$O(n\log n)$
  ②最坏情况下：$O(n^2)$

• 空间复杂度：
  ①最好情况下：$O(\log n)$
  ②最坏情况下：$O(n)$
  

• 稳定性：不稳定。

当选择的基准元素将待排序序列划分为均匀的两个部分时，算法的运行效率更高。如果序列被划分为不均匀的两部分，则会导致递归深度增加，算法效率变低。
在实际运用中，快速排序更倾向于最好情况。因此这也是快排在众多排序算法中被运用最广泛的原因之一。

（3）优化

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

5. 选择排序

5.1 简单选择排序

（1）思想

• 每一轮选择待排序队列中最小元素加入有序序列队尾，需要循环n-1次。
  

void SelectSort(int A[], int n) {
	for(int i=0; i<n-1; i++) {
		int min = i;	// 最小位置
		// 1.寻找待排序序列中最小元素
		for(int j=i+1; j<n; j++) {
			if(A[j] <A[min])	
				min = j;
		}
		// 2. 将元素插入队尾
		if(min !=i)	
			swap(A[min], A[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

（2）算法性能

• 空间复杂度：$O(1)$
• 时间复杂度：$O(n^2)$
• 稳定性：不稳定。
  适用于顺序表，也可用于链表。

5.2 堆排序

（1）堆

• 大顶堆：$L(i)\ge L(2i)且L(i)\ge L(2i+1);$
  任何一个结点的值比它子节点的值大。
• 小顶堆：$L(i)\le L(2i)且L(i)\le L(2i+1);$
  任何一个结点的值比它子节点的值小。

• 建立大根堆：对所有$[n/2]$个非终端结点都检查一遍，是否满足大根堆的要求。
  ①先向上调整(n/2–>1)，在调整下坠(1–>n/2)。
  ①若不满足条件，则将比当前节点更大的孩子互换。
  
• 插入：新元素放到表尾，然后向上调整==“上升”==，直到无法继续上升为止。
• 删除：用堆底元素替代被删除元素，然后让该元素下坠，直到无法下坠为止。

（2）思想

• 建立大顶堆后获得了降序序列，每一轮将堆顶元素与待排序序列最后一个元素交换。再将待排序元素序列调整为大根堆（下坠）。

void HeapSort(int A[], int len) {
	BuildMaxHeap(A, len);	// 建立最大堆
	// 交换堆顶元素和最后一个元素，再对待排序序列调整为大根堆。
	for(int i=len; i>1; i++) {
		swap(A[i], A[1]);
		HeadAdjust(A, 1, i-1);	// "下坠"
	}
}
1
2
3
4
5
6
7
8

（3）算法性能

• 时间复杂度：$O(N\log N)$
  ①建堆时间复杂度：O(N)
  ②循环n次，最多需要比较交换的次数为2h.
• 空间复杂度：O(1)
• 稳定性：不稳定。
  
  

6. 归并排序

• 归并：将两个或多个已经有序的序列合并成一个。
  ①m归并，每选出一个元素需要对比关键字m-1次。
  

（1）思路

• 将待排序序列划分为两个部分，对两个分别进行归并排序。排序完成后，将两个有序序列合并。
• 合并：需要一个辅助数组B（拷贝A），通过两个指针i, j指示两部分当前合并的位置。通过比较B中两部分的数值，对A进行排序。

void Merge(int A[], int low, int mid, int high) {
	int i, j, k;
	// 复制
	for(k =low; k<=high; k++)
		B[k] = A[k];
	// 范围内比较
	for(i =low, j=mid+1, k =i;i <=mid&&j <=high;k++) {
		if(B[i] <=B[j])
			A[k] = B[i++];
		else 
			A[k] = B[j++];
	}
	// 多余部分
	while(i <=mid)
		A[k++] = B[i++];
	while(j <=high)
		A[k++] = B[j++];
}

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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

（3）算法性能

• 时间复杂度：$O(n{\log }_{2}n)$
  ①归并趟数${\log }_{2}n$次。
  ②每趟时间复杂度为$O(n);$
• 空间复杂度：$O(n)$
  ①空间复杂度主要来自于辅助数组，递归带来的空间复杂度可以忽略不记。
• 稳定性：稳定。

7. 基数排序

（1）思想
基数排序不是基于比较的排序算法。

• 初始化：设置r个空队列。
• 按照关键字位权重递增的次序，对关键字位分别做分配和收集。
• 分配：顺序扫描，若当前关键字位=x，则将元素插入Qx队尾。
• 收集：把队列Q_r-1~Q0各队列的结点依次出队并链接。
• 第一趟得到按个位递减排序的序列。
• 第二趟以十位进行分配，获得按照十位递减的排序序列。
• 第三趟以百位进行分配，获得按照百位递减的排序序列。
  ①若百位相同则按十位递减，若十位相同则按个位递减。
  

（2）算法性能

• 空间复杂度：$O(r)$
• 时间复杂度：$O(d(n+r))$
  共进行d趟分配和收集，一趟分配$O(n)$，收集$O(r)$。
• 稳定性：稳定。