十大排序①：插入、选择和交换排序_直接插入排序和选择插入排序的区别

十大排序②：桶、计数与基数排序

插入排序

插入排序是一类排序，包括直接插入排序、折半插入排序和希尔排序。一般常说的插排就是直接插入排序。

插入排序的核心是有序区，即在排序区域首部的一些元素局部有序。

直接插入排序和选择排序都是逐个将无序区的元素放到有序区，但是元素的选取（以及对应安放策略）不一样。

直接插入排序的策略是选取无序区的第一个元素，由于最前面是有序区，所以就是最后一个局部有序元素后面那个被选取。然后拿这个从有序区最后一个元素开始向前比较找到合适的位置插入。

选择排序是选取无序区最值放到无序区最左边（也就是和有序区挨着的那个）作为新的有序区的元素，如果是选择最大的放到无序区最左边，则会使整个序列是从小到大排列的。

直接插入排序

直接插入排序代码如下：

#define DataType int
void insertSort(DataType* arr, int length){
	/*
		插排类似于摸牌，依旧是在数组左侧构建有序区域
		第i轮意味着下标小于i的局部有序
		每轮将第i个元素向前与局部有序区域内元素逐个至合适的位置插入 
		时间复杂度O(n^2) 空间复杂度为O(1) 稳定排序算法
	*/ 
	int i, j, temp;
	for(i = 1; i < length; i++){
		temp = arr[i];
		j = i - 1;
		for(; j >= 0 && temp < arr[j]; --j){
			// 待排序元素左侧大于它的右移
			arr[j + 1] = arr[j]; 
		}
		arr[j + 1] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

折半插入排序就是在直接插入排序的基础上，对有序区的遍历采用折半查找的思路。

折半插入排序

折半插入排序代码如下所示

#define DataType int
void binInsertSort(DataType* arr, int length){
	/*
		较之于直接插入排序，折半插排先查到插入位置 
		然后再对于插入位置右边的部分整体右移 
	*/ 
	int i, j, low, high, mid;
	DataType temp;
	for(i = 1; i < length; ++i){

		if(arr[i] < arr[i - 1]){
			temp = arr[i];
			low = 0;
			high = i - 1;
			while(low <= high){
				
				mid = (low + high) / 2;
				if(temp < arr[mid]){
					high = mid - 1;
				}
				else{
					low = mid + 1;
				}
			}
			for(j = i - 1; j >= high + 1; --j){
					arr[j + 1] = arr[j];
				}
			arr[high + 1] = temp;
		}
		
	}
}
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
30
31
32

希尔排序

随便看一篇讲十大排序的文章就会发现，希尔排序是其中一种，插入排序也是其中一种。可是为什么要把希尔排序放到插入排序底下说呢？

希尔排序本质上用的就是分组插入方法，该方法又称递减增量排序算法。

可以理解为是对插入排序的一种改进。

既然说是改进就得看插入排序有什么需要改进的地方：每次只能移动一位数据。

#define DataType int
void shellSort(DataType* arr, int length){
	int i, j, d;
	DataType temp;
	d = length / 2;
	while(d > 0){
		for(i = d; i < length; ++i){
			temp = arr[i];
			j = i - d;
			while(j >= 0 && temp < arr[j]){
				arr[j + d] = arr[j];
				j = j - d;
			}
			arr[j + d] = temp;
		}
		d = d / 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

选择排序

选择排序，关键在于选择二字。选择什么？当然是待排序元素中的极值

直接选择排序

#define DataType int
// Max比较策略
bool Max(DataType x, DataType y){
	return x>y?true:false;
} 

void selectSort(DataType* arr, int length, bool (*p)(DataType, DataType)){
	/*
		选择排序不断在数组首部构建有序区域
		第i轮对应着下标小于i的都有序
		每次将无序区域的最值放到arr[i]上
		n-1轮 每轮遍历所有元素 时间复杂度是O(N^2)
		空间复杂度是O(1) 不稳定排序算法 
	*/
	DataType temp;
	int minIndex;
	for(int i = 0; i < length; ++i){
		//i之前的都是有序的,i是即将有序的 
		minIndex = i;
		temp = arr[i];
		for(int j = i + 1; j < length; ++j){
			if(p(temp,arr[j])){
				//temp始终是最小的 
				temp = arr[j];
				minIndex = j;
			}
		}
		arr[minIndex] = arr[i];
		arr[i] = temp;
	}
}
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
30
31

平均时间复杂度$O(n^2)$，空间复杂度$O(1)$，不稳定排序算法。

堆排序

堆排序要从二叉堆说起。

二叉堆的细节详见另一篇文章[算法笔记]二叉堆

思路：不断删除二叉堆的根元素，按先后顺序被删元素组成的序列是有序的。

时间复杂度约为$O(nlogn)$

#include<iostream>
using namespace std;

int heap[2048];
int n = 0;

int left(int parent){
    return 2 * parent;
}
int right(int parent){
    return 2 * parent + 1;
}
int parent(int son){
    if (son <= 0){
    	return -1;
	}
    return (son - 1) / 2;
}
void up(int x) {
	while (x > 1 && heap[x] > heap[x / 2]) {
		swap(heap[x], heap[x / 2]);
		x /= 2;
	}
}
void down(int x) {
	while (x * 2 <= n) {
		int t = x * 2;
		if (t + 1 <= n && heap[t + 1] > heap[t]) t++;
		if (heap[t] <= heap[x]) break;
		std::swap(heap[x], heap[t]);
		x = t;
	}
}

void insertHeap(int key){
	n = n + 1;
	heap[n] = key;
	up(n);
}
void deleteHeap(){
	// 删除树根 
	swap(heap[1], heap[n]);
	n = n - 1;
	down(1);
}
void printHeap(){
	for(int i = 1; i <= n ; ++i){
		cout<<heap[i]<<" ";
	}
	cout<<endl;
}

void heapSort(int nn){
	int i = n;
	//清空堆
	while(i > 0){
		deleteHeap();
		--i;
	}
	// 打印整个排好的序列
	for(i = 1; i <= nn; ++i){
		cout<<heap[i]<<" ";
	}
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

由于我deleteHeap()本身实现就是把根元素index = 1放到index = n的位置然后实行n -=1，所以是不需要进一步再多加改动的，直接把整个堆清空就是有序的了。

交换排序

交换排序特征是两两比较待排序元素，若次序相反则交换。

冒泡排序

基础的冒泡排序如下

#define DataType int
void bubbleSort(DataType* arr, int n){
	int i, j;
	for(i = 0; i < n; ++i){
		for(j = n - 1; j > i; --j){
			if(arr[j] < arr[j - 1]){
				swap(arr[j], arr[j - 1]);
			}
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11

进一步地如果某趟扫描没有发生任何交换则可以判断全部有序。改进版如下：

#define DataType int
void bubbleSort(DataType* arr, int n){
	int i, j;
	bool sorted = false;
	for(i = 0; i < n; ++i){
		sorted = true;//假定已经有序 
		for(j = n - 1; j > i; --j){
			if(arr[j] < arr[j - 1]){
				swap(arr[j], arr[j - 1]);
				sorted = false;
			}
		}
		if(sorted){
			return;
		} 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度$O(n^2)$

属于就地排序算法，空间复杂度$O(1)$

是稳定排序

快速排序

快速排序是由从冒泡排序算法改进来的，结合了分治与递归的思想。

为了实现冒泡排序，你需要每轮有一个基准值，在下面的程序中暂把它叫做datum

你每轮需要做的是：将大于基准值的值放在一边，小于基准值的值放在另一边

多数快速排序算法里，基准值通常是当前处理序列的第一个值。但是显而易见的是，基准值的位置可能会变化。

如上图，快速排序第一轮之后，基准值3的位置发生了变动，并且左侧的值小于基准值3，右侧的值大于基准值3（虽然都无序）

基准值的值是不变的，但是基准值的位置是变化的。

接着上图继续看，很容易明白，每轮排序过后，该轮的基准值就已经不在需要变动了，因为它已经提前处于最终有序序列中它应该在的位置了。

然后下一步体现了递归思想，基准值会把整个序列划分成两部分，给这两部分分别做快速排序。这两部分做完后再下一次就是给四个序列（如果确实有四个需要做就做，毕竟上图中3左边的再经过一次就已经有序了）做快速排序。

整体思路清楚的情况下就是实现细节问题，也就是如何使基准值处在合适的位置，具体代码如下：

while(i<j&&a[j]>datum)--j;
	if(i<j)a[i++]=a[j];
while(i<j&&a[i]<datum)++i;
	if(i<j)a[j--]=a[i]; 
1
2
3
4

什么意思呢？就是说在指向左侧遍历的指针i和右侧遍历的指针j未相遇时，总是一轮一轮地进行两个操作（分别是两个while循环及它们各自后面那句）

1. 如果右侧指针j指向的值大于基准值datum，此时没啥要动的，j做自减操作向左移就行，直到与i相遇或者找到一个小于基准值的元素
2. 如果找到了这样一个元素，将它挪到空位上，一开始的空位是基准值拿走后的。随后的空位都是这样的元素挪走之后产生的。
3. 然后该向右移动左侧的i，直到和j相遇或者找到一个大于基准值的值
4. 如果找到了这样一个元素，将它挪到空位上，一开始的空位是基准值拿走后的。随后的空位都是这样的元素挪走之后产生的。

这样的操作最终会使i和j相遇，且此时空位就是相遇的位置，把基准值填入就行了。

void quickSort(DataType* a,int l,int r)
{
	if(l<r)//对输入的正确性进行检验，不能出现左侧序号大于右侧序号 
	{
		
		int i=l,j=r;//ij为查找器，不用lr是因为结尾需要lr的值递归 
		DataType datum=a[l];//datum保存基准值
		while(i<j)
		{
			while(i<j&&a[j]>datum)--j;//右起向左寻小于datum的数,结束条件是查找器i=j或者找到a[j]
			if(i<j)a[i++]=a[j];//当while因找到a[j]<datum时，值赋给左侧查找器的位置，此时右侧查找器有两种可能性：到i=j时保存datum，或左查找器找到a[i]>datum需要给右边
			while(i<j&&a[i]<datum)++i;
			if(i<j)a[j--]=a[i]; 
		}
		a[i]=datum;//结束条件必然是i==j，此时a[i]的数必然出现了两次，即上面两种可能性的第一种，然后本语句是datum在a[i]处 
		quickSort(a,l,i-1);//范围最左到datum前一位进行快排 
		quickSort(a,i+1,r); //datum后一位到范围最右进行快排 
	 } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

不难看出，形式参数l和r是排序的下标范围。

快速排序的时间复杂度是$O(nlo{g}_{2}n)$，空间复杂度为$O(lo{g}_{2}n)$。是不稳定的排序算法。

进一步还可以随机枢轴或者三路快排。

我觉得更详细的内容可以看这里，以及它底下的参考。