快速排序(霍尔划分）_快速排序霍尔划分

快速排序

大家看到快速排序，想必都会觉得此类排序方法很快吧。的确，该种算法排序效率比较高。那么，什么是快速排序呢？
在快速排序中，选择一个基准值，后，遍历这个数列，通过一定的划分算法，将基准值放到合适的位置，若是升序排序，则基准值的前面全部是小于基准值的数，其后全是大于基准值的数，即通过一趟快速排序后，基准值找到了自己合适的位置，继续递归进行快速排序，直到整个数列变成有序。
快速排序其一的划分为霍尔划分，接下来我们就看看霍尔划分是如何实现的吧

霍尔划分

选定一个基准值，规定begin指向最左边的值，end指向最右边的值。从end向前找第一个小于基准值的数，找到后，再从begin向后寻找第一个大于基准值的数，此时交换两个数后，继续从此刻end的位置向前找第一个小于基准值的数，再从begin位置向后找第一个大于基准值的数，找到后，两数进行交换，重复如此，直到end和begin相遇，再交换end与begin相遇的值和基准值，此时，一趟快速排序便结束了，基准值也就找到了自己合适的位置，基准值的左右两边又是新的无序序列，这时只需要递归的进行快速排序即可，便于理解，上图

比如这个无序数列，我们选定28为基准值，则begin和end的位置如上图，此刻我们开始进行霍尔划分如下图

我们从后向前找到一个小于28的数是5，再从前向后找第一个大于28的数是32，所以我们交换这两个数。继续寻找满足要求的两个数交换，如下

同样的2和60也满足条件我们交换后如上图下方所示。这时我们继续使end向前找，发现begin和end重合，那这时我们便将基准值和该值交换，如下图

我们这时可以发现，基准值即28的左边全部是小于28的数，它的右边全部是大于它的数，此时一趟快速排序便结束了，只需要对左右两边递归进行快速排序即可。
如果大家理解了，我们看看代码如何写

首先，这个划分算法要用到交换函数，同样我们先写一个交换函数
交换函数

void swap(itn* array,int left,int right)
{
	int tmp = array[left];
	array[left] = aray[right];
	array[right] = tmp;
}
1
2
3
4
5
6

霍尔划分

int houlepartion(int* array,int begin,int end)//这里的begin是数列第一个元素的下标，end是数列最后一个元素的下标
{
	int key = array[begin];//选定基准值，这里的基准值我选定为数列第一个元素
	int start = begin;//记录基准值的位置
	while(begin<end)
	{
		//从后向前找第一个小于基准值的数
		while(begin<end&&array[end] >= key)
			end--;
		//从前向后找第一个大于基准值的数
		while(bengin<end&&array[begin] <= key)
			begin++;
		swap(array,begin,end);//找到后交换这两个数
	}
	//跳出上面循环时，即end和begin相遇，我们交换基准值和当前位置
	swap(array,start,begin);
	//返回基准值现在的位置，方便递归调用
	return begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

霍尔划分写完后，我们便需要写个递归函数，递归进行霍尔划分即可。首先，我们要知道，递归跳出的条件是什么？如果我们一直霍尔划分下去，那么最小的一个数列相当于只有一个数，那么此刻的begin和end是同一个值，那么我们此刻便可以向上级返回。知道了递归结束条件后，我们便可以写出该递归函数

void quicksort(int* array,int begin,int end)
{
	//递归跳出条件
	if(bengin >= end)
		return ;
	//记录基准值的当前位置
	int keypos = houlepartion(array,begin,end);
	quicksort(array,begin,keypos - 1);//递归排序基准值之前的无序数列
	quicksort(array,keypos + 1,end);//递归排序基准值之后的无需数列
}
1
2
3
4
5
6
7
8
9
10

注意，我们再传参数的时候，一定要记住传入的是无序数列的第一元素的下标和最后一个元素的下标，比如5，6，2，12，16，28，3这个无序数列，我们知道该数列size=7，那么我们的快排接口应该为quicksort(array,0,size - 1)
霍尔划分讲到这里就结束了，大家下去可以自行写写哦！