【C++】——快速排序（前后指针，挖坑法，快慢指针法）_用指针排序c++

一、前后指针法

基本思路：
1．将数组的第一个数a[left]作为基准数key。
2．分区过程:right开始向前找比key小的数（end找小）;数组的首元素left开始向后找比key大的数（begin找大）；找到后然后两者交换（swap）,直到begin >= end终止遍历。最后将begin和最后一个数交换（ 这个时候end不是最后一个位置），即 key作为中间数（左区间都是比key小的数，右区间都是比key大的数）
3．再对左右区间重复第二步，直到各区间只有一个数。

 void QuickSort(int* a, int begin, int end)
{
	if (begin < end)
	{
		int left = begin;
		int right = end;
		int temp = a[left];
		while (left != right)
		{
			while (left < right&&a[right] >= temp)
				right--;
			while (left < right&&a[left] <= temp)
				left++;
			swap(a[left], a[right]); 
		}
		swap(a[left], a[begin]);
		QuickSort(a, begin, left-1);
		QuickSort(a, left + 1, end);
	}
}
void print(int* a)
{
	for (int i = 0; i < 6; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
int main()
{
	int a[6] = { 9,5,7,6,8,0 };
	cout << "左右指针法：" << endl;
	QuickSort(a, 0, 5);

	print(a);
	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

二、挖坑法

挖坑法的快排跟前后指针法很相似
基本思路：
定义两个指针left指向起始位置，right指向最后一个元素的位置,然后指定一个基数key（right）,作为坑
left寻找比基数（key）大的数字，找到后将left的数据赋给right，left成为一个坑，然后right寻找比基数（key）小的数字，找到将right的数据赋给left，right成为一个新坑，循环这个过程，直到begin指针与end指针相遇，然后将key返回给那个坑（最终：key的左边都是比key小的数，key的右边都是比key大的数），然后进行递归操作。

//挖坑法的快排
void partSort(int* arr, int left, int right)
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		int temp = arr[end];  //三数取中

		while (begin != end)
		{
			while (begin < end&&arr[begin] <= temp)
				begin++;
			if (begin < end)
				arr[end] = arr[begin];  //begin成为新坑 
			while (begin < end&&arr[end] >= temp)
				end--;
			if (begin < end)
				arr[begin] = arr[end];
		}
 		arr[begin] = temp;
		partSort(arr, left, begin-1);
		partSort(arr, begin + 1, right);
	}
	
}
void print(int* a)
{
	for (int i = 0; i < 6; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
int main()
{
	int a[6] = { 2,5,1,6,8,0 };
	cout << "挖坑法的快速排序:" << endl;
	partSort(a, 0, 5);
	print(a);
	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

三、前后指针法

基本思路：
定义两个指针，一前一后，cur（前）指向起始位置，prev（后）指向cur的前一个位置；选择数组最后一个元素作为key（right）
实现过程：cur找比key小的数，prev在cur没有找到的情况下，一直不动（即保证prev一直指向比key大的数）；直到cur找到比key小的数（+ +prev && prev != cur时）然后++cur,prev仍然不动。
直到cur走到right前一个位置，终止循环。最后++prev，交换prev和right的值

//前后指针法
void PartSort3(int* a, int begin, int end)
{
	if (begin <= end)
	{
		int temp = a[end];
		int cur = begin;
		int prev = begin - 1;
		while (cur < end)
		{
			if (a[cur] < temp&&++prev != cur)
			{
				swap(a[cur], a[prev]);
			}
			++cur;
		}
		prev++;
		swap(a[cur], a[prev]);
		PartSort3(a, begin, prev - 1);
		PartSort3(a, prev+1, end);
	}
}
void print(int* a)
{
	for (int i = 0; i < 6; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
int main()
{
	int a[6] = { 9,5,7,6,8,0 };
	cout << "前后指针法：" << endl;
	PartSort3(a, 0, 5);

	print(a);
	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

快速排序使用的场景是数据量大并且杂乱的序列，避免出现最坏的情况（为了让效率变得更高，使用了三数取中法，在数字大小小于10的时候，用直接插入排序，减少栈帧）

其中：

• 快速排序最优的情况：当关键词位于序列正中间的时候
• 快速排序最坏的情况：对已经有序的序列进行排序
• 时间复杂度：O(N^2)最差，O（N*lgN）最好
• 空间复杂度：O(1)
• 稳定性：不稳定