3.2-1 快速排序（交换排序的一种）

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

1.hoare版本

交换排序链接这篇博客的链接有讲hoare版本的排序方法。

具体代码内容：

//1. hoare版本
int PartSort1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int keyi = left; #当药匙的下标位置。

	while (left < right)
	{
		//右边先走，找小
		while (left < right && a[right] >= a[keyi])
			--right;
		//左边再走，找大
		while (left < right && a[left] <= a[keyi])
			++left;

		Swap(&a[right], &a[left]);

	}
	Swap(&a[keyi], &a[left]);

	keyi = left;
	return keyi;
}

void QuickSort(int* a, int begin, int end)
{
	assert(a);

	if (begin >= end)
		return;

	int keyi = PartSort1(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 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
35
36
37
38

2.挖坑法（注意挖坑法要记住药匙的值而不是下标，坑会变）。

方法刨析：首先我们知道快速排序第一步要确定药匙（key）这个位置的下标 这个位置我们当成一个（pit）坑（也就是把这个数当成分割线，定区间），我们通过两个下标（left和right）来查找。right从右到左来找比key这个数小的，然后把比key小的数填到pit（坑）中，然后right此时的下标位置就是一个新的pit；轮到left从左往右来找比key值大的数，找到后把比key这个数大的填到pit中；left和right都走完后，这个坑就填key这个值。此时以key这个位置分成两个区间，这个时候轮到递归。

我们先看代码，后面会有图演示：

int PartSort2(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int key = a[left];
	int piti = left;

	while (left < right)
	{
		//右边先走，找小
		while (left < right && a[right] >= key)
			--right;
		a[piti] = a[right];
		piti = right;

		//左边再走，找大
		while (left < right && a[left] <= key)
			++left;
		a[piti] = a[left];
		piti = left;

	}
	
	a[piti] = key;
	return piti;

}


void QuickSort(int* a, int begin, int end)
{
	assert(a);

	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 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
35
36
37
38
39
40
41
42

图形讲解：

while (left < right)
	{
		//右边先走，找小
		while (left < right && a[right] >= key)
			--right;
		a[piti] = a[right];
		piti = right;

		//左边再走，找大
		while (left < right && a[left] <= key)
			++left;
		a[piti] = a[left];
		piti = left;

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

依次类推到left<right,这个条件不成立。

while (left < right)
		//右边先走，找小
1
2

此次轮到 a[piti] = key

a[piti] = key;
1

调试后的结果：
在这里插入图片描述

3. 前后指针版本（注意药匙的下标就是prev的下标）

方法刨析：首先还是老样子，先找药匙的下标位置（keyi）。我们现在还需要两个变量（prev和cur，cur的初始位置再pre后面–就是pre下标加一就是cur的下标的位置），这个与前面的有所不同；我们只要知道我们通过prev和cur下标位置的值交换 来保证小于药匙的值移到前面，大的移到后面。（具体就是cur一直往后移动，遇到比keyi下标值小的 停下来 ，cur与pre下标加1后（注意不是prev这个位置的值） 所处位置的值交换；最后cur超过下标范围停止。）此时以keyi(就是prev)这个位置分成两个区间，这个时候轮到递归。

我们先看代码，后面会有图演示：

//3. 前后指针版本
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = prev + 1;
	int keyi = begin;


	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)#当prev加一后位置与cur相同的时候不交换，交换其实也可以。
			Swap(&a[cur], &a[prev]);
	  /*if (a[cur] < a[keyi])
		{
			++prev
			Swap(&a[cur], &a[prev]);
		}*/

		++cur;
	}
	Swap(&a[prev], &a[keyi]);

	keyi = prev;
	return keyi;
}


void QuickSort(int* a, int begin, int end)
{
	assert(a);

	if (begin >= end)
		return;

	int keyi = PartSort3(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 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
35
36
37
38
39
40
41

图形讲解：

while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)#当prev加一后位置与cur相同的时候不交换，交换其实也可以。
			Swap(&a[cur], &a[prev]);

		++cur;
	}
1
2
3
4
5
6
7

end是数组最大下标。
比keyi下标位置大的往后退，小的往前移。

调试第一堂结果:

3.2-2 快速排序优化

1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序（当我们要排序的数有十万个，当递归的到每一块的数字为20的时候我们可以用插入排序—原因：我们可以减少%70-%80的递归次数，还可以防止递归到深处栈溢出。）

三数取中法选key

在一个范围内找最中间的当药匙，这样我们可以减少递归次数，有时候给你一个数组接近有序，可能你选的药匙下标是最大值或最小值，而这个方法出现这种概率几乎没有。

这个很简单 例如：下标0到 9 这十个数中选 0 9 4这三个下标 中 选中间的那个值（注意：不是下标）。

代码内容：

int GetMidIndex(int* a, int left, int right)
{
	int midi = left + (right - left)/2;

	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
		{
			return midi;
		}//a[mid] > a[right] 可以看为a[mid]最大。
		else if (a[right] > a[left])  
		{
			return right;
		}
		else
		{
			return left;
		}
		
	}
	else  //a[left] >= a[mid]
	{
		if (a[midi] > a[right])
		{
			return midi;
		}//a[mid] < a[right] 可以看为a[mid]最小。
		else if (a[right] < a[left])
		{
			return right;
		}
		else
		{
			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
37

3.2-3 快速排序非递归

方法分析：我们需要借助栈（在堆上开辟的）的性质–先进后出（我们可以从左到右类似递归的方式处理。）；而队列不能实现。cpp有专门的库函数，c没有。我们通过先存后区的方式实现。

栈链接

先看代码后分析：

void QuickSortNonR(int* a, int begin, int end)
{
	assert(a);
	
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st))//里面：如果栈为空StackEmpty(&st)返回Ture（真）。
	{
		int left = StackTop(&st);
		StackPop(&st);

		int right = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(a, left, right);
		// left keyi right。

		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}

		if (keyi - 1 > left)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}

	StackDestroy(&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

创建栈，先存头和尾。

ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);
1
2
3
4

出栈

		int left = StackTop(&st);
		StackPop(&st);//删除

		int right = StackTop(&st);
		StackPop(&st);//删除

1
2
3
4
5
6

确定区间范围

int keyi = PartSort3(a, left, right);
//[left, keyi-1]  keyi   [keyi+1, right]
1
2

如果keyi-1小于keyi入栈， keyi+1大于keyi入栈

if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}

		if (keyi - 1 > left)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
1
2
3
4
5
6
7
8
9
10
11

while (!StackEmpty(&st))
{}//里面的内容相当于递归  往后栈图依次类推。
1
2

当然最后不要忘了销毁栈。

StackDestroy(&st);
1