快速排序（hoare版本）

文章目录

前言

二、使用步骤

1.实现基准值

2.递归实现排序

3.三数取中

三.注意事项

总结

前言

我们之前学习的多种排序，它们都有着不同的效率，可以适用与不同的场景，接下来要说的一种排序它叫做快速排序，从它的名字就可以看出来它的效率一定很高。

一、快速排序的实现

快速排序的实现就如图一样，先右边的开始走如果碰到比key值小的数值就在那个位置停下，然后左边开始执行，如果碰到比key值大的也同样停止，然后对两者进行交换。最后左和右相遇后将key和相遇的地方进行交换从而使得左边是比key小的值，右边是比key大的值，使用递归实现排序。

二、使用步骤

1.实现基准值

这是霍尔大佬最先发明写出的算法，同样的也是最经典的，同样的也好理解，通过交换的方法从而做到左边的比key要小，右边的比key要大。

代码如下（示例）：

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

2.递归实现排序

通过递归的方式，我们可以使得数都满足左边的值大于右边从而实现排序。

代码如下（示例）：

void qucksort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = Partsort(a, left, right);
	qucksort(a, left, key - 1);
	qucksort(a, key + 1, right);
}

3.三数取中

我们有时会因为key的值太小或者太大从而发挥不出快速排序的优势，所以我们可以使用自己的方式从而使其不会太大或者太小，所以三数取中就出现了，通过比较最左边和最右边以及中间的数来比较出那个的值是比较趋于中间的数。

int mid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[right])
	{
		if (a[mid] > a[left])
		{
			mid = left;
		}
		else if (a[mid] < a[right])
		{
			mid = right;
		}
	}
	else if (a[left] < a[right])
	{
		if (a[mid] < a[left])
		{
			mid = left;
		}
		else if (a[mid] > a[right])
		{
			mid = right;
		}
	}
	return mid;

}

三.注意事项

我在编写代码的时候当时我认为我的思路都是正确的，代码写的也是正确的，但是就是无法实现排序，后面我发现了先走右边和先走左边是会对结果造成影响的，我最开始写的是从左边开始走，但是排序的结果是不正确的，从右边开始的话就正确了，因为我所设置的key就为数组的最左边，如果我先走左边的话，最后的结果就为当left和right相遇的时候就该进行交换了，而这个时候交换的话无法保证左边的数比key要小，因为先走左边的时候就会在比key的大的值位置停下，最后也只能在这个位置停下。

所以实现排序的时候也要注意是先走的左边还是先走的右边，这样的小细节也是会影响到结果的实现。