数据结构（C语言实现）——常见排序算法的基本思想及实现（快速排序的三种方法和优化及非递归实现快速排序）

1. 前言

生活中几乎处处都会用到排序，比如：网购时的店铺顺序，学生成绩的排名等，今天我们就来学习数据结构中常见的几种排序算法。

2. 排序

2.1 概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2.2 常见的排序算法

插入排序：直接插入排序、希尔排序
选择排序：直接选择排序、堆排序
交换排序：冒泡排序、快速排序
归并排序：归并排序

下面我就为大家介绍这些排序算法的特点及如何实现。

3. 常见排序算法的实现

3.1 直接插入排序

思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。

代码实现：

void InsertSort(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		//[0,end]有序，把end+1的位置插入，并保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		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

特点：
1.元素集合越接近有序，直接插入排序算法的时间效率越高
2.时间复杂度：O(N^2)
3.空间复杂度：O(1)
4.稳定性：稳定

3.2 希尔排序

思想：
先选定一个整数，把待排序文件中所有记录分成若干个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取gap=gap/3+1，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

代码实现：

void ShellSort(int* a, int n)
{
	//gap > 1时是预排序
	//gap 最后一次等于1，是直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		int i = 0;
		for (i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					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
27
28
29

特点：
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，进行直接插入排序，就会很快。
3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，根据严蔚敏老师写的《数据结构（C语言版）》中分析的，我们可以得到希尔排序的时间复杂度大约是O(N^1.3)。
4.稳定性：不稳定

3.3 直接选择排序

思想：
1.在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素。
2.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。
3.在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

我们对直接选择排序进行一点优化，让这个算法每次分别选出一个最大的数和一个最小的数，这样可以两边同时进行排序，减少程序执行的时间。
代码实现：

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin; i < end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		//如果begin和maxi重叠，那么要修正一下maxi的位置
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}
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

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

3.4 堆排序

思想：
堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

代码实现：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(int* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(int* arr, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && arr[child + 1] < arr[child])
		{
			child = child + 1;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* arr, int size)
{
	//排升序建大堆，排降序建小堆
	//向上调整建堆O(N*logN)
	//int i = 0;
	//for (i = 1; i < size; i++)
	//{
	//	AdjustUp(arr, i);
	//}

	//向下调整建堆O(N)
	int i = 0;
	for (i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, size, i);
	}

	int end = size - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}
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

特点：
1.堆排序使用堆来选数，效率就高了很多。
2.时间复杂度：O(N*logN)
3.空间复杂度：O(1)
4.稳定性：不稳定

3.5 冒泡排序

思想：
1.先比较相邻的元素，如果第一个数比第二个数大，就交换他们两个。
2.对每一对相邻元素都重复第一步，从开始的两个元素直到结尾的最后两个元素。这一趟排序结束后最后的元素就是最大的数。
3.所有的元素重复以上的步骤，除了已经排好序的元素，所以每次待排序元素个数都减1。每一个元素都排序结束后就成了升序。

代码实现：

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

特点：
1.冒泡排序是一种非常容易理解的排序
2.时间复杂度：O(N^2)
3.空间复杂度：O(1)
4.稳定性：稳定

3.6 快速排序

思想：
任取待排序元素序列中的某元素作为基准值key，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值key，右子序列中所有元素均大于基准值key，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

而问题就是如何将一个待排序序列按key分割成两个满足要求的子序列，下面我们来介绍三种最常见的方式。

3.6.1 hoare版本

思想：
1.将序列中第一个元素定为基准值key。
2.右边先走，从右向左遍历序列找比key小的位置，找到后停下来。
3.左边再走，从左向右遍历序列找比key大的位置，找到后停下来。
4.交换这两个位置，不断重复2.3两步，直到左右相遇，此时再把key和任意一个位置交换，key的位置就是最终位置，同时将序列分割成key的左边和key的右边两个序列。

代码实现：

//hoare版本
int PartSort1(int* a, int left, int right)
{
	int begin = left;
	int end = right;
	int key = left;
	while (left < right)
	{
		//右边先走，找小
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		//左边再走，找大
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[key], &a[left]);
	key = left;
	return 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

3.6.2 挖坑法

思想：
1.先将左边第一个元素放到一个临时变量key中存储，这个位置就形成了一个坑位。
2.右边先走，从右向左遍历序列找比key小的位置，找到后把这个数填到左边的坑中，此时这个数原来的位置就形成了一个新的坑。
3.左边再走，从左向右遍历序列找比key大的位置，找到后把这个数填到右边的坑中，此时这个数原来的位置又形成了一个新的坑。
4.循环2.3步骤，直到左右相遇，把key填到此时的坑中，这样key的左右区间就被划分好了。

代码实现：

//挖坑法
int PartSort2(int* a, int left, int right)
{
	int begin = left;
	int end = right;
	int key = a[begin];
	int pit = begin;
	while (left < right)
	{
		//右边先走，找小,填到左边的坑里面去。这个位置形成新的坑
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;
		//左边再走，找大,填到右边的坑里面去。这个位置形成新的坑
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[pit] = key;
	return pit;
}
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

3.6.3 前后指针法

思想：
1.初始时prev指针指向序列的开头，cur指针指向prev的下一个位置。
2.cur指针开始向右遍历序列，直到找到比key小的值。
3.prev指针向右走一步，交换prev指针指向的值和cur指针指向的值。
4.重复2.3步骤，直到cur==NULL。

代码实现：

//前后指针法
int PartSort3(int* a, int left, int right)
{
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			prev++;
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[key], &a[prev]);
	key = prev;
	return key;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.6.4 快速排序的优化

3.6.4.1 三数取中法

快速排序的效率和key的选取有直接的关系，如果每次key都是最小值或者最大值时，就是最坏的情况，所以我们可以合理的选择key值，来尽量避免这种情况，最好的选key方法就是三数取中法。

代码实现：

int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[right] > a[mid])
		{
			return mid;
		}
		else if (a[right] < a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else //a[left] >= a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			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

3.6.4.2 小区间简化法

快速排序的空间复杂度和递归深度有关，递归次数越多，程序占用空间就越多，而我们通过快速排序的思想就能发现，其实递归次数最多的恰好就是递归的最后几层序列，但此时每个序列中几乎只有很少的元素，此时继续递归下去就是对空间的浪费，容易造成栈溢出，所以我们可以设定一个界限，如果数据少于这个界限，就不需要再递归下去了，使用直接插入排序更简单，效率更好。

3.7 快速排序最优版

通过上面的方法，我们就能够很好的划分递归子区间，并选取合适的key值，而且也不会造成空间浪费。

最终版快速排序代码如下：

//前后指针法
int PartSort3(int* a, int left, int right)
{
	int key = left;
	int prev = left;
	int cur = left + 1;
	//三数取中法优化
	int mid = GetMid(a, left, right);
	Swap(&a[key], &a[mid]);

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

void QuickSort(int* a, int left, int right)
{
	//区间不存在，或者只有一个值则不需要在处理
	if (left >= right)
	{
		return;
	}
	
	if (right - left > 10)
	{

		//int key = PartSort1(a, left, right);
		//int key = PartSort2(a, left, right);
		int key = PartSort3(a, left, right);
		QuickSort(a, left, key - 1);
		QuickSort(a, key + 1, right);
	}
	else
	{
		//递归到小区间的时候，用插入排序
		InsertSort(a + left, right - left + 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

特点：
1.快速排序整体的综合性能和使用场景都是比较好的。
2.时间复杂度：O(N*logN)
3.空间复杂度：O(logN)
4.稳定性：不稳定

3.8 快速排序非递归实现

利用栈的特点来实现非递归的快速排序

代码如下：

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	StackInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);

	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);

		int right = StackTop(&st);
		StackPop(&st);

		int key = PartSort3(a, left, right);

		if (key + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, key + 1);
		}
		if (left < key - 1)
		{
			StackPush(&st, key - 1);
			StackPush(&st, left);
		}
	}
	StackDestroy(&st);
}
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

3.9 归并排序

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

代码实现：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//[begin, mid] [mid+1, end] 分治递归，让子区间有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	//归并[begin, mid] [mid+1, end]
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int i = begin1;
	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 + begin, tmp + begin, sizeof(int)*(end - begin + 1));

}


void MergeSort(int* a, int n)
{
	assert(a);
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	_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
50
51
52
53
54
55

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

3.10 归并排序非递归实现

设置一个gap值，每次归并的区间大小由gap来控制，以此实现非递归的归并排序。

代码实现：

void MergeSortNonR(int* a, int n)
{
	assert(a);
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2*gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			//越界-修正边界
			if (end1 >= n)
			{
				end1 = n - 1;
				//[begin2, end2]修正为不存在区间
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				//[begin2, end2]修正为不存在区间
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			
			int j = begin1;
			int m = end2 - begin1 + 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) * m);
		}
		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
64

4. 排序算法复杂度及稳定性分析

5. 结尾

关于数据结构中常见的排序算法我就给大家介绍到这里了，要想学会排序算法最重要的是掌握每种排序的思想，熟悉每一种算法的特点、复杂度和稳定性，在不同的场景选择最合适的排序算法。文中难免有很多地方出现错误和纰漏，此文仅供大家学习和参考。如果本文对大家学习排序算法有帮助的话，博主感到非常荣幸。
最后，感谢各位大佬的耐心阅读和支持，觉得本篇文章写的不错的朋友可以三连关注支持一波，如果有什么问题或者本文有错误的地方大家可以私信我，也可以在评论区留言讨论，再次感谢各位。