【排序算法】----详解快速排序算法（hoare法，挖坑法，指针法，三数取中优化）1.概念2.代码展示3.结果展示4.复杂度分析5.优化问题6.心得体会

140 阅读 0 评论 93 点赞

我是靠谱客的博主灵巧啤酒，这篇文章主要介绍【排序算法】----详解快速排序算法（hoare法，挖坑法，指针法，三数取中优化）1.概念2.代码展示3.结果展示4.复杂度分析5.优化问题6.心得体会，现在分享给大家，希望可以做个参考。

1.概念

快速排序，选定一个key值作为参考，我们以最后一个数为参考，一个从左向右找比key大的值，一个从右向左找比key小的值，交换这两个值，继续遍历，直到两个指针相遇，然后将key值交换到这个位置，那么数组就分成两段，一段比key大，一段比key小，重复这个过程，直到只有一个数为止。
在这里插入图片描述

2.代码展示

复制代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//hoare版本
void Swap(int* pa, int *pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void _QuickSort1(int left, int right, int *arr)
{
	int index = right;
	int key = arr[index];
	if (left >= right)
	{
		return;
	}
	//找比key大的数
	//找比key小的数
	//交换
	while (left < right)
	{
		while (left < right)
		{
			if (arr[left] >= key)
			{
				break;
			}
			++left;
		}

while (left < right)
		{
			if (arr[right] < key)
			{
				break;
			}
			--right;
		}
		Swap(&arr[left], &arr[right]);	
	}
	Swap(&arr[left], &arr[index]);
	right = index;
	index = left;
	left = 0;
	_QuickSort1(left, index-1, arr); 
	_QuickSort1(index+1,right,arr);
}

//挖坑法
void _QuickSort2(int begin, int end,int * arr)
{
	if (begin >= end)
	{
		return;
	}
	int end1 = end;
	int index = end;
	int key = arr[index];
	
	while (begin <end)
	{	//将比key大的数放在坑里， 从左向右找
		while (begin < end)
		{
			if (arr[begin] > key)
			{
				arr[index] = arr[begin];
				index = begin;
				break;
			}
			++begin;
		}
		//将比key小的数放在坑里， 从右向左找
		while (begin < end)
		{
			if (arr[end] < key)
			{
				arr[index] = arr[end];
				index = end;
				break;
			}
			--end;
		}
	}
	arr[index] = key;//要将Key 放回到坑里
	_QuickSort2(0, index - 1, arr);//前半段
	_QuickSort2(index+1 , end1, arr);//后半段，一定要注意end动了，不要直接传end的值，不然会造成后半段，没有被遍历
	
}

//指针法
void _QuickSort3(int begin, int end, int * arr)
{
	if (begin >= end)
	{
		return;
	}
	int key = arr[end];
	int	cur = begin;
	int prev = cur - 1;
	while (cur < end)
	{
		if (arr[cur] < key && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	++prev;
	Swap(&arr[end], &arr[prev]);
	_QuickSort3(0, prev - 1, arr);
	_QuickSort3(prev + 1, end, arr);
}

void QuickSort1(int* arr, int n)
{
	
	//_QuickSort1(0, n - 1, arr);	//hoare法
	//_QuickSort2(0, n - 1, arr);	//挖坑法
	//_QuickSort3(0, n - 1, arr);	//指针法
}

int Mid(int begin, int end,int* arr)
 {
	int mid = (begin + end) >> 1;
	if (arr[begin] > arr[end])
	{
		if (arr[end] > arr[mid])
		{
			return end;
		}
		else
		{
			if (arr[begin] > arr[mid])
			{
				return mid;
			}
			else
			{
				return begin;
			}
		}
	}
	else
	{
		if (arr[mid] > arr[end])
		{
			return end;
		}
		else
		{
			if (arr[mid] > arr[begin])
			{
				return mid;
			}
			else
			{
				return begin;
			}
		}
	}
	
}

//指针法
int _QuickSort4(int begin, int end, int * arr)
{
	
	int keyindex = Mid(begin, end, arr);
 	Swap(&arr[keyindex], &arr[end]);
	int key = arr[end];
	int	cur = begin;
	int prev = cur - 1;
	while (cur < end)
	{
		if (arr[cur] < key && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	++prev;
	Swap(&arr[end], &arr[prev]);
	return prev;
}

void QuickSort(int begin,int end,int* arr)		//优化
{
	if (begin >= end)
	{
		return;
	}
	int keyindex = _QuickSort4(begin, end, arr);//三数取中法，选择三数的中间数值
	QuickSort(begin, keyindex - 1, arr);
	QuickSort(keyindex + 1, end, arr);
}
	
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",arr[i]);
	}
	printf("n");
}
int main()
{
	int arr[] = {9,8,7,6,5,4,3,2,1,0,8};
	int n = sizeof(arr) / sizeof(arr[0]);
	QuickSort( 0, n - 1,arr);
	Print(arr, n);
	system("pause");
	return 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
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
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//hoare版本
void Swap(int* pa, int *pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void _QuickSort1(int left, int right, int *arr)
{
	int index = right;
	int key = arr[index];
	if (left >= right)
	{
		return;
	}
	//找比key大的数
	//找比key小的数
	//交换
	while (left < right)
	{
		while (left < right)
		{
			if (arr[left] >= key)
			{
				break;
			}
			++left;
		}

		while (left < right)
		{
			if (arr[right] < key)
			{
				break;
			}
			--right;
		}
		Swap(&arr[left], &arr[right]);	
	}
	Swap(&arr[left], &arr[index]);
	right = index;
	index = left;
	left = 0;
	_QuickSort1(left, index-1, arr); 
	_QuickSort1(index+1,right,arr);
}

//挖坑法
void _QuickSort2(int begin, int end,int * arr)
{
	if (begin >= end)
	{
		return;
	}
	int end1 = end;
	int index = end;
	int key = arr[index];
	
	while (begin <end)
	{	//将比key大的数放在坑里， 从左向右找
		while (begin < end)
		{
			if (arr[begin] > key)
			{
				arr[index] = arr[begin];
				index = begin;
				break;
			}
			++begin;
		}
		//将比key小的数放在坑里， 从右向左找
		while (begin < end)
		{
			if (arr[end] < key)
			{
				arr[index] = arr[end];
				index = end;
				break;
			}
			--end;
		}
	}
	arr[index] = key;//要将Key 放回到坑里
	_QuickSort2(0, index - 1, arr);//前半段
	_QuickSort2(index+1 , end1, arr);//后半段，一定要注意end动了，不要直接传end的值，不然会造成后半段，没有被遍历
	
}

//指针法
void _QuickSort3(int begin, int end, int * arr)
{
	if (begin >= end)
	{
		return;
	}
	int key = arr[end];
	int	cur = begin;
	int prev = cur - 1;
	while (cur < end)
	{
		if (arr[cur] < key && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	++prev;
	Swap(&arr[end], &arr[prev]);
	_QuickSort3(0, prev - 1, arr);
	_QuickSort3(prev + 1, end, arr);
}

void QuickSort1(int* arr, int n)
{
	
	//_QuickSort1(0, n - 1, arr);	//hoare法
	//_QuickSort2(0, n - 1, arr);	//挖坑法
	//_QuickSort3(0, n - 1, arr);	//指针法
}



int Mid(int begin, int end,int* arr)
 {
	int mid = (begin + end) >> 1;
	if (arr[begin] > arr[end])
	{
		if (arr[end] > arr[mid])
		{
			return end;
		}
		else
		{
			if (arr[begin] > arr[mid])
			{
				return mid;
			}
			else
			{
				return begin;
			}
		}
	}
	else
	{
		if (arr[mid] > arr[end])
		{
			return end;
		}
		else
		{
			if (arr[mid] > arr[begin])
			{
				return mid;
			}
			else
			{
				return begin;
			}
		}
	}
	
}

//指针法
int _QuickSort4(int begin, int end, int * arr)
{
	
	int keyindex = Mid(begin, end, arr);
 	Swap(&arr[keyindex], &arr[end]);
	int key = arr[end];
	int	cur = begin;
	int prev = cur - 1;
	while (cur < end)
	{
		if (arr[cur] < key && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	++prev;
	Swap(&arr[end], &arr[prev]);
	return prev;
}

void QuickSort(int begin,int end,int* arr)		//优化
{
	if (begin >= end)
	{
		return;
	}
	int keyindex = _QuickSort4(begin, end, arr);//三数取中法，选择三数的中间数值
	QuickSort(begin, keyindex - 1, arr);
	QuickSort(keyindex + 1, end, arr);
}
	
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",arr[i]);
	}
	printf("n");
}
int main()
{
	int arr[] = {9,8,7,6,5,4,3,2,1,0,8};
	int n = sizeof(arr) / sizeof(arr[0]);
	QuickSort( 0, n - 1,arr);
	Print(arr, n);
	system("pause");
	return 0;
}

3.结果展示

在这里插入图片描述

4.复杂度分析

和堆排序类似，时间复杂度 O(nlogN)
每次交换都开了一次空间存储Key,空间复杂度 O(logN)

5.优化问题

如果数组是目标数组的逆序，那么就不能实现相对均匀分割，快排就会退化成冒泡排序，所以我们采取三数取中法，让数组分割成为相对均匀的数组，再去遍历，效率会提高。算法的思路，找出数组中begin mid end 对应的值，选出中间值，然后和end的值交换，还是end位置上的数作为Key 。

6.心得体会

Hoare法，需要注意最后边为key时，左边要先走，不然就会出现问题。
在这里插入图片描述
挖坑法就不存在谁先走的问题。
指针法写起来非常简洁。
开始会觉得很难理解，逐步分解为单趟，然后递归这个过程，找出终止条件。需要注意的是begin大于等于end终止，因为存在keyindex+1 和end比较的情况，我最初这里没有考虑到，导致后半段直接没有被排序。