数据结构 ——— 快速排序算法的实现（hoare版本）

目录

快速排序的思想

单趟排序逻辑的实现

快速排序算法的实现

快速排序的思想

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子列中所有元素均小于基准值，右子席列中所有元素均大于基准值，然后最左右子席列重复该过程，直到所有元素都排列在相应位置上为止

选出一个中间值 key，以升序举例，每一趟排序要保证 key 左边的元素比 key 小，key 右边的元素比 key 大，因为这样的话，key 停留的位置就是最后排好序的位置，就不用动了
然后比 key 小的区间再选出一个中间值 key，同样要保证 key 左边的元素比 key 小，key 右边的元素比 key 大；比 key 大的区间也是一样的操作
此操作类似于递归、分治的想法，直到最后 key 的左右两边只有一个数，且同样保证 key 比左大，比右小，那么数组就是升序了

单趟排序逻辑的实现

代码演示：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int PartSort_Hoare(int* a, int left, int right)
{
	int key = left;

	while (left < right)
	{
		// 先找右边比 key 小的元素的下标
		while (left < right && a[right] >= a[key])
			right--;

		// 再找左边比 key 大的元素的下标
		while (left < right && a[left] <= a[key])
			left++;

		// 交换 
		Swap(&a[left], &a[right]);
	}

	// 把 key 放在最终位置
	Swap(&a[key], &a[left]);

	return left;
}

代码解析：

通过以上每一趟排序的递归分治思想来看，left 和 right 并不是从数组的首尾开始递增递减的，而是每次从某一区间开始的

通常中间值的选取是最左边的值，那么 key 就是最左边值的下标
right 找比 key 小的元素，left 找比 key 大的元素
且要注意越界，因为在极端情况下，可能 key 的值小于或者大于任何一个元素
在 key 左边找到了比 key 大的值，在 key 右边找到了比 key 小的值，就进行交换
直到 left 和 right 相遇就停止，因为此时的 left 和right 都指向了同一个元素，没有可交换的

再把 key 放在最终位置，因为最开始 a[key] 是最左边的元素，那么当 while 循环走完时
left 和 right 同时指向的位置就是 a[key] 最终改放的位置

此时就完成了 a[key] 左边的元素比 a[key] 小，a[key] 右边的元素比 a[key] 大，且 a[key] 也放在了最终一个停留的位置

最后再把中间元素的下标 key 进行返回，为什么要返回下面会讲解到

快速排序算法的实现

代码演示：

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int key = PartSort_Hoare(a, begin, end);

	// [begin,key-1] key [key+1,end]

	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

代码解析：

当 begin 等于 end 时，说明此区间只有一个元素了，那么就不用再递归
当 begin 大于 end 时，说明此区间不存在，同样也停止递归

以上就是递归结束的条件

先通过每一趟的算法函数对数组进行排序，排好后返回了中间元素的下标 key
此时数组 a[key] 左边的值小于等于 a[key]，且 a[key] 右边的值大于等于 a[key]

再通过分治的思想进行递归，也就是 [begin,key-1] 这个区间再次排序，且 [key+1,end] 这一区间再次排序，同时配合递归的结束条件，最终完成对数组的排序

代码验证：