八大排序详解

一.插入排序

1.代码思路

我们在生活中打扑克时，是一张牌一张牌地摸的，当我们每摸一张牌就插入到前面已经排好序的牌中，摸牌之后整副牌就是有序的了。插入排序也是这个思路：假设现在任意给我们一个拥有6个元素的整型数组，我们可以先把0号元素看成是有序的，把1号元素往前面插入，那么0号到1号元素就是有序的了，接着把2号元素也往前插入，以此类推，等5号元素也往前插入后整个数组便是有序的了。

2.代码实现

void InsertSort(int* a, int n)
{
	int cur = 1;
	while (cur < n)
	{
		int pos = cur-1;
		int key = a[cur];//记录当前要进行插入的数
		while (pos >= 0)
		{
			if (a[pos] > key)
			{
				a[pos + 1] = a[pos];//数据后移
			}
			else
			{
				break;
			}
			--pos;
		}
		a[pos + 1] = key;//将本轮要前插的数据移动到相应位置
		++cur;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

有的人对直接插入排序进行了优化，在把数据往前插入时，既然前面的数据已经有序了，我们就可以使用二分查找寻找要插入的位置，这提高了查找的效率，但数据移动的次数还是没有变，这就是所谓的折半插入排序，这里不过多赘述。

3.复杂度分析

空间复杂度:O(1)
时间复杂度O(n^2)
最坏情况下，第1个数据插入要移动0次，第2个要移动1次…第n个要移动n-1次，累加起来，最坏情况下时间复杂度就是O(n^2)

4.稳定性分析

由于我们在控制移动时，只有要前插的数据小于他前面的数据时（假设我们现在要排升序），我们才移动数据，大于和等于均不移动，故排序是稳定的。我们也可以看出当数据集合越接近有序，排序的效率就越高（并不是所有的排序越接近有序效率就越高）。

二.希尔排序

1.代码思路

既然我们知道进行直接插入排序排序时，数据集合越有序排序的效率就越高，那我们先对数据进行与排序，最后再进行一次直接插入排序。
假设现在我们有一个10个数据的数据，我们可以先把间隔为5的作为一组数据进行插入排序，即把（0,5）、（1,6）、（2,7）、（3,8）、（4,9）这五组数据分布进行一次插入排序，接着把间隔为3的数据作为一组数据，即（0,3,6,9）、（1,4,7）、（2,5,8）这3组数据进行一次插入排序，最后再把间隔为1的数据进行一次插入排序(即对整个数据进行一次插入排序)，那么整个数据集合便是有序的了。注意：最后一次插入排序时数据间隔必须为1.
现在我们要考虑的就是这个间隔应该怎么取值比较合适呢？
现在较多人使用的方法是先让gap=n(数组长度)，接着让每趟排序的gap=gap/3+1。

2.代码实现

void ShellSort(int* a, int n)
{
	int gap = n;
	int i = 0;
	int j = 0;
	while (gap > 1)//进行多趟，直至gap为1
	{
		gap = gap / 3 + 1;
		for (i = 0; i < gap; ++i)
		{

			//进行直接插入排序
			for (j = i; j < n; j += gap)
			{
				int key = a[j];
				int pos = j - gap;
				while (pos >= i)
				{
					if (a[pos] > key)
					{
						a[pos + gap] = a[pos];
					}
					else
					{
						break;
					}
					pos -= gap;
				}
				a[pos + gap] = key;
			}
		}
	}
}
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

3.复杂度分析

空间复杂度:O(1)
时间复杂度O(n^1.25)到
O(1.6n^1.25)
希尔排序的时间复杂度不好计算，不过其于O(NlogN)是一个量级的（实际上会比这个大一点）。

4.稳定性分析

属于不稳定排序

三.快速排序

1.代码思路

假设现在给我们一个整型数组，我们可以先在数组里面任意拿一个值value（一般都是找第一个），我们现在想达到这样一个效果：在数组里面找到一个位置把value放进去，同时value左边的值都比value小（我们现在要排升序），右边的值都比value大，那么value就一定放到了整个排序的正确位置上，接着又可以对value左边的数据和右边的数据分别进行以上操作，依此类推，直到要进行操作的数据个数小于等于1。

接下来就是要如何达到我们想要的效果了，我们可以用左右指针的方法（hoare版本），左指针指向数组最左边，右指针指向数组最右边，右指针指向的值如果大于等于value，就往左走，小于value就停下来，左指针指向的值如果小于等于value,就往右走，大于value就停下来，接着交换左右指针指向的值，直至左右指针相遇。注意：如果我们要排升序，一定要先让右指针先走，这样左右指针相遇的位置的值小于等于value（后面会说明）。交换value和左右指针相遇的位置的值，至此，我们想要的效果就达成了。
下面的动图借用了Kimi-zhang的文章里的动图作为演示：

说明：
相遇只有两种情况：左指针遇上右指针、右指针遇上左指针
①左指针遇上右指针：
因为是右指针先走，所以左指针往右走相遇位置遇到的值一定比value小
②右指针遇上左指针：
由于左指针上的值一定小于等于value，所以右指针往左走相遇位置遇到的值一定小于等于value

2.代码实现

int PartSort1(int* a, int left, int right)
{
	Swap(&a[left], &a[mid]);

	int key = a[left];
	int keypos = left;

	while (left < right)
	{
		while (left < right && a[right] >= key)//1
		{
			--right;
		}
		while (left < right && a[left] <= key)//2
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}
	Swap(&a[keypos], &a[left]);//先1后2，相遇点的值一定比key小

	return left;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int mid = PartSort1(a, left, right);
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid+1, right);
}
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

3.复杂度分析

空间复杂度:O(logN)
由于递归要调用栈帧，其深度一般为logN(当然了，如果数据特殊，如已经有序，那么栈的深度就为N)。
时间复杂度:N(logN)
函数一般要调用logN层，每层最坏情况下交换N次，故时间复杂度为O(NlogN)。当然了，如果数据是有序的，其时间复杂度就会达到O(N^2)，故快排适用于数据集合无序。

4.稳定性分析

不稳定排序

5.代码改进

由于我们每次都是取数组第一个元素将其分成左右两部分，故当数组有序时，总有一部分的元素个数为0，另一部分的元素个数为N-1,其空间和时间复杂度会大大增加，我们希望可以取到一个数，将数组平分为左右两部分，这样就算有序，其时间复杂度就会降到O(NlogN)，空间复杂度也会降到O(logN)。那我们可以在数组的左边，右边和中间位置各取一个值，将这3个值的中大小处于中间的数作为value，这样就把有序的情况优化掉了，对无序情况基本没什么影响。

//三数取中
int GetMid(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;

	if (a[left] < a[right])
	{
		if (a[mid] < a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
	else if (a[left] > a[right])
	{
		if (a[mid] < a[right])
		{
			return right;
		}
		else if (a[mid] > a[left])
		{
			return left;
		}
		else
		{
			return mid;
		}
	}

	return left;
}

//交换两个数
void Swap(int* num1, int* num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

// 1.快速排序hoare版本
int PartSort1(int* a, int left, int right)

{
	//利用三数取中极大优化原数集接近有序的情况
	int mid = GetMid(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = a[left];
	int keypos = left;

	while (left < right)
	{
		while (left < right && a[right] >= key)//1
		{
			--right;
		}
		while (left < right && a[left] <= key)//2
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}
	Swap(&a[keypos], &a[left]);//先1后2，相遇点的值一定比key小

	return left;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int mid = PartSort1(a, left, right);
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid+1, right);
}
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

前面所说的将划分的数组进行排序的部分都是hoare版本的，下面看看另外的版本
①挖坑法版本

int PartSort2(int* a, int left, int right)
{
	//利用三数取中极大优化原数集接近有序的情况
	int mid = GetMid(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = a[left];
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[left] = a[right];

		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[right] = a[left];
	}
	a[left] = key;

	return left;
}
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

②前后指针版本

int PartSort3(int* a, int left, int right)
{
	//利用三数取中极大优化原数集接近有序的情况
	int mid = GetMid(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = a[left];
	int pre = left;
	int cur = pre + 1;
	while (cur <= right)
	{
		if (a[cur] < key && ++pre != cur)
		{
			Swap(&a[pre], &a[cur]);
		}
		++cur;
	}
	Swap(&a[left], &a[pre]);

	return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这些版本的复杂度并无区别，只不过用不同的方式把数组分为左右两部分。

6.后续补充：三路划分

前面针对原数据集有序的情况，我们采取了三数取中的方法，但面对原数据集有大量重复元素时，快排的时间和空间复杂度又会大大增加（在原数据集全部是重复元素的极端情况下，时间复杂度:O(N^2),空间复杂度:O(N)），为此，人们提出了三路划分的方法，即把数据分为三部分（假设我们要排升序）：数组左边部分比key小，中间部分等于key，右边部分大于key，那我们下一趟进行快排时，只需对小于key和大于key的部分进行排序就可以了。因此当原数据集全是重复元素时，下一趟排序就不在进行了，也就优化了原数据集拥有大量重复元素的情况.
我们只需对PartSort函数进行改进就可以了，即对数组a操作时需要三个指针:
left:开始时指向数组a排序部分的最左边
cur:开始时等于left
right:开始时指向数组a排序部分的最右边
我们可以这样操作数组a目前要排序的部分：
①a[cur] ②a[cur]==key:++cur
③a[cur]>key:交换a[cur]和a[right]，同时–right
当cur>right后：数组a要排序的部分就分成了，left左边部分都比key小，right右边部分都比key大，left到right的部分都等于key。

四.归并排序

1.代码思路

现在我们有一个长度为15的整型数组，我们把数组从中间分开分成2部分，我们希望他左半部分和右半部分都是有序的，那我们只需要将这两半部分合并，那整个数组就是有序的了。既然这样，那我们又可以将左半部分和右半部分分别各再分割成2部分，如此一直进行下去，直至某一部分只剩一个元素，我们可以认为单个元素是有序的，之后就是两两归并，那整个数组便是有序的了。

现在问题在于归并时怎么归并，如果在原数组归并，其时间复杂度就会比较大（至少比O(N)大），但如果我们使用一个临时数组，采用合并有序表的思路，将数据不断加入到临时数组里面，最后再把数据拷贝会原数组，那时间复杂度就会降到O(N)。

2.代码实现

void PartMergeSort(int* a, int* temp, int begin,int end)
{
	if (end <= begin)
	{
		return;
	}

	//分治
	int mid = begin + (end - begin) / 2;
	PartMergeSort(a, temp, begin, mid);
	PartMergeSort(a, temp, mid+1, end);

	//归并
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int pos = 0;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			temp[pos++] = a[begin1++];
		}
		else
		{
			temp[pos++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		temp[pos++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[pos++] = a[begin2++];
	}
	memcpy(a + begin, temp, pos*sizeof(int));
}

void MergeSort(int* a, int n)
{
	int* temp = (int*)malloc(n * sizeof(int));
	if (NULL == temp)
	{
		perror("malloc");
		exit(0);
	}

	PartMergeSort(a, temp, 0, n - 1);

}
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

3.复杂度分析

空间复杂度：O(N)
由于开辟了一个大小为N数组
时间复杂度：O(NlogN)

无论原数组是有序还是无序，其复杂度都不变，故当原数据集接近有序时，可以先考虑别的排序。

4.稳定性分析

由于在归并时，如果两数相等，我们可以控制其先让左边的数据入临时数据，故归并排序是稳定的。

五.堆排序

关于堆排序本人已经写过一篇详细的博客堆排序

1.复杂度分析

故堆排序
时间复杂度为为O(NlogN)
空间复杂度为O(1)

2.稳定性分析

不稳定排序

六.计数排序

1.代码思路

假如我们现在有一个数组a[3,2,2,2,1,1,1,3,3,5,6,7,5,6]，我们想要对其排序，我们可以定义一个大小为6数组b，遍历数组a，将a中的值作为b数组的下标并在该位置上加1，遍历完数组a后，再遍历数组b，如果该位置的值非零则将该位置的下标作为值放入a中，直至b数组在该位置的值为0。
由于a数组的最小值可能会比较大，我们可以找到数组a的最大值max和最小值min，开辟大小为max-min大小的数组b。

由此我们可以知道计数排序只适用于数据比较集中的非负整数排序

2.代码实现

// 计数排序
void CountSort(int* a, int n)
{
	int maxNum = a[0];
	int minNum = a[0];
	int i = n;

	//寻找最大值和最小值
	while (i--)
	{
		if (a[i] > maxNum)
		{
			maxNum = a[i];
		}
		else if (a[i] < minNum)
		{
			minNum = a[i];
		}
	}

	int size = maxNum - minNum + 1;
	int* temp = (int*)malloc(size * sizeof(int));
	if (NULL == temp)
	{
		perror("mallloc");
		exit(-1);
	}
	memset(temp,0, size * sizeof(int));
	//计数
	i = n;
	while (i--)
	{
		temp[a[i] - minNum]++;
	}

	//排序
	int pos = 0;
	for (i = 0; i < size; i++)
	{
		while (temp[i]--)
		{
			a[pos++] = i + minNum;
		}
	}

	free(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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

3.复杂度分析

假设数组最大值和最小值之差为K
空间复杂度:O(K)
时间复杂度:O(N+K)
遍历a数组花去N,遍历b数组花去K

4.稳定性分析

计数排序属于稳定排序，具体可见计数排序

七.冒泡排序

1.代码思路

假如现在我们要对一个数组排升序，我们可以让一个指针指向数组首元素，前后比较，将大的往后面交换，接着指针后移，遍历完数组后，最大值就到数组末尾去了，接着再将指针指向数组首元素，重复上述操作N-1次就完成排序了。

2.代码实现

void BubbleSort(int* a, int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n; ++i)
	{
		int flag = 0;
		for (j = 0; j+1 < n - i; ++j)
		{
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = 1;
			}
		}
		if (!flag)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.复杂度分析

空间复杂度:O(1)
时间复杂度:O(N^2)
属于稳定排序

这个排序几乎没什么用，唯一的用途就是用于学排序的新手教学。

八.选择排序

1.代码思路

先遍历一遍数组，找到最小值，然后与数组第一个元素交换，接着再从剩下的元素里找最小值，与数组第二个元素交换，直至剩下的元素个数为1，一个升序数组就完成了。

2.代码实现

void SelectSort(int* a, int n)
{
	int i = 0;
	int j = 0;
	
	for (i = 0; i < n; ++i)
	{
		int minPos = i;
		for (j = i; j < n; ++j)
		{
			if (a[j] < a[minPos])
			{
				a[minPos] = a[j];
			}
		}
		int temp = a[i];
		a[i] = a[minPos];
		a[minPos] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.复杂度分析

空间复杂度:O(1)
时间复杂度:O(N^2)
属于稳定排序

这个排序几乎没什么用，新手教学也很少用

九.总结

下面给出常见排序的复杂度和稳定性表格：

如果本文有什么不对的，恳请指正。编写不易，如若本文对读者有所帮助，点个赞给博主充充电吧！