首先设定一个分界值Key，通过该分界值将数组分成左右两部分。
将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

上述为快速排序递归实现的主框架，简而言之就是快排分为两步：

（1）通过找Key将数组分成一大一小两部分

（2）递归

我们不难发现这与二叉树前序遍历规则非常像，所以在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。因此，快排也可以说是基于二叉树的排序算法。

二、快排的实现

1. 调试环境

为了方便测试写出的快排的正确性以及效率，我们首先写出下面两段用于测试的代码。

其中PrintArray是数组打印函数

TestQuickSort函数用于测试代码的正确性

TestOP函数用于测试快排的效率


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
 
void TestQuickSort()
{
	int a[] = { 9,8,7,6,5,4,3,2,1,0 };
	QuickSort(a, 0, 9);
	PrintArray(a, 10);
}


void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}
 
	int begin1 = clock();
	QuickSort(a1, 0, N - 1);
	int end1 = clock();
	printf("QuickSort:%d\n", end1 - begin1);
}

现在我们有了测试函数之后，可以进行快排的具体实现过程了。

2.快排的单趟排序

按照上文中所说的步骤，我们首先进行第一步，找key将数组分成一大一小的两部分，也就是快排的单趟排序。快排发展到现在，单趟排序一共有三种主流的方式，下面我将逐一解释这三种方式的具体做法。

（1）Hoare版本

第一种做法是Hoare大佬最初设计快排时提出并采用的方法。首先我们定义left和right两个指针分别指向数组的头和尾，然后将数组中第一个数据定义为key。

我在这里按照升序演示，因为我们需要保证数组左边的数据比key小，右边的数据比key大，所以我们让right指针先出发找小，left指针找大，找到后两指针指向的数据交换。

然后让left和right继续前进，分别找大找小交换后，直到两指针相遇。

两指针相遇后，将相遇位置的数据与key交换，此时快排的第一步单趟排序结束。

注意： 你可能会对最后一步有疑问，为什么直接将key与相遇位置交换，相遇位置有没有可能比key大，直接交换是不是会出错？

答案是不会，因为我们让左边第一个数做key，right先走

R停下来，L撞到R，相遇位置比key小
L停下来，R撞到L，相遇位置比key小

因此，如果选右边第一个数做key的话，就需要让left先走了。

这便是Hoare版本的具体过程，下面请看具体代码。

（返回值是为了后面要提及的递归）


//快排的单趟排序（hoare版本）
int PartSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	int meeti = left;
	Swap(&a[keyi], &a[meeti]);
	return meeti;
}

（2）挖坑法

下面是具体的代码。


//单趟排序--挖坑法
int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

（3）前后指针法

下面是具体代码。


//前后指针法
int PartSort3(int* a, int left, int right)
{
	int key = a[left];
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < key && ++prev < cur)
			Swap(&a[prev], &a[cur]);
		cur++;
	}
	Swap(&a[left], &a[prev]);
	return prev;
}

2.递归过程


void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
 
	int keyi = PartSort3(a, begin, end);
 
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
	
}

只要写完快排的单趟排序，递归过程就非常简单了。上面的单趟排序中返回值便是排序好后key的位置，也就是说快排的单趟排序可以确实一个元素的正确位置，并且将数组分成了比key小和比key大的两个部分。所以直接递归【begin，key-1】和【key+1，end】就可以了。

三、快排的优化

1. 优化取key方式，防止栈溢出

经过上面的讲解我们已经有了一个快排的初步代码，现在我们可以使用开头给出的测试函数检查一下快排的正确性，以及快排的效率怎么样。

首先，我们写的快排正确性没有问题，然后我给出了测试有一百万个随机数的数组，排序用了 183ms，速度还是比较快的。

让我们来计算一下快排的时间复杂度，不难得出快排的时间复杂度为O（NlogN）

但是，让我把测试函数改一下的话，则会出现一些状况。


void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}
	QuickSort(a1, 0, N - 1);
	int begin1 = clock();
	QuickSort(a1, 0, N - 1);
	int end1 = clock();
	printf("QuickSort:%d\n", end1 - begin1);
}

我们让快排去给一个有序的数组排序，按理说应该速度更快，结果却栈溢出了。

刚才我们计算时间复杂度的时候是按照较为理想的情况，如果一个数组有序或者接近有序，我们在使用刚才写出的代码进行排序时，每个key选择的都是左边第一个，那么递归深度就会很大，接近N，此时就是出现栈溢出的情况。

所以，为了避免这种情况，我们就需要优化选key的方式，在这里，我给出三种方法：

随机选一个位置做key
针对有序，选正中间做key
三数取中：选出数组的begin end mid 三个位置然后取中间值做key。

其中，第三种方式最常用，实现过程也比较简单，下面我直接给出代码。


//三数取中选key
int getMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[right] < a[left])
		{
			return left;
		}
		else if (a[right] > a[mid])
		{
			return mid;
		}
		else
			return right;
	}
	else  //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
			return right;
	}
}

2. 小区间优化

我们在递归的过程中，小区间占用的函数栈帧最多，此时数组的长度较小，使用快排的递归反而会导致效率下降，因此我们可以优化一下小区间使用其他排序方式排序。

我们进行如下优化，当递归区间长度小于8时，我们使用插入排序，这样可以进一步提高快排的效率。


void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
 
	// 小区间优化
	if (end - begin < 8)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort1(a, begin, end);
 
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

四、快排的非递归方式


void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
 
	while ( !StackEmpty(&st) )
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		int mid = PartSort3(a, left, right);
 
		if (mid + 1 < right)
		{
			StackPush(&st, mid+1);
			StackPush(&st, right);
		}
 
		if (mid - 1 > left)
		{
			StackPush(&st, left);
			StackPush(&st, mid-1);
		}
 
	}
	StackDestroy(&st);
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/614907