【数据结构】一篇文章带你学会八大排序

一、排序的概念

1. 排序的使用：

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

2. 稳定性：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的;否则称为不稳定的。
简而言之，两个相同的数，例如下图，排完序后黑9仍然相对于在红9的前面，则算稳定。

3. 内部排序：

数据元素全部放在内存中的排序。

4. 外部排序︰

数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

5. 排序的用途：

排序作为数据结构中很重要的一环，在生活中被普遍的使用。
5.1 例如某东在售卖商品时，都会有按综合排序、按销量排序等都会有排序的身影

5.2 例如在壁纸软件某paper中也有最热门、评分最高等中也有排序的身影

二、排序的原理及实现

1. 插入排序

1.1 直接插入排序

1.1.1 直接插入排序在现实中的应用

相信大家都玩过牌，在摸牌阶段，每摸一张牌都从后往前依次比较，若摸起来的这张牌比比较的这张牌小，则继续向前比较，直到遇到比它小的那张牌，则将摸起来的那张牌放在它的后面，若没有比摸起来的这张牌小的，则将这张牌放在最前面。而直接插入排序与摸牌的思想相同。

---

1.1.2 直接插入排序的思想及个人理解

直接插入排序的思想：当插入第i(i>=1)个元素时，前面的array[0],array[1]…array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2]…的排序码顺序进行比较，找到插入位置即将array[i]插入.原来位置上的元素顺序后移。

我个人理解为是：将待排序的数据依次与前面有序的数组比较，直到形成一个新的有序数组。

---

1.1.3 直接插入排序的排序过程及代码实现

a. 静态排序过程

b. 动态排序过程

c. 代码实现

#include <stdio.h>

void InsertSort(int* arr , int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];      //tmp 记录需要插入的值
		while (end >= 0)
		{
			if (arr[end] > tmp)      //如果arr[end] > tmp 则 arr[end] 向后移动一位
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else					 //如果arr[end] <= tmp ,则将tmp放到 arr[end] 的后面
			{
				break;
			}
		}							 //如果需要插入的数是最小的时候，是特殊情况需要放在第一位
		arr[end + 1] = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意：
这里有一个很巧妙的设计，上述代码只分了两种情况，而一般情况下的想法是将比较分为三种情况：
⑴待排序数从后往前与有序数列比较时较小，被比较数向后移动，待排序数向前继续比较
⑵待排序数从后往前与有序数列比较时较大或者相等时，待排序数放在比较数后面
⑶待排序数比有序数列中的任何一个数据都要小时，无法继续比较(待排序数已经到了数组首元素位置，继续比较的数无意义且已经越界)，放在有序数列的第一个位置上

而这里则将( 2 )( 3 )两种情况合并为一种，详细来说就是，( 2 )( 3 )两种情况都是需要赋值的，而按照第一种情况的相反方向列为赋值情况，那么待排序数就到了正确的位置，赋值并跳出循环，但循环有两种停止情况，①不满足循环条件（待排序是比有序数组中的每一位都小） ② 待排序数放在正确的位置，而我们并不能确定是上面两种情况的哪一种，所以要判断待排序数是否是不满足循环条件，将其赋值到有序数组的首元素位置。上述情况则为下面的代码。

两种代码都可行，并无本质上的区别。

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

1.1.4 直接插入排序的复杂度计算

1.1.5 直接插入排序的总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度:O(n^2)
3. 空间复杂度:O(1)，它是一种稳定的排序算法
4. 稳定性:稳定

---

1.2 希尔排序（缩小增量排序）

1.2.1 希尔排序的由来

希尔排序的定义是:希尔排序(Shell Sort)也称为缩小增量排序,是插入排序的一种。它是英国数学家唐纳德·希尔(Donald Shell) 在1959 年提出的。

1.2.2 希尔排序的排序思想

希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件刚好被分成一组,算法便终止。

简单来说,希尔排序的工作原理是:

1. 按照一个增量 gap ,将记录分组。所有距离为 gap 的倍数的记录放在同一组。
2. 对每组使用直接插入排序算法对该组进行排序。
3. 持续减少增量 gap 的值,重复第一和第二步,直到 gap = 1 时,整个序列变为一个组,算法终止。

所以,希尔排序是一种基于插入排序的分组排序算法,它通过增量的逐步缩小来达到平均趋近 O(n*logn) 的效率。

1.2.3 希尔排序的排序过程及代码实现

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
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

1.2.4 希尔排序的复杂度

• 《数据结构(C语言版)》— 严蔚敏
  
• 《数据结构-用面相对象方法与C++描述》— 殷人昆
  

---

1.2.5 希尔排序的总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
   会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。
4. 稳定性：不稳定

---

2. 选择排序

2.1 直接选择排序

2.1.1 直接选择排序的基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

2.1.2 直接选择排序过程及代码实现

上面的动态图显示的是一次选择一个最小/最大的值进行交换，下面我写的的代码是直接选择排序的优化版本，一次挑出最大和最小的分别与最右边与最左边进行交换。

// 选择排序
void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;
	while (left <= right)
	{
		// 记录最大值和最小值的位置
		int maxi = left;
		int mini = left;
		for (int i = left; i <= right; i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		// 将最小的换到左边，最大的换到右边
		Swap(&a[left], &a[mini]);
		// 这里是为了解决最大的值在最左边时，左边与最小值交换
		// 导致最大值的位置被改变，下面交换交换时会出现问题
		// 下面的图中展示可能出现的情况
		if (left == maxi)
			maxi = mini;

		Swap(&a[maxi], &a[right]);

		left++;
		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

2.1.3 直接选择排序的时间复杂度

2.1.4 直接选择排序的总结

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(n^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

---

2.2 堆排序

堆排序这里不过多解释了，详细讲解在我写的这篇文章有详细的讲解。【数据结构】非线性结构之树结构(含堆)

---

3. 交换排序

3.1 冒泡排序

3.1.1 冒泡排序的基本思想

1. 比较相邻的元素,如果第一个比第二个大,就交换它们两个
2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素会是最大的数
3. 针对所有的元素重复以上的步骤,除了最后一个元素之外的所有元素都已被排序
4. 继续采用相同的方法对剩余未排序元素重复排序,直到所有元素有序为止

注意： 冒泡排序能够优化，定义一个变量，用来记录排序过程是否有数据交换操作，如果没有交换操作，那么这次排序就已经完成。

3.1.2 冒泡排序的排序过程及代码实现

void BubbleSort(int* arr, int N)
{
	int i = 0;
	for (i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < N - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.1.3 冒泡排序的时间复杂度

3.1.4 冒泡排序的总结

1. 冒泡排序是—种非常容易理解的排序
2. 时间复杂度:O(n^2)
3. 空间复杂度:O(1)
4. 稳定性:稳定

---

3.2 快速排序

3.2.1 快速排序的基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为:任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

3.2.2 快速排序的排序过程及代码实现（三种版本+非递归版本）

多种快速排序的实现共用Swap()函数
1

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
1
2
3
4
5
6

3.2.2.1 hoare版本

hoare版本的思想是在待排序的数组中选取一边的元素作为关键字，例如这里使用左边的元素作为关键字，使用一个变量keyi记录关键字的下标，再使用两个下标分别记录关键字左边的一个元素（left）和数组的最后一个元素（right）,left从左向右寻找比关键字大的元素，right从右向左寻找比关键字小的元素，找到后让两个下标对应位置上的两个元素交换，然后两个下标继续上面的操作继续寻找，直到两个下标相等后，keyi指向的元素（关键字）与当前下标上的元素交换，则完成了当前关键字左边的元素比关键字小，关键字右边的元素比关键字大，那么则完成了第一次排序。

记录交换后关键字的下标，将关键字左边和右边分割成为两个待排序区间，重复上面第一次排序的操作继续将剩下的待排序区间进行排序，直到区间不存在或者是区间内只有一个元素 ，那么当前区间不可继续分割，则这次排序才算结束。当所有的区待排序区间都不存在或是只有一个元素时，那么所有的元素就到了它应该在的位置，则排序完成。

int PartSort1(int* a, int left, int right)
{
	int keyi = left;

	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);

	return right;
}

void QuickSort(int* a, int left, int right)
{
	int keyi = PartSort1(a, left, right);
	//[left , keyi - 1] [keyi] [keyi + 1 , right]
	if (keyi - 1 > left)
	{
		QuickSort(a, left, keyi - 1);
	}
	if (right > keyi + 1)
	{
		QuickSort(a, keyi + 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

3.2.2.2 挖坑法

挖坑法的思想是在待排序数组中的选取一边的下标作为坑位且坑位指向的元素为关键字，例如这里使用左边的元素作为关键字，使用一个变量keyi记录坑位的下标，再使用两个下标分别记录关键字左边的一个元素（left）和数组的最后一个元素（right）,先使right从右向左寻找比关键字小的元素，找到后将right指向的元素赋值给keyi（坑位）指向的元素，将当前right值赋值给keyi形成新坑位，再使left从左向右寻找比关键字大的元素，找到后将当left指向的元素赋值给keyi（坑位）指向的元素，将当前right值赋值给keyi形成新坑位。重复以上操作，直到两个下标相遇后，将keyi指向的元素（关键字）赋值给最后的坑位，则完成了当前关键字左边的元素比关键字小，关键字右边的元素比关键字大，那么则完成了第一次排序。

记录交换后关键字的下标，将关键字左边和右边分割成为两个待排序区间，重复上面第一次排序的操作继续将剩下的待排序区间进行排序，直到区间不存在或者是区间内只有一个元素 ，那么当前区间不可继续分割，则这次排序才算结束。当所有的区待排序区间都不存在或是只有一个元素时，那么所有的元素就到了它应该在的位置，则排序完成。

int PartSort2(int* a, int left, int right)
{
	int keyi = left;

	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[right] = key;

	return left;
}

void QuickSort(int* a, int left, int right)
{
	int keyi = PartSort2(a, left, right);
	//[left , keyi - 1] [keyi] [keyi + 1 , right]
	if (keyi - 1 > left)
	{
		QuickSort(a, left, keyi - 1);
	}
	if (right > keyi + 1)
	{
		QuickSort(a, keyi + 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

3.2.2.3 前后指针法

前后指针法的思想是选取待排序数组的左边作为关键字，使用一个变量keyi记录关键字的下标，再使用两个下标分别记录关键字的下标（prev）和关键字左边的一个元素（cur）,先使cur从左向右遍历，若cur指向的元素比关键字大，那么cur向后继续遍历。若cur指向的元素比关键字小，那么prev先向后移动，cur和prev指向的元素交换，然后cur向后继续遍历，重复上面的步骤，直到cur越界后，keyi指向的元素（关键字）与prev上指向的元素交换，则完成了当前关键字左边的元素比关键字小，关键字右边的元素比关键字大，那么则完成了第一次排序。

记录交换后关键字的下标，将关键字左边和右边分割成为两个待排序区间，重复上面第一次排序的操作继续将剩下的待排序区间进行排序，直到区间不存在或者是区间内只有一个元素 ，那么当前区间不可继续分割，则这次排序才算结束。当所有的区待排序区间都不存在或是只有一个元素时，那么所有的元素就到了它应该在的位置，则排序完成。

int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;

	int keyi =  left;

	while (cur <= right)
	{
		if (a[cur] < a[keyi] && cur != prev)
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);

	return prev;
}

void QuickSort(int* a, int left, int right)
{
	int keyi = PartSort3(a, left, right);
	//[left , keyi - 1] [keyi] [keyi + 1 , right]
	if (keyi - 1 > left)
	{
		QuickSort(a, left, keyi - 1);
	}
	if (right > keyi + 1)
	{
		QuickSort(a, keyi + 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

3.2.2.4 快速排序的优化（三数取中）

前面未优化的快速排序有一个致命缺点，就是当待排序数组有序或接近有序时，选取关键字并排序后需要将待排序数组分割为两个区间，而有序或接近有序的数字分割时，并不能实现相对的平分，使得一个区间占据了一两个元素，而另外一个区间占据相对很多的数据，导致每一次排序几乎都是O(n的递减)，最终快速排序的时间复杂度变为O(n^2)。

三数取中的实现是取区间最左边、最右边和中间的三个元素中中间大小的元素，将该元素与待排序数组最左边元素交换，使得所取关键字的大小不是最大或最小，使得分割区间时，两个区间元素数量不是最差的情况（即一个区间占一个元素，而另外一个区间占其他元素），能有效的降低待排序数组为有序或接近有序时，快速排序的时间复杂度。

下面实现了三数取中的代码，并且在hoare版本中的使用，三数取中在上面三个方法使用的方法相同，在下面非递归版本中也会使用到。

int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else //(a[left] <= a[right])
		{
			return right;
		}
	}
	else //(a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}

// 快速排序hoare版本三数取中优化
int PartSort1(int* a, int left, int right)
{
	int keyi = GetMidIndex(a, left, right);
	Swap(&a[keyi], &a[left]);
	keyi = left;

	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);

	return 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

3.2.2.5 非递归版本

快速排序的非递归版本需要使用栈，而C语言的库中并没有关于栈的数据结构，那么这里需要自己实现栈。递归和非递归版本的内部逻辑相同，都是使用上面三个排序思路。

递归版本在向下传递参数时，每一层都有单独的两个变量存储待排序区间的范围，而快速排序非递归版本没有这个能力，那么非递归版本需要通过栈来存储待排序数组的左右两边的下标，将待排序数组排序后，记录关键字的下班，将待排序数组分割为两个区间，并将两个区间范围的下标入栈，形成两个新的待排序数组，重复上面的操作，取出待排序数组的范围进行下一次排序，直到栈不为空。若栈不为空，则说明还有区间未被排序，取出栈中待排序数组的范围继续排序。栈为空时，说明所有区间都排序结束，则快速排序完成。

QuickSortNonR.c 文件的实现
1

#include <stdio.h>
#include "Stack.h"

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);

	int end = right;
	int begin = left;

	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st))
	{
		begin = StackTop(&st);
		StackPop(&st);
		end = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort1(a, begin, end);
		//[begin , keyi - 1] [keyi] [keyi + 1 , end]
		if (end > keyi + 1)
		{
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}
		if (keyi - 1 > begin)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}
}
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

stack.h 文件的实现
1

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
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

stack.c 文件的实现
1

#include "Stack.h"
// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->capacity = 0;
	ps->top = 0;     //top指向栈顶的后面一个元素
	ps->a = NULL;
}

void StackFull(Stack* ps)
{
	assert(ps);
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
	if (tmp == NULL)
	{
		perror("realloc");
		return;
	}
	ps->a = tmp;
	ps->capacity = newcapacity;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	if (ps->capacity == ps->top)
		StackFull(ps);
	ps->a[ps->top] = data;
	ps->top++;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//栈为空，则不能继续出栈
	ps->top--;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//栈为空，则无栈顶元素
	return ps->a[ps->top - 1];
}

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;   //由于top是指向栈顶元素的下一个位置		
					  //而元素个数正好是下标 + 1 ，也就是top
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;

	ps->capacity = 0;
	ps->top = 0;
}
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

3.2.3 快速排序的时间复杂度

快速排序的时间复杂度如果每次都平分两个待排序数组时为O(n*logn --> n * 以二为底n的对数) ，而在最坏的情况下时间复杂度为O(n^2),但是在三数取中的优化下，快速排序不会变为最坏的情况,一般时间复杂度为O(n*logn)。

3.2.4 快速排序的总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(n*logn)
3. 空间复杂度：O(logn)
4. 稳定性：不稳定

---

4. 归并排序

4.1 归并排序的基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

4.2 归并排序的代码实现

需要注意的是归并排序的边界问题，归并排序每次将两个有序子序列合并为一个有序序列，但是这两个子序列并不一定都存在或是两个子序列都存在，但是两个子序列的元素个数并不相同。使用变量begin1，end1记录第一个子序列的区间范围，使用变量begin2，end2记录第二个子序列的区间范围，那么越界情况可以分为下面三种情况：

1. end2 越界
   

2. begin2和end2越界
   

3. end1、begin2和end2越界
   

所以实现归并排序需要很好的处理好边界问题。

4.2.1 归并排序的递归版本实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// 归并排序递归实现
void _MergeSort(int* a, int left, int right, int* tmp)
{
	int mid = (left + right) / 2;
	//[left , mid] [mid + 1 , right]
	if (mid > left)
		_MergeSort(a, left, mid, tmp);
	if (right > mid + 1)
		_MergeSort(a, mid + 1, right, tmp);

	int i = left;
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}
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

4.2.2 归并排序的非递归版本实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		int j = 0;
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			//三种越界情况
			//end1 begin2 end3 都越界
			//begin2 end3 越界
			//end3 越界
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			//这里需要归并一段，拷贝一段，而不是整段拷贝
			//整段拷贝会使原数组中后面没有归并的元素被覆盖
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}
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

4.3 归并排序的总结：

1. 归并的缺点在于需要O(n)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(n*logn)
3. 空间复杂度：O(n)
4. 稳定性：稳定

5. 计数排序（非比较函数）

5.1 计数排序的思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

5.2 计数排序的代码实现

#include <stdio.h>
#include <stdlib.h>

// 计数排序
void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* CountArr = (int*)calloc(range, sizeof(int));
	if (CountArr == NULL)
	{
		perror("malloc");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		CountArr[a[i] - min]++;
	}

	int num = 0;
	for (int j = 0; j < range; j++)
	{
		while (CountArr[j]--)
		{
			a[num++] = j + min;
		}
	}
}
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

5.3 计数排序的总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(n,范围))
3. 空间复杂度：O(范围)

---

三、排序算法复杂度及稳定性分析

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！