【数据结构】排序算法的代码实现

---

往期数据结构文章可点击下列链接

【数据结构】时间复杂度
【数据结构】顺序表
【数据结构】链表——增、删、查、改
【数据结构】双向循环链表
【数据结构】栈和队列详解
【数据结构】树详解——二叉树——堆
有兴趣的同学可以点击前往支持一下

---

前言

排序：所谓排序就是使一串数据以一定规律顺序递增或者递减的排列起来。

在正式学习排序算法之前，我先带大家了解一下排序算法的分类：

下来我会一一接受各个排序算法：

---

直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

按照玩扑克牌在发牌时的思想我们每抽到一张新的排，就从后往前进行比较，直到把牌放到合适的位置。

在实际写代码时：当插入第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)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			end--;
		}
		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

时间复杂度：O(N^2)
空间复杂度：O(1)

---

希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序

在笔者看来，希尔排序就是数组插入排序组成。将数组从无序逐渐变为有序。

在上述过程中gap = 5时，插入排序的次数即为5组插入排序，所以希尔排序是建立在插入排序之上的

代码实现：

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

时间复杂度：O(N^1.3)
空间复杂度：O(1)

---

选择排序

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

• 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
• 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
• 在剩余的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[maxi])
				maxi = i;
			if (a[i] < a[mini])
				mini = i;
		}
		Swap(&a[begin], &a[mini]);
		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

时间复杂度：O(N^2)
空间复杂度：O(1)

---

堆排序

掌握堆排序前我们首先要了解完全二叉树与堆的概念，具体内容可以看笔者的另一篇博客，本文不再赘述。——【数据结构】树详解——二叉树——堆

代码实现：

void AdjustDown(int* a, int n, int parent)
{
	int child = 2 * parent + 1;

	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	for (int i = 1; i < n; i++)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 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

时间复杂度：O(N*logN)
空间复杂度：O(1)

---

冒泡排序

冒泡排序即为遍历数组，两两元素进行比较，如果arr[i] > arr[i+1]则进行交换。这样每一轮遍历我们就能把大的元素"甩"到最后。

代码实现：

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

时间复杂度：O(N*2)
空间复杂度：O(1)

---

快速排序

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

这样每次交换之后，基准元素都能到最终的位置

快速排序运用了递归的思想：每次排序后左边的元素都比基准值要小，右边的元素总比基准值要大所以可以对基准值左右的范围分别再进行快速排序，这时候就使用了递归。

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
	if(right - left <= 1)
	return;
	// 按照基准值对array数组的 [left, right)区间中的元素进行划分
	int div = PartSort(array, left, right);
	// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
	// 递归排[left, div)
	QuickSort(array, left, div);
	// 递归排[div+1, right)
	QuickSort(array, div+1, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

下面我们来具体讲一讲找基准值的方法：

一般来讲我们会把首元素做为基准值，定义一个左边界下标left， 右边界下标right。我们需要先从右边开始 找到一个比基准值小的元素停止，然后从左边找到比基准值大的元素，之后left与right进行交换，直到两者相遇为止（left == right）。相遇后再将基准值与left位置的元素进行交换。

代码实现：

int PartSort(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[keyi], &a[left]);
	return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(N*logN)
空间复杂度：O(1)

---

归并排序

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

归并排序核心步骤：

这里看出来，归并排序与快速排序相比很大的不同是：归并排序是一种后序排序，而快速排序即为一种前序遍历。

代码实现：

void _MergeSort(int* a, int* tmp, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;

	//[left, mid], [mid + 1, right]
	_MergeSort(a, tmp, left, mid);
	_MergeSort(a, tmp, mid + 1, right);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int tmpi = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[tmpi++] = a[begin1++];
		}
		else
		{
			tmp[tmpi++] = a[begin2++];
		}
	}
	if (begin1 <= end1)
	{
		while (begin1 <= end1)
		{
			tmp[tmpi++] = a[begin1++];
		}
	}
	else if (begin2 <= end2)
	{
		while (begin2 <= end2)
		{
			tmp[tmpi++] = 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);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	_MergeSort(a, tmp, 0, n - 1);


	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

时间复杂度：O(N*logN)
空间复杂度：O(N)