数据结构---快速排序_数据结构快速排序

数据结构—其他排序的方法（排序1）
链接: link.

1. 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。（简单点说就是：在一个给定的数组内，选取最左边或者最右边的数作为K值，然后把K值放在合适的位置，在升序的情况下保证左边的数都小于K，右边的数都大于K，然后在对K的左半边进行相似的过程类似于递归的形式，直到左右都有序，那么整体就有序）

1.1 hoare方法（左右指针法）

解题难点：

1.为了方便找K值，一般选取数组最左边的数，或者最右边的数（还可以优化）

2.让begin找比K大的值，end找比K小的值

3.保证让选K的相反方向那个先动先去找相应的数（如果选K在右边，就让begin先走，那么最终begin和end相遇的点一定是比K大的值，这样才能保证K值和这个位置的值交换，达到想要的效果：左边的都比K值小，右边的都比K值大）

那么为什么我选择K值在右边，我要让begin先去找比K大的值呢？这个先后的顺序是否可以改变？，我让右边的end先动，去找比K小的数来看一下

会发现此时begin和end相遇的位置的值，在和K值交换，K值并不在正确的地方（因为你的右边并不是都是比K大的值）

那么此时你的左边都比K值小，右边都比K值大，但是还并不是有序的，所以此时解题就相当于递归的形式，你的K值的左半边可以再选出一个K值，进行相同的思路，当你左半边都有序，右半边也有序的时候，整体就有序了，很像分治的思想。

1.1.1 时间复杂度的分析

当你所选择的K值每次都是中位数的时候（最好的情况），那么此时你的遍历相当于二叉树的前序遍历，树的高度就是logN（以2为底），那么你有N层，你的时间复杂度就是O(N*logN)，当你每次选的数都是最大或者最小的时候（最坏的情况）此时你的每层都接近N，那么时间复杂度就是O（N*N）,所以时间复杂度介于O(N * logN) ~O（N*N）

1.1.2 三数取中（优化快排）

这里就引出了一个优化，当你的一段已经接近有序或者就是有序的时候，你选择K值就会要么是最小要么是最大的值了，时间复杂度就是O（N*N），我希望选择的K值是接近中间的值，在选择K值过程中可能不会幸运的选择到接近中间的K值，但是最起码我要保证，他所选到的这个值一定不要是最小或者最大的。这样在一定程度上就避免了最坏的情况出现，并且可以保证在有序的情况下，会变为最优的情况

int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
			return mid;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else //a[begin] >a[mid]
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

*有了三数取中的优化，快排的时间复杂度不再考虑最坏的情况，而认为时间复杂符就是O（N * logN）

1.1.3 完整代码

//这里写的只是你选择一次K遍历整个数组出来的结果
int PartSort1(int* a, int begin, int end)
{
	//选出合适的中位数
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[midIndex], &a[end]);

	int keyIndex = end;
	while (begin < end)
	{
		//先让begin去找大于K的值
		while (begin<end && a[begin] <= a[keyIndex])
		{
			++begin;
		}

		//再让end去找比K小的值，此时在这里还要对end有限制条件，不然begin和end在内部循环的时候就错过了，而不是相遇停止
		while (begin<end && a[end] >= a[keyIndex])
		{
			--end;
		}
		Swap(&a[begin], &a[end]);
	}
	//此时你的begin和end在同一个位置了(选begin还是和end都是一样的)，在交换
	Swap(&a[begin], &a[keyIndex]);

	//此时你的begin和end所停留的位置就是K的正确位置
	return begin;
}

//快排
void QuickSort(int* a, int left, int right)
{
	assert(a);
	//if (left < right) //连等于的时候都可以不用排了，因为此时就剩下一个值了
	//{
	//	int div = PartSort1(a, left, right);
	//	//递归下去
	//	//[left, div - 1] div [div+1,right]
	//	QuickSort(a, left, div - 1);
	//	QuickSort(a, div + 1, right);
	//}

	if (left >= right)
		return;
	int div = PartSort1(a, left, right);
	//递归下去
	//[left, div - 1] div [div+1,right]
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}
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

1.2 挖坑法（重点解法便于理解）

这个在思想上和左右指针法基本一致，就是在理解的时候避免了为什么要让先让选K值相反方向的那个先走的思想过程。
挖坑法：先选择最左边或者最右边作为K，这里就假设选择最右边为K，此时把这个K值取出来以后，就相当于这个位置是一个坑，然后在最左边定义了一个begin去找大于K的值，然后把它拿去填坑，此时这个位置为一个坑，在最右边定义一个end让它去找小于K的值，然后在填到上一个坑，再让begin走，直到begin和end相遇的时候，选取这个坑填入K值

//挖坑法
int PartSort2(int* a, int begin, int end)
{
	//选出合适的中位数
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[midIndex], &a[end]);

	//最开始的坑
	int key = a[end];
	while (begin < end)
	{
		//让begin去找大于K的值 ,  
		//这里值得注意的就是一定要加=，因为当begin所走到的那个数如果此时和你的key值相等，要么留在左边，要么留在右边都可以
		//但是你不加，就会造成死循环
		while(begin < end && a[begin] <= key)
		{
			++begin;
		}
		a[end] = a[begin];

		//让end去找比K小的值
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[begin] = a[end];
	}
	//走到这里说明begin和end 相遇了，这里放上K的值
	a[begin] = key;
	return 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
31

1.3 前后指针法

定义一个prev和cur，让cur去找比key小的值，找到了就停下，然后++prev，在交换两个值，直到cur把数组都走完，在++prev，此时让prev处的值和key交换。（此时就是左边都小于key的值，右边都大于key的值）

如果写成好理解的，那么代码会很冗余。

//前后指针法
int PartSort3(int* a, int begin, int end)
{
	//选出合适的中位数
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[midIndex], &a[end]);
	
	int prev = begin - 1;
	int cur = begin;
	int keyIndex = end;
	while (cur <= end) //
	{
		//让cur去找小于K的值 ,但是你会发现有的时候你的cur和prev在同一个位置，所以可以不考虑交换
		if (a[cur] < a[keyIndex] && ++prev != cur)
			Swap(&a[prev], &a[cur]);

		//当a[cur]比a[keyIndex]小的时候，停下++完prev之后，cur要在++
		//当a[cur]比a[keyIndex]大的时候，直接++cur，所以宗的来说，都是要进行++cur的操作的，所以可以直接合并
		++cur;	
	}
	Swap(&a[++prev], &a[keyIndex]);
	return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.4 小区间优化

即使此时这里只剩下10个数不是有序的，依旧要递归下去，先选择一个K然后，左边排有序，右边排有序，最后让这10个数有序。其实对于递归来说这里就是多余的，可能不但不会帮你优化，然而搞的更加的复杂，因为在递归的过程中是需要不断的借用栈针的，可能当你需要排的这个数组是一个非常大的时候，栈空间会溢出，所以这里引入优化：当到达一定的数区间的时候，不再使用递归的方法，而是改用直接插入的方法来实现剩下的数排序，在时间上来说，基本不会有区别。

//插入排序
void InsertSort(int* a, int n)
{
	assert(a);
	//把第一个数当成有序的，然后拿后面的数据和第一个数据比较插入
	for (int i = 0; i < n - 1; ++i)
	{
		//可以把任何一种排序都分解开来为单步分析在整合整体的过程来思考问题
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0) //当这个tmp和第一个值相比较还是小的话，再次移动end就会发现他已经到-1的位置了，说明他依旧和所有的元素都比较过了
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		//这里跳出来会有两种可能，第一个就是tmp此时大于end下角标所在的元素，break出来
		//第二种就是while循环结束end已经到了-1的位置，（也就是比第一个值还要小）
		a[end + 1] = tmp;
	}
}

//快排
void QuickSort(int* a, int left, int right)
{
	assert(a);
	if (left >= right)
		return;
 //小区间优化--不再使用递归的方式，而是改用直接插入排序
	if ((right - left + 1) > 10)
	{
		int div = PartSort3(a, left, right);
		//递归下去
		//[left, div - 1] div [div+1,right]
		QuickSort(a, left, div - 1);
		QuickSort(a, div + 1, right);
	}
	else
	{
		//区间小于10个数的时候，不再使用递归，而是改用直接插入的方法
		//然而你这里需要排序的数组范围，不再是最初的，可能是此时递归到某一层的左右子树
		InsertSort(a + left, right - left + 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

1.5 快排的非递归

由于目前还没有学习到C++，所以还是需要手动的写一个栈，然后这里需要借助栈来实现快排的非递归。递归的本质就是借助栈针在保存参数，而这里实现的主要思想是：把栈针的区间保存到栈里面去

非递归的意义：

①因为递归递归建立栈针还是有消耗的，但是对于现代计算机，这个优化微乎其微，可以忽略。
②递归的最大缺陷是，如果栈针的深度太深，可能会导致栈溢出。因为系统栈空间一般不大在M级别，但是数据结构栈模拟非递归，数据是存储在堆上的，堆是G级别的。

void StackInit(Stack* pst)
{
	assert(pst);
	//这种方式是有不好的地方的，因为但当你需要增容的时候，你就会发现，他的capacity初始化是0，那么你乘2依旧是0，所以建议一开始就给一个固定值
	//pst->_a = NULL;
	//pst->_top = 0;
	//pst->_capacity = 0;
	pst->_a = (STDateType*)malloc(sizeof(STDateType)*4);
	pst->_top = 0;
	pst->_capacity = 4;
}

//销毁
void StackDestory(Stack* pst)
{
	assert(pst);
	free(pst->_a);
	pst->_a = NULL;
	pst->_top = pst->_capacity = 0;
}

//入栈
void StackPush(Stack* pst, STDateType x)
{
	assert(pst);
	//空间不够则增容
	if (pst->_top == pst->_capacity)
	{
		pst->_capacity *= 2;
		STDateType* tmp = (STDateType*)realloc(pst->_a, sizeof(STDateType)*pst->_capacity);
		if (tmp == NULL)
		{
			printf("内存不足\n");
			exit(-1);
		}
		else
		{
			pst->_a = tmp;
		}
	}
	pst->_a[pst->_top] = x;//你所定义的栈顶总是在你放入数据的下一个位置
	pst->_top++;
}

//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	assert(pst->_top > 0);
	--pst->_top;
}

//获取数据个数
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->_top;
}


//返回1是空，返回0是非空
int StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->_top == 0 ? 1 : 0;
}


//获取栈顶的数据
STDateType StackTop(Stack* pst)
{
	assert(pst);
	assert(pst->_top > 0);
	return pst->_a[pst->_top - 1];//你所定义的栈顶总是在你放入数据的下一个位置
}




//快排的非递归
void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);

	//先入右在入左
	//那么出的时候就会先出左在出右
	StackPush(&st, right);
	StackPush(&st, left);
	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);
		//此时相当于我们拿到这这段区间[begin,end]
		//先进行大区间单趟排
		int div = PartSort3(a, begin, end);
		//[begin,div-1] div [div+1,end]
		//原来是对[begin,div-1] 和[div+1,end]进行递归的操作，但是现在思路不变但换成用栈来实现
		//这里为了好理解对照着二叉树的前序遍历的思想，选择了先入右在入左，这样出栈以后就可以先堆最左边区间进行操作
		//入右边
		if (div + 1 < end)//当你是一个数的时候就相当于有序了，不再入栈了
		{
			StackPush(&st, end);
			StackPush(&st, div+1);
		}
		//入左边
		if (begin < div - 1) 
		{
			StackPush(&st, div-1);
			StackPush(&st, begin);
		}
	}
	StackDestory(&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

1.6 快速排序的特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定