【数据结构从青铜到王者】第九篇:数据结构之排序

系列文章目录

---

---

前言

---

一、排序的概念

1.排序的概念

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

二、常见排序算法的实现

1.插入排序

1.基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想

2.代码实现

代码如下：

void InsertSort(int* arr, int sz)
{
	int i = 0;
	int j = 0;
	//多躺排序
	for (i = 0; i < sz - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		//单趟排序
		while (end >= 0)
		{
			if (arr[end]>tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				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
24
25

2.希尔排序

1.基本思想

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

2.代码实现

代码如下：

void ShellSort(int* arr, int sz)
{
	//gap>1的时候，预排序
	//gap=1的时候，直接插入排序
	int gap = sz;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < sz - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end]>tmp)
				{
					arr[end + gap] = arr[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
		printf("gap=%d ", gap);
		for (int i = 0; i < sz; i++)
		{
			printf("%d-->", arr[i]);
		}
		printf("NULL\n");
	}

}
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

3.选择排序

1.基本思想

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

2.代码实现

代码如下：

void Swap(int *a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void SelectSort(int* arr, int sz)
{
	int left = 0;
	int right = sz - 1;
	while (left < right)
	{
		int minIndex = left;
		int maxIndex = left;
		for (int i = left; i <= right; i++)
		{
			if (arr[i] < arr[minIndex])
			{
				minIndex = i;
			}
			if (arr[i]>arr[maxIndex])
			{
				maxIndex = i;
			}
		}
		Swap(&arr[left], &arr[minIndex]);
		if (left == maxIndex)
		{
			maxIndex = minIndex;
		}
		Swap(&arr[right], &arr[maxIndex]);
		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

4.堆排序

1.基本思想

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

2.代码实现

代码如下：

void swap(int* left, int* right)
{
	int tmp = 0;
	tmp = *left;
	*left = *right;
	*right = tmp;
}
void AdjustDown(int* arr, int sz, int parent)
{
	int child = 2 * parent + 1;
	while (child < sz)
	{
		if (child + 1 < sz&&arr[child + 1] > arr[child])
		{
			child++;
		}
		if (arr[child]>arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
//排升序，建大堆
void HeapSort(int *arr, int sz)
{
	//建堆
	int i = (sz - 1 - 1) / 2;
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
	int end = sz - 1;	
	while (end > 0)
	{
		//选出次大的
		swap(&arr[0], &arr[end]);
		//最后一个不用交换，所以为n-1个数为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

5.冒泡排序

1.基本思想

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.代码实现

代码如下：

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

6.快速排序递归思想

1.左右指针法

1.基本思想

2.代码实现

代码如下：

void Swap(int*a, int*b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void QuickSort1(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int midIndex = getMid(arr, begin, end);
	int left = begin;
	int right = end;
	Swap(&arr[left], &arr[midIndex]);
	int key = left;
	while (left<right)
	{
		while (left<right && arr[right] >= arr[key])
		{
			right--;
		}
		while (left<right && arr[left] <= arr[key])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	int meet = left;
	Swap(&arr[key], &arr[meet]);
	QuickSort1(arr, begin, meet - 1);
	QuickSort1(arr, meet + 1, 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

2.挖坑法

1.基本思想

2.代码实现

代码如下：

//挖坑法
void QuickSort2(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int left = begin;
	int right = end;
	int key = arr[begin];
	while (left < right)
	{
		while (left<right && arr[right] >= key)
		{
			right--;
		}
		//把值放到左边的坑位
		arr[left] = arr[right];
		while (left<right && arr[left] <= key)
		{
			left++;
		}
		//把值放到右边的坑位
		arr[right] = arr[left];
	}
	int meet = left;
	//最后相遇的位置就是坑位
	arr[meet] = key;
	QuickSort2(arr, begin, key - 1);
	QuickSort2(arr, key + 1, 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

3.前后指针法

1.基本思想

2.代码实现

代码如下：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
int partSort3(int* arr, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] )
		{
			Swap(&arr[++prev], &arr[cur]);
		}
		cur++;
	}
	int meet = prev;
	Swap(&arr[key], &arr[prev]);
	return meet;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if (end - begin > 10)
	{
		int keyi = partSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 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

4.快速排序优化方法

1.三数取中法

代码如下：

//三数取中
int getMid(int *arr, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (arr[mid] > arr[left])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left]>arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			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
35

2.小区间排序优化

代码如下：

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if (end - begin > 10)
	{
		int keyi = partSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

7.快速排序非递归思想

1.基本思想

2.代码实现

代码如下：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
int QuickSort(int* arr, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[key])
		{
			Swap(&arr[++prev], &arr[cur]);
		}
		cur++;
	}
	int meet = prev;
	Swap(&arr[key], &arr[prev]);
	return meet;
}
void QuickSortNonR(int* arr, int begin, int end)
{
	struct Stack st;
	StackInit(&st);
	StackPush(&st, begin); //先入左，在入右
	StackPush(&st, end);
	while (!StackEmpty(&st))
	{
		int left = 0;
		int right = 0;

		right = StackTop(&st); //取右值
		StackPop(&st);

		left = StackTop(&st); //取左值
		StackPop(&st);
		int key = QuickSort(arr, begin, end);
		if (left < key - 1)
		{
			StackPush(&st, left);
			StackPush(&st, key - 1);
		}
		if (key + 1 < right)
		{
			StackPush(&st, key + 1);
			StackPush(&st, right);
		}
	}
	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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

8.归并排序递归思想

1.基本思想

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

2.代码实现

代码如下：

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}
	//
	int mid = left + (right - left) / 2;
	_MergeSort(arr, left, mid, tmp);     //对mid左边的进行归并
	_MergeSort(arr, mid + 1, right, tmp);//对mid右边的进行归并

	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int i = left;
	while (begin1 <= end1&&begin2 <= end2)  //两端区间合并，将值放到tmp空间中
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	//如果左右区间中一个先结束，则把另一个直接放到tmp空间中
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	//合并完之后，拷贝回原数组
	for (int j = left; j <= right; j++)
	{
		arr[j] = tmp[j];
	}
}
void MergeSort(int* arr, int sz)
{
	int* tmp = (int*)malloc(sizeof(int)*sz);
	if (tmp == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}
	_MergeSort(arr, 0, sz - 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

9.归并排序非递归思想

1.基本思想

2.代码实现

注意情况：

代码如下：

void _MergeSortNonR(int* arr, int* tmp, int begin1, int end1, int begin2, int end2)
{

	int i = begin1;
	while (begin1 <= end1&&begin2 <= end2)//小的数据放到tmp空间
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)//一个空间结束，将另一个区间剩余的数据直接放到tmp的后面
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	int j = begin1;
	for (j = 0; j <= end2; j++)	//结束，拷贝回原空间
	{
		arr[j] = tmp[j];
	}	
}
void MergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);//开辟辅助空间
	if (tmp == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}
	int gap = 1;//合并的区间中相隔间距
	while (gap < n)
	{
		int i = 0;
		for (i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//最后一组的第二个小区间不存在或是第一个小区间不够gap个，结束本次循环
			if (begin2 >= n)
			{
				break;
			}
			//最后一组的第二个小区间不够gap个，结束位置越界了，则第二个小区间的后界变为数组的后界
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			_MergeSortNonR(arr, tmp, begin1, end1, begin2, end2);//合并
		}
		gap = 2 * 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

10.计数排序

1.基本思想

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

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

2.代码实现

代码如下：

//计数排序
void CountSort(int* a, int n)
{
	int min = a[0];//最小值
	int max = a[0];//最大值
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}
	int range = max - min + 1;//min和max之间的数个数
	int* count = (int*)malloc(sizeof(int)*range);//开辟空间range个
	memset(count,0,sizeof(count));//初始化count个数据为0
	if (count == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	for (int i = 0; i < n; i++)	//统计相同元素出现次数（相对映射）
	{
		count[a[i] - min]++;
	}
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
	free(count);
}
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

总结

以上就是今天要讲的内容，本文仅仅简单介绍了数据结构中排序的使用，而排序提供了大量能使我们快速便捷地处理数据的函数和方法。在以后编程中有很高的效率，我们务必掌握！另外如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。