快速排序是一种交换排序，交换就是根据序列中的两个记录键值的比较结果来兑换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

hoare版本

我们选择最左边的作为一个Key值，left和right分别记录的是数组的下标，我们让右边的先往左走，到遇到一个比a[key]的值的时候停止

接下来我们让左边的再走，当遇到一个比a[key]大的值的时候停止

 此时此刻我们将左右的两个值进行交换，然后继续走右边的right,遇到一个比a[key]的值要小的

 接下来走left，遇到一个大于a[key]的将其与a[right]进行交换

之后再次走right，最终会与left相遇，那么此时交换a[key]与a[left]或者a[right],此时left与right指向同一个位置 

 此时此刻，整个数组就分为了三部分【a[0]，a[left(right)-1]】a[left(right)]【a[left(right)+1]，a[n]】,那么左半部分的数都是比key要小的，有半部分是比key要大的，注意，此时左右两边部分并不是有序的

接下来我们实现一下这个代码

​int Partion1(int* a, int left, int right)
{
    int key = left;
	while (left < right)
	{
		while ( a[right] > a[key])
		{
			right--;
		}
		while ( a[left] < a[key])
		{
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[left], &a[key]);
	return left;
​}

但是我们明显的发现我们的代码有问题，我们没有考虑完全，要是这个数组是这个样子的呢？

a = [5,5,5,5,5];

那么便不会发生交换，所以我们修改为

​int Partion1(int* a, int left, int right)
{
    int key = left;
	while (left < right)
	{
		while ( a[right] >= a[key])
		{
			right--;
		}
		while ( a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[left], &a[key]);
	return left;
​}

还有一个问题，当我们的数组本来就是有序的呢？那么这个时候left或者right就会一直往右或者往左走，就会发生越界访问，所以正确的样子应该是这样子的

//haore版本
int Partion1(int* a, int left, int right)
{
	//左边为key,右边先走
	int key = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[left], &a[key]);
	return left;
}

这是我们的第一步的交换，那么同理我们可以将左半部分认为是一个新的数组，右半部分认为是一个新的数组，对其再次进行找key交换

那么最终的代码

void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = Partion(a, left, right);
	//[left,key-1]keyi[key+1,right]
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

 最终我们的数组就会有序

最后

以上就是靓丽铅笔为你收集整理的快速排序(详解)hoare版本的全部内容，希望文章能够帮你解决快速排序(详解)hoare版本所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。