部分排序算法讲解

---

部分排序算法讲解

1.插入排序

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

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)
{
	//[0,end]有序
	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];
				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

2.希尔排序

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

当gap=1时会进行一个直接插入排序,一定会保证数组有序.由于之前的预排序,会使最后一次的时间会降低很多.

代码实现:

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//gap = 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];
					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

2.选择排序

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

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 max = end;
		int min = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[max])
			{
				max = i;
			}
			if (a[i] < a[min])
			{
				min = i;
			}
		}
		swap(a + begin, a + min);
		if(max==begin)
		{
			max = min;
		}
		swap(a + end, a + max);
	/*	if (min == end)
		{
			min = max;
		}
		swap(a + begin, a + min);*/
		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
32
33
34

2.堆排序

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

代码实现:

void AdjustDwon(int* a, int n,int root)
{
	while (root >= 0)
	{
		int parent = root;
		int child = parent * 2 + 1;
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		while (child < n)
		{
			if (a[parent] < a[child])
			{
				swap(a + parent, a + child);
			}
			else
			{
				break;
			}
			parent = child;
			child = parent * 2 + 1;
			if (child + 1 < n && a[child] < a[child + 1])
			{
				child++;
			}
		}
		root--;
	}
	
}

void HeapSort(int* a, int n)
{
	//建堆
		AdjustDwon(a,n,(n-2)/2);
	//排序
	int j = 0;
	while (j<n-1)
	{
		swap(a , a + n - j - 1);
		j++;
		AdjustDwon(a, n - j,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

3.交换排序

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

1.冒泡排序

实现代码:

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

2.快速排序

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

接下来使用的方法实现这种情况,递归,从而使每一个局部有序,从而使整体有序.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vqWqOYRQ-1660749353685)(C:\Users\Administrator\Desktop\20210515134431451.gif)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HZxWY6Tx-1660749353685)(C:\Users\Administrator\Desktop\20210515183213169.gif)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GKua8K1f-1660749353686)(C:\Users\Administrator\Desktop\20210515172409754.gif)]

实现代码:

 //快速排序递归实现

 //取中间值
 int getminindex(int* a, int left, int right)
{
	int mid = (right - left) / 2 + left;
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else//a[mid]>a[right]
		{
			if (a[right] > a[left])
			{
				return right;
			}
			else
			{
				return left;
			}
		}
	}
	else //a[mid]
	{
		if (a[mid] > a[left])
		{
			return mid;
		}
		else //a[mid] < a[left]
		{
			if (a[right] > a[left])
			{
				return left;
			}
			else
			{
				return right;
			}
		}
	}
}
 //快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	int mid = getminindex(a, left, right);
	swap(a+left,a+mid);
	int keyi = left;
	while (left < right)
	{
		//找小
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//找大
		while (left < right&&a[left]<=a[keyi])
		{
			left++;
		}
		if (left < right)
		{
			swap(a + left, a + right);
		}
	}
	swap(a + left, a + keyi);
	return left;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	int mid = getminindex(a, left, right);
	swap(a + left, a + mid);
	int key = a[left];
	int hole = left;
	while (left<right)
	{
		//找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		//swap(a + hole, a + right);
		a[hole] = a[right];
		hole = right;
		//找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		//swap(a + hole, a + left);
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;

}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	int mid = getminindex(a, left, right);
	swap(a + left, a + mid);
	int cur = left+1;
	int prev = left;
	while (cur <= right)
	{
		while(cur<=right&&a[cur] >= a[left])
		{
			cur++;
		}
		if(cur <= right && a[cur]<a[left])
		{
			prev++;
			swap(a + prev, a + cur);
			cur++;
		}
		/*if (cur<=right&&a[cur] < a[left])
		{
			prev++;
			swap(a + cur, a + prev);
		}
		cur += 1;*/
	}
	swap(a + left, a + prev);
	return prev;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if (right - left < 10)
	{
		InsertSort(a + left, right - left + 1);
	}
	else
	{
		int keyi = PartSort3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	
}



// 快速排序 非递归实现(使用栈来模拟实现递归)
void QuickSortNonR(int* a, int left, int right)
{
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, left);
	StackPush(&ps, right);
	while (StackEmpty(&ps))
	{
		int end = StackTop(&ps);
		StackPop(&ps);
		int begin = StackTop(&ps);
		StackPop(&ps);
		if (end <= begin)
		{
			continue;
		}
		int keyi = PartSort3(a, begin, end);
		StackPush(&ps, keyi+1);
		StackPush(&ps, end);
		
		StackPush(&ps, begin);
		StackPush(&ps, keyi - 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
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

结束时,附上在我电脑上的排序效率

10000数据

100000数据

1000000数据

10000000数据

---

效率

10000数据

100000数据

1000000数据

10000000数据

---