【数据结构初阶】--- 快速排序

一、递归的整体思路

整体思路：
每次固定一个数的位置
默认当前范围的第一个数就是要固定的数
比它大的放左边，比它小的放右边

递归

分析：

每次固定好一个数的位置后，去左区间固定一个数，右区间固定一个数，以此类推，直到要固定数的范围只剩一个数或范围不存在就停止
begin == end表示这个范围只有一个数，begin>end表示范围不存在
PartSort这个函数的功能是：从当前范围中固定好一个数的位置，并返回固定后的位置下标，具体如何实现这个功能，下面右三种方法

代码示例：

void QuickSort(int* a, int begin, int end)
{
	if(begin>=end)
	return;
	
	int keyi = PartSort(a,begin,end);
	QuickSort(a,begin,keyi-1);
	QuickSort(a,keyi+1,end);
}
1
2
3
4
5
6
7
8
9

二、固定好一个位置的三种方法

1. hoare版本

具体步骤：

1. 先从范围最后一个位置开始找比a[keyi]小的值，找到就停下；再从最开始的位置找比a[keyi]大的值，找到就停下；交换这两个值。
2. 重复步骤1，直到左边和右边相遇或右边和左边相遇（left == right）停止，此时left这个位置的值是小于a[keyi]的
3. 最后，交换a[keyi]和a[left]的值，再令keyi = left;此时a[keyi]就被固定在它排序好的位置

初版代码示例：

根据上面步骤，演示代码

//haore
int PartSort1(int* a, int left, int right)
{
	int keyi = left;

	while (left < right)
	{
		//右边找小
		while (a[right] > a[keyi])
		{
			right--;
		}
		//左边找大
		while (a[left] < a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	keyi = left;
	return keyi;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意：

• 问题1：死循环
  

如果左右两边都有等于a[keyi]的值,这时left和right都会停下，然后交换，交换后继续找大或找小，但left和right仍然不动，继续交换，一直重复这个操作，成为死循环
解决方法：
遇到等于a[keyi]就继续++/–
右边找小的条件：a[right]>=a[keyi]
左边找大的条件：a[left]<=a[keyi]

• 问题2：越界
  

极端情况下，这个范围里的值刚好是升序的，right先走，一直找小，找不到，来到了left的位置，依然没找到，所以right继续走，走到了left前面的位置，此时right就已经越界，Swap(&a[left],&a[right])时就会非法访问
解决方法：
right和left每次找值的时候先判断是否已经相遇，若相遇就不今小循环
增加的条件left<right

修改后的代码示例：

修改后的代码：

//haore
int PartSort1(int* a, int left, int right)
{
	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]);
	keyi = left;
	return keyi;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

如何保证相遇位置一定比a[keyi]小

两种方案：

1. 最左边的值做key,右边先走，保障了相遇位置的值比a[keyi]小
2. 最右边的值做key,左边先走，报章了相遇位置的值比a[keyi]大

根据方案1分情况讨论：
右边先走：L遇R，R遇L

• 情况一：L遇R
  此时R已经走过了，并且停下的位置的值小于a[keyi]，那么L遇R的位置就比a[keyi]小
• 情况二：R遇L
  1. L没动： R遇L可能是R第一次走，一次性就到L，L还没动，这时相遇的位置就是L的初始位置keyi
  2. L动了： R遇L，L已经走过了，说明L已经找到了大并且与R进行了交换，交换后的L的值是小于a[keyi]的，所以R遇L的位置的值比a[keyi]小

2. 挖坑法

思路：

1. 将范围最左边的值作为坑hole，用key将a[left]的值保存起来
2. 右边先走，找小，找到后将right位置上的值赋给hole的值,再更新坑hole的位置，hole = right;左边找大，找到后将left位置上的值赋给hole的值，再更新坑hole的位置，hole = left。
3. 重复步骤2，直到左右相遇，相遇的位置就是坑hole，将key的值赋给这个坑，结束

代码示例：

//挖坑法
int PartSort2(int* a, int left, int right)
{
	int key = a[left];//先将要固定的值保存起来
	int hole = left;
	while (left < right)
	{
		//右边找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		//更新坑的位置
		a[hole] = a[right];
		hole = right;
		//左边找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		//更新坑位置
		a[hole] = a[left];
		hole = left;
	}
	//最后坑的位置就是要固定的值的位置
	a[hole] = key;
	return hole;
}
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

3. 前后指针法

思路：

1. 先定义两个下标prev、cur，prev指向范围中最左边的值，cur指向prev的下一个值
2. cur找小，遇到大于等于key的直接cur++；遇到小于key的，先++prev，再将prev和cur位置的值进行交换，cur++。
3. 重复步骤2，直到cur走出这个范围，此时prev指向的是所有大于key位置的前一个，最后交换prev和keyi位置的值

分析

1. 当cur遇到比key大的值后，cur++，prev不动
2. 当cur遇到比key小的值后，与++prev的位置交换，把小于key的值移到左边，大于可以的值移到右边，相当于把大于key的值向右推

代码示例：

//前后指针法
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)
	{
		//cur找小，与++prev交换
		if (a[cur] < a[keyi] && ++prev != cur)//++prev != cur是一点优化，针对prev和cur之间没有大于a[keyi]的值时的原地交换
		{
			Swap(&a[prev], &a[keyi]);
		}
		//if (a[cur] < a[keyi])
		//{
		//	++prev;
		//	Swap(&a[prev], &a[keyi]);
		//}
		//无论a[cur]大于小于还是等于a[keyi]，cur都++
		cur++;
	}
	//prev指向的是所有大于a[keyi]的前一个位置
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}
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

三、非递归思路

思路:

用栈模拟递归的过程

1. 先将最开始的范围分别压入栈中，压两次，先压右边界，再压左边界
2. 一次弹出两个值，表示一个范围，在该范围中固定好一个值的位置，然后将这个值的右区间的两个边界值入栈，再将左区间的两个边界入栈
3. 重复步骤2，直到栈为空停止，最后销毁栈

代码示例：

//快排非递归方法
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);

	//将左右区间压入栈中
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		//弹出左右范围
		int leftrange = STTop(&st);
		STPop(&st);
		int rightrange = STTop(&st);
		STPop(&st);

		//在这个范围中固定好一个值
		int keyi = PartSort1(a, leftrange, rightrange);

		//先压右后压左区间是为了模拟递归的调用过程
		//如果keyi的右区间的个数至少大于一个就说明还需要固定值，所以压栈
		if (keyi + 1 < rightrange)
		{
			STPush(&st, rightrange);
			STPush(&st, keyi + 1);
		}
		//如果keyi的做区间的个数至少大于一个就说明还需要固定值，所以压栈
		if (keyi - 1 > leftrange)
		{
			STPush(&st, keyi - 1);
			STPush(&st, leftrange);
		}
	}
	STDestory(&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

四、时间复杂度分析

最好的情况，每次要固定的位置都在最中间，这样的时间复杂度是O(N*logN)
最坏的情况，要排的本来就是升序，每次要固定的位置都在最左边，时间复杂度是O(N²)
时间复杂度与选的key是有关的，这个key越靠近中间位置，时间复杂度越小
解决方案：

1. 随机数选key
2. 三数取中

五、对递归法的优化

由于快排的时间复杂度跟每次选的key值有关，如果每次固定的值刚好是最小值，那么快排的速度就会非常慢，几乎是O(N²)级别
这种情况的例子就是有序
那么如何在有序或接近有序的情况让快排的速度提高呢？
三数取中

三数取中

在当前范围中选取左边界，中间和右边界三个数，比较大小，将中间的值作为key，与左边界的值进行交换，然后再进行固定key的操作

//快排的优化：三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return right;
		}
		else //a[left]>a[mid], a[left]<a[right]
		{
			return left;
		}
	}
	else //a[mid]>a[left]
	{
		if(a[right]>a[mid])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return right;
		}
		else //a[mid]>a[left], a[left]>a[right]
		{
			return left;
		}
	}
}
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

三路分化

当要排的数据含有大量重复的值甚至全部一样，我们的快排就会被克制，

每次确定一个值的位置，但按照上图的过程进行下去，最后的时间复杂度到达O(N²)，为了保证遇到这类情况也会很快的解决，使用三路划分即可
思路：
将小于key的值弄到左侧，大于key的值弄到右侧，等于key的值弄到中间，这样排一次就可以固定好多个等于key值的值

三个指针l,r,cur;l指向左边界，r指向右边界，cur指向l的下一个位置

步骤：

1. 当a[cur]<key，交换cur、l位置的值，cur++，l++；
2. 当a[cur]>key，交换cur、r位置的值，r–；
3. 当a[cur]==key，cur++；
4. 直到cur大于r时停止，再将左区间(left,l-1)，右区间(r+1,right)进行递归

分析：

1. l指向的是等于key值的最左边的位置，r指向的是大于key值的组左边的位置
2. cur和l之间是等于key的值
3. cur找到小后与key交换的目的是将小于key的值移到左侧，等于key的值向中间移动，交换后的a[cur]是等于key的值，所以cur++，交换后的a[l]是小于key的值，所以l++,指向等于key值的最左边的位置
4. cur找到大于key的值后与r位置的值交换，交换后，a[r]的值大于key，r–指向大于key值的最左边的位置；此时a[cur]的值是不知道的，因为交换前的a[r]与key的大小关系并不清楚，所以现在的a[cur]需要判断，不能++

本质：

1. 小的甩到左边，大的甩到右边
2. 跟key相等的只推到中间

代码实现：

//快排的优化：三路划分
void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int l = begin;
	int r = end;
	int cur = begin + 1;
	int key = a[begin];
	while (cur <= r)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[l]);
			cur++;
			l++;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[r]);
			r--;
		}
		else
		{
			cur++;
		}
	}

	QuickSort2(a, begin, l - 1);
	QuickSort2(a, r + 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