【数据结构】排序总结_编写代码实现一种插入排序(直接插入排序)心得体会

一、插入排序

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

直接插入排序

基本思想

想已经排好序的数据里面插入一个新数据，用将要插入的数与原排好的进行比较，找到应该插入的位置插入，原数据向后顺移。

代码实现

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		//其中一趟，i前面已经有序，将a[end+1]插入[0,end]数组中
		int end = i;
		int next = a[end + 1];

		//一直比较到第一个
		while (end >= 0)
		{
			if (next < a[end])
			{
				//如果要插入的数据小，那么原数据往后挪
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				//如果比前面最后一个还大，因为前面已经有序，所以直接退出本次循环
				break;
			}
		}
		//找到了合适的位置，插入数据即可
		a[end + 1] = next;
	}
}
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

性能分析

特性：元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)
最好：O(N) – 顺序有序或者接近有序
最坏：O(N^2) – 逆序
空间复杂度：O(1)
稳定性：稳定

希尔排序

基本思想

设待排数据有n个，先选定一个整数gap<n作为间隔，把待排元素中分成gap个子序列，所有距离为gap的元素分在同子序列内，并对每个子序列内的元素进行直接插入排序。然后缩小间隔gap，重复上述子序列划分和排序的工作。当到达gap==1时，所有元素在同一序列排好序。

代码实现

// 希尔排序
void ShellSort(int* a, int n)
{
	//希尔排序即为优化的插入排序
	//1.分组预排序：规定一个间隔，按间隔分组排序，这样会使数组变得更加有序
	//2.插入排序（间隔不断减少到1，当间隔为1时为插入排序）

	int gap = n;
	//不断减小gap直到为1，最后一次为插入排序。但数组经过前面的排序，已经非常接近有序，时间复杂度大大降低
	while (gap > 1)
	{
		//一般的两种改变gap的方法
		//gap = gap / 2;
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int next = a[end + gap];//找到对应组的下一个
			while (end >= 0)
			{
				if (next < a[end])
				{
					//数据往后挪
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					//已经有序
					break;
				}
			}
			//找到对应位置
			a[end + gap] = next;
		}
	}
}
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

性能分析

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

二、选择排序

从未排序的序列里面选择最大或者最小的元素放在本序列的特定位置。

直接选择排序

基本思想

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, end = n - 1;//设置两个下标，指向未排序的数组区间
	while (begin < end)
	{
		//用于记录每次比较后该区间的最大值和最小值下标，可随机取begin和end之间的值
		int maxi = begin, mini = 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位置的值是最大的，即begin=maxi，那么交换后最大值的下标改变，maxi也需要改变
		if (begin == maxi)
			maxi = mini;
		Swap(&a[end], &a[maxi]);
		//改变区间大小
		--end;
		++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

性能分析

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
总体来说是一个非常差的排序，一般不使用

堆排序

基本思想

若要升序，需要建大堆，每次将堆顶元素和最后一个元素交换，总数减少再调整成堆，如此往复知道堆元素总数为0即可。

若要降序，需要建小堆，其他都一样。

代码实现

// 堆排序，升序建大堆
void AdjustDwon(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//选出两个孩子中较大的一个
		if (child + 1 < n && a[child + 1] > a[child])
			child = child + 1;
		//孩子大于父节点就交换
		if (a[child] > a[parent])
			Swap(&a[child], &a[parent]);
		else
			break;
		parent = child;
		child = parent * 2 + 1;
	}
}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
        //将数组元素向下调整建堆
		AdjustDwon(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
        //不断交换并向下调整
		Swap(&a[0], &a[end]);
		AdjustDwon(a, 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

性能分析

时间复杂度：O(N*log N)
空间复杂度：O(1)
稳定性：不稳定
总体来说排序很快

三、交换排序

两两比较大小，交换为合适的相对位置

冒泡排序

基本思想

若是升序：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

代码实现

// 冒泡排序
void BubbleSort(int* a, int n)
{
	//n趟
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;//用于判断数组是否有序
		//第一次将最大的交换到最后
		for (int i = 1; i < n - j; ++i)
		{
			//比较两个数的大小
			if (a[i - 1] > a[i])
			{
				//前一个大于当前就交换
				Swap(&a[i - 1], &a[i]);
				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
24
25

性能分析

时间复杂度：O(N* N)
空间复杂度：O(1)
稳定性：稳定
总体来说排序很简单，但效率不是太高

快速排序

基本思想

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

缺陷： 一般选取区间最左边或者最右边，当数据有序的时候，每次基准值的位置不变，但仍要和其他元素比较，所以时间复杂度就变成了O(N^2)，此时是一个非常差的算法。

改进：

1. 三数取中法选基准值，三数-> 最左边 最中间 最右边 的三个数取一个大小中间值，此时基准值接近中间位置，快排仍然很快。
2. 小区间优化，递归最后几层调用次数占了所有调用的大部分，但是最后几层的区间内数据已经接近有序，适合插入排序，减少递归调用。

不可改进的缺陷：关键值全部相同，或者相等的数非常多时，算法排序性能很差O(N^2)，而且无法优化

方法

Hoare:选取一个基准值，左边找大，右边找小，左右两个下标不断增加，查找直到相遇

挖坑法： 右边找小放在坑里，右边位置成为新的坑
左边找大放在坑里，左边位置成为新的坑
相遇后将最初始坑的值放在现在坑里

前后指针法：小的往右放，大的被交换到左边

快速排序非递归：用栈存放递归的区间值，再用循环不断执行

代码实现

//三数取中，三数-》最左边  最中间   最右边 的三个数取一个大小中间值
//目的：解决快排接近有序时的缺陷
int GetMidIndex(int* a, int left, int right)
{
	//int midi = (left + right) / 2;
	//为防止溢出，左边加上差值除以二
	int midi = left + ((right - left) >> 1);
	if (a[left] < a[right])
	{
		if (a[left] > a[midi])
		{
			return left;
		}
		else
		{
			//a[left] < a[midi]
			if (a[midi] < a[right])
			{
				return midi;
			}
			else
			{
				//a[midi] > a[right]
				return right;
			}
		}
	}
	else
	{
		//a[left] > a[right]

		if (a[right] > a[midi])
		{
			return right;
		}
		else
		{
			//a[right] < a[midi]
			if (a[midi] < a[left])
			{
				return midi;
			}
			else
			{
				//a[midi] > a[left]
				return left;
			}
		}
	}
}
// 快速排序递归实现
// hoare版本
// [left, right]
// O(N)
// 快速排序hoare版本
int Partition1(int* a, int left, int right)
{
	//优化：三数取中
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);//将中间值放在最左边，不改变后续的代码

	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;
}
// 快速排序挖坑法
int Partition2(int* a, int left, int right)
{
	//优化：三数取中
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);//将中间值放在最左边，不改变后续的代码
	//设一个基准，也就是初始坑
	int pivot = left;
	int key = a[left];//基准值
	//思想：右边找小放在坑里，右边位置成为新的坑
	//      左边找大放在坑里，左边位置成为新的坑
	//      相遇后将最初始坑的值放在现在坑里
	while (left < right)
	{
		//选取左边作为关键值，那么右边先开始查找

		//右边找比关键值小的数,等于不算，防止死循环
		while (left < right && a[right] >= key)
		{
			//右边比关键大就继续
			--right;
		}
		//找到了，先放入坑
		a[pivot] = a[right];
		pivot = right;//新的坑

		//左边找比关键值大的数,等于不算，防止死循环
		while (left < right && a[left] <= key)
		{
			//左边比关键值小就继续
			++left;
		}
		//找到了，先放入坑
		a[pivot] = a[left];
		pivot = left;//新的坑
	}
	a[pivot] = key;//最开始的值放回坑
	//返回该坑位
	return pivot;
}
// 快速排序前后指针法
int Partition3(int* a, int left, int right)
{
	//优化：三数取中
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);//将中间值放在最左边，不改变后续的代码

	//思想：小的往右放，大的被交换到左边
	if (left == right)
		return left;
	int prev = left;
	int cur = left + 1;
	int keyi = left;

	//改进代码
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			//前一个条件判断是否找到小的，后一个条件判断防止与自己交换
			Swap(&a[prev], &a[cur]);
		}
		//遍历区间每个元素
		++cur;
	}

    //原代码
	//while (cur <= right)
	//{
	//	//cur向后找小
	//	while (cur <= right&&a[cur] >= a[keyi])
	//	{
	//		++cur;
	//	}
	//	if (cur <= right)
	//	{
	//		//找到了小的，放在prev的后一个位置
	//		++prev;
	//		//将小的值和大的值交换
	//		Swap(&a[prev], &a[cur]);

	//		//
	//		++cur;
	//	}		
	//}

	//最后把key放在他正确的位置
	Swap(&a[prev], &a[keyi]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	//区间为大小为1时结束
	if (left > right)
		return;
	//先找到一个分隔点
	//int keyi = Partition1(a, left, right);
	//int keyi = Partition2(a, left, right);
	int keyi = Partition3(a, left, right);
	// [left, keyi-1] keyi [keyi+1, right]
	// 完全递归
	//QuickSort(a, left, keyi - 1);//左边区间排序
	//QuickSort(a, keyi + 1, right);//右区间排序

	//小区间优化
	//递归最后几层调用次数占了所有调用的大部分，但是最后几层的区间内数据已经接近有序，适合插入排序，减少递归调用
	if (right - left + 1 < 10)
	{
		//插入排序是对数组首地址开始的n个数据进行排序，针对不同区间使用
		InsertSort(a + left, right - left + 1);
	}
	else
	{
		QuickSort(a, left, keyi - 1);//左边区间排序
		QuickSort(a, keyi + 1, right);//右区间排序
	}
}

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	//用栈存放递归的区间值，再用循环不断执行
	ST st;
	StackInit(&st);

	//先将完整区间入栈，需要注意的是栈是先进后出
	StackPush(&st, left);
	StackPush(&st, right);
	while (!StackEmpty(&st))
	{
		//取出栈里面存放的区间值
		int end = StackTop(&st);//先取出来的是区间右值
		StackPop(&st);
		int begin = StackTop(&st);//区间左值
		StackPop(&st);

		//先但趟排序，分隔出两个区间
		int keyi = Partition3(a, begin, end);
		//得到区间[begin,keyi-1]  keyi [keyi+1,end]

		//处理右边，那就把左边先入栈
		if (begin < keyi - 1)
		{
			//区间还需要继续排序就入栈
			StackPush(&st, begin);
			StackPush(&st, keyi - 1);
		}
		//右边入栈
		if (end > keyi + 1)
		{
			//区间还需要继续排序就入栈
			StackPush(&st, keyi + 1);
			StackPush(&st, end);
		}
	}
	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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244

性能分析

时间复杂度：O(N*log N)
空间复杂度：O(log N) 递归产生的基准值
稳定性：不稳定
总体来说改进后排序很快，很常用。

四、归并排序

归并排序

基本思想

类似于快速排序，也是采用分治思想，但不用选基准值。归并排序是将待排的元素序列分成两个长度尽量相等的子序列，为每个子序列排序，然后再将它们合并，得到有序序列。执行过程一直在调用一个划分序列过程，知道子序列为空或者只有一个元素，那样可认为是有序，然后不断归并。

可采用递归，近似把数组分成一个二叉树。

也可采用非递归，设置一个间距gap，以两倍速率增长，gap1 一一归并所有元素；gap2，两两归并所有元素；…直到gap大于n，整个序列全部归并，排好序。
但要注意边界，因为gap以两倍增长，如果数组元素总数不是2^x，那么可能会发生数组越界；对两个需要合并的区间判断是否越界

代码实现

递归实现

//合并两段区间
void Merge(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
	//升序
	int i = begin1;//tmp数组的下标
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i] = a[begin1];
			++begin1;
		}
		else
		{
			tmp[i] = a[begin2];
			++begin2;
		}
		++i;
	}

	while (begin1 <= end1)
	{
		//右边还没排完
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		//右边还没排完
		tmp[i++] = a[begin2++];
	}
}
//归并排序子程序
void _MergeSort(int* a, int left, int right, int* tmp)
{
	//控制好递归的返回条件
	if (left >= right)
		return;
	//先让两个区间有序，再合并成一个新的有序的区间
	int mid = (left + right) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	//两个区间有序，进行归并到tmp数组
	Merge(a, left, mid, mid + 1, right, tmp);

	//将tmp排好序的部分复制到原数组
	for (int i = left; i <= right; ++i)
	{
		a[i] = tmp[i];
	}
}

// 归并排序递归实现
void MergeSort(int* a, int n)
{
	//创建一个临时数组，存放部分已经排好序区间
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
		exit(-1);
	_MergeSort(a, 0, n - 1, tmp);
	//释放开辟的数组
	free(tmp);
	tmp = NULL;
}
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

非递归实现

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	//思想：模拟实现递归归并排序的过程，倒着来
	//先一个和一个归并，然后两个和两个归并，最后全部归并

	//创建一个临时数组，存放部分已经排好序区间
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
		exit(-1);

	int gap = 1;//控制归并的个数
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//找到两个归并的区间  [i,i+gap-1]  [i+gap,i+2*gap-1]
			//比如gap=1,i=0  [0,0] [1,1] 
			//gap=1,i=2      [2,2] [3,3]
			//gap=1,i=4      [4,4] [5,5]
			//gap=2,i=0      [0,1] [2,3]

			//分别设置下标指向这两个区间
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			
             //区间
             //[begin1,end1]  [begin2,end2]
            
			//很多时候不是刚好分开，需要针对两个区间越界处理
			if (end1 >= n || begin2 >= n)
			{
				//end1越界,或者begin2越界，直接退出，因为后面的数据已经不用归并
				break;
			}
			if (end2 >= n)
			{
				//第二个区间的右值越界，修改到数组边界吗，继续与前面是归并
				end2 = n - 1;
			}

			//归并
			Merge(a, begin1, end1, begin2, end2, tmp);

			//将tmp排好序的部分复制到原数组
			for (int j = i; j <= end2; ++j)
			{
				a[j] = tmp[j];
			}
		}

		gap *= 2;//间距每次以两倍增加
	}
	free(tmp);
	tmp = NULL;
}
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

性能分析

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

五、非比较排序

计数排序

基本思想

可分为绝对映射和相对映射，都要开辟一个数组

绝对映射：将要排序的序列的所有关键值映射到数组的下标，开辟一个下标足够被映射的数组。此时序列关键值最大值加1即为数组大小。

相对映射：很多时候采用绝对映射，会浪费很多空间，我们选用该序列关键值最大和最小值，每个数减去最小值映射到数组下标，可减少空间浪费，并且能排负数。

代码实现

void CountSort(int* a, int n)
{
	//以防开辟数组过于大，只开辟最大值和最小值的差值个数空间即可
	int min = a[0], max = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}

	int size = max - min + 1;
	//创建一个临时数组用于计数，每个下标的值就是原数组值为此下标的个数
	int* count = (int*)malloc(sizeof(int) * size);
	if (count == NULL)
		exit(-1);
	memset(count, 0, sizeof(int) * size);//初始化为0，初始每个个数为0

	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;//计数
	}

	//拷贝回原数组
	int j = 0;
	for (int i = min; i <= max; ++i)
	{
		while (count[i - min]--)
		{
			a[j++] = i;
		}
	}

	free(count);
	count = NULL;
}
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

性能分析

Size即需要开辟的数组大小

1. 时间复杂度：O(Max(N, Size))
2. 空间复杂度：O(Size)
3. 适合范围比较集中的整数数组。范围较大，或者是浮点数等等都不适合排序了