【快速排序】（C语言实现）_快速排序c语言

一. 递归实现

1. 快排是什么？

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

2.实现快排的三种方式

a.挖坑法

单趟的图形演示：(红色为坑)

挖坑法的单趟排序的基本步骤如下：
（1）选出一个数据（一般是最左边或最右边得）作为key,并且在改数据位置形成一个坑。
（2）定义两个变量begin和end,begin从左向右走，end从右向左走。（若坑在左边，则end先走；若坑在右边，则begin先走）
（3）在end走的过程中，如果遇到比key小的数，停下来，把该位置的数放到坑里，然后把该位置更新为新坑。
（4）然后begin开始走，如果走的过成中遇到比key大的数，停下来，把该位置的数放到坑中，然后把该位置更新为新坑。

反复执行（3）（4）直到begin和end相遇，相遇的位置一定是一个坑，然后把key放入坑中。

经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key。

然后也是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。
 
代码实现：

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;
	//三数取中
	//int midIndex = GetThreeMid(a,begin,end);
    //Swap(&a[begin],&a[midIndex]);
	int pivot = begin;
	int key = a[begin];
	
	while (begin < end)
	{
		//右边找小的，如果不是小于key,继续
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		//找到比key小的，把它放在坑里，换新坑
		a[pivot] = a[end];
		pivot = end;
		//左边找大的，如果不是大于key,继续
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		//找到比key大的，把它放在坑里，换新坑
		a[pivot] = a[begin];
		pivot = begin;
	}
	
	a[pivot] = key;//bengin 与 end 相遇，相遇的位置一定是一个坑
	QuickSort1(a, left, pivot - 1);
	QuickSort1(a, pivot + 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

b.左右指针法

单趟的图形演示：

左右指针法的单趟排序的基本步骤如下：
（1）选出一个key，一般是最左边或是最右边的。
（2）定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要begin先走）。
（3）在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和end的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）

经过一次单趟排序，最终使得key左边的数据全部都小于key，key右边的数据全部都大于key。

然后我们在将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，因为这种序列可以认为是有序的。
 代码实现：

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;
	//三数取中
	//int midIndex = GetThreeMid(a,begin,end);
    //Swap(&a[begin],&a[midIndex]);
	int keyi = begin;
	while (begin < end)
	{

		while (begin < end && a[end] >= a[keyi])
		{
			end--;
		}
		while (begin < end && a[begin] <= a[keyi])
		{
			begin++;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[keyi], &a[begin]);
	QuickSort2(a, left, begin - 1);
	QuickSort2(a, begin + 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

c.前后指针法

单趟的图形演示：

前后指针法的单趟排序的基本步骤如下：
（1）选出一个key，一般是最左边或是最右边的。
（2）起始时，prev指针指向序列开头，cur指针指向prev+1。
（3）若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur指针越界，此时将key和prev指针指向的内容交换即可。

经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。

然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

代码实现：

void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left, end = right;
	//三数取中
	//int midIndex = GetThreeMid(a,begin,end);
    //Swap(&a[begin],&a[midIndex]);
	int keyi = begin;
	int prev = begin;
	int cur = prev + 1;
	
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	QuickSort3(a, left, prev - 1);
	QuickSort3(a, prev + 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

d.快速排序的两个优化

（1）三数取中
如果不加三数取中，我们不能保证每次取到的key的值一定是在整个数组的中间位置，假设我们碰巧，key在每一趟排序中，都可以选到中间大小的值，那么我们来算算它的时间复杂度。

如果我们运气不好，每次的key都为头，我们再来算算他的时间复杂度。

对比上面两个key位置不同的的时间复杂度，显而易见，当key在中间位置一点的时候，算法效率高。所以我们要想办法，尽量要使key取在中间位置，这个时候就要用到三数取中了，三数取中就是在数组的头尾中间选择中间大小的那个值作为key，然后把它与数组的首元素位置进行交换。

代码实现：

//三数取中
 int GetThreeMid(int* a, int left, int right)
 {
	 int mid = (left + right) / 2;
	 if (a[mid] > a[left])
	 {
		 if (a[right] > a[mid])
			 return mid;
		 else if (a[left] > a[right])
			 return left;
		 else
			 return right;
	 }
	 else
	 {
		 if (a[left] < a[right])
			 return left;
		 else if (a[right] < a[mid])
			 return mid;
		 else
			 return right;
	 }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

然后把它与数组的首元素位置进行交换

int midIndex = GetThreeMid(a,begin,end);
Swap(&a[begin],&a[midIndex]);
1
2

(2)小区间优化
 我们可以看到，就算是上面理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以2倍的形式快速增长。
 为了减少递归树的最后几层递归，我们可以设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，而且待排序列的长度越长，该效果越明显。

void QuickSortTop(int* a, int left, int right)
{
	if (left >= right)
	{
		return;//如果只有一个数，直接返回。
	}
	if (right - left + 1 > 10)//可自行调整
	{
		QuickSort1(a, left, right);
		//QuickSort2(a, left, right);
		//QuickSort3(a, left, right);

	}
	else//当序列长度小于等于10是，使用堆排序
	{
		HeapSort1(a, right - left + 1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

点一点学 堆排序.

二.非递归实现

1.三种方法的单趟实现代码

a.挖坑法

//1.挖坑法
 int QuickSortPlay1(int* a, int left, int right)
 {
	 if (left >= right)
	 {
		 return;//当只有一个数，直接返回
	 }
	 int begin = left;
	 int end = right;
	 //三数取中
	 int midIndex = GetThreeMid(a, begin, end);
	 Swap(&a[begin], &a[midIndex]);
	 int pivot = begin;
	 int key = a[begin];
	 while (begin < end)
	 {
		 //右边找小的，如果不是小于key,继续
		 while (begin < end && a[end] >= key)
		 {
			 end--;
		 }
		 //找到比key小的，把它放在坑里，换新坑
		 a[pivot] = a[end];
		 pivot = end;
		 //左边找大的，如果不是大于key,继续
		 while (begin < end && a[begin] <= key)
		 {
			 begin++;
		 }
		 //找到比key大的，把它放在坑里，换新坑
		 a[pivot] = a[begin];
		 pivot = begin;
	 }
	 a[pivot] = key;//最后相遇一定是在坑相遇
	 return pivot;
 }

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

b.左右指针法

//2.左右指针 
 int QuickSortPlay2(int* a, int left, int right)
 {
 
	 if (left >= right)
	 {
		 return;//当只有一个数，直接返回
	 }
	 int begin = left;
	 int end = right;
	 //三数取中
	 int midIndex = GetThreeMid(a, begin, end);
	 Swap(&a[begin], &a[midIndex]);
	 int keyi = begin;
	 
	 while (begin < end)
	 {
		 while (begin < end && a[end] >= a[keyi])
		 {
			 end--;
		 }
		 
		 while (begin < end && a[begin] <= a[keyi])
		 {
			 begin++;
		 }
		 
		 Swap(&a[begin], &a[end]);
	 }
	 
	 int meet = begin;//begin与end的相遇点
	 Swap(&a[keyi], &a[meet]);//交换key和相遇点的值
	 return meet;
 }
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

c.前后指针法

//3.前后指针
 int  QuickSortPlay3(int* a, int left, int right)
 {
	 if (left >= right)
	 {
		 return;//当只有一个数，直接返回
	 }
	 int begin = left;
	 int end = right;
	 //三数取中
	 int midIndex = GetThreeMid(a, begin, end);
	 Swap(&a[begin], &a[midIndex]);
	 int keyi = begin;
	 int prev = begin;
	 int cur = prev + 1;
	 while (cur <= end)
	 {
		 if (a[cur] < a[keyi] && ++prev != cur)
		 {
			 Swap(&a[cur], &a[prev]);
		 }
		 cur++;
	 }
	 Swap(&a[keyi], &a[prev]);
	 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
24
25
26

d.非递归实现快排

快速排序的非递归算法基本思路：
 1、先将待排序列的最后元素的下标和第一个元素的下标入栈。
 2、当栈不为空时，读取栈中的信息（一次读取两个：前一个是begin，后一个是end），然后调用某一版本的单趟排序，排完后获得了key的下标pivot，然后判断key的右序列和左序列是否还需要排序，若还需要排序，就将相应序列的end和begin依次入栈；若不需排序了，就不需要将该序列的信息入栈。
 3、反复执行步骤2，直到栈为空为止。
 如果不理解栈点一点 栈.

void QuickSortNonR(int* a, int left, int right)
{
	ST st;//创建栈
	InitStack(&st);//初始化栈
	int begin = left;
	int end = right;
	StackPush(&st, end);//待排序列的end
	StackPush(&st, begin);//待排序列的begin 
	while (!StackEmpty(&st))
	{
		begin = StackTop(&st);//读取待排序列的begin
		StackPop(&st);//出栈
		end = StackTop(&st);//读取待排序列的end
		StackPop(&st);//出栈
		//int pivot = QuickSortPlay1(a, begin, end);//调用单趟排序函数
		//int pivot = QuickSortPlay2(a, begin, end);//调用单趟排序函数
		int pivot = QuickSortPlay3(a, begin, end);//调用单趟排序函数
		if (pivot + 1 < end)//该序列的右序列还需要排序
		{
			StackPush(&st, end);//右序列的end入栈
			StackPush(&st, pivot + 1);//右序列的begin入栈
		}
		if (begin < pivot - 1)//该序列的左序列还需要排序
		{
			StackPush(&st, pivot - 1);//左序列的end入栈
			StackPush(&st, begin);//左序列的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