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

目录

前言

快速排序算法（挖坑版本）的思想

单躺排序逻辑的实现

快速排序算法的实现（挖坑法）

前言

在上一章学习了 hoaer 版本的快速排序算法的实现
数据结构 ——— 快速排序算法的实现（hoare版本）-CSDN博客
可是 hoaer 版本的快速排序算法存在缺陷
比如说：如果把最左边的值当作 key 的话，那么就必须让右边先走，也就是要让右边先找到比 key 小的值，否则的话最后排出来的就是乱序
因为 left 是找比 key 大的值，right 是找比 key 小的值，只有让 right 先走，才能保证当他们快要相遇时，相遇的值比 key 小，否则让 left 先走的话，最后相遇的位置就不一定是比 key 小的值

所以基于上述原因，对 hoare 版本的快速排序算法进行了改进，避免了这些缺陷

快速排序算法（挖坑版本）的思想

同样是 left 往右边走，找比 key 小的值； right 往左边走，找比 key 大的值；且 key 是最左边的值
不同之处在于是把 key 的值先保存下来，那么就可以形象的理解为 key 的位置被挖了一个坑
然后 right 找到比 key 小的值时，就把小的值放在 key 的位置，也就是放在坑的位置
那么 right 这个位置就形成了新的坑，然后 left 再找，当 left 找到比 key 大的值时，就放到 right 这个坑的位置，最后 left 和 right 相遇的位置也肯定是一个坑，再把保存的 key 放入坑中
这时的数组同样能保证 key 左边的值比 key 小，key 右边的值比 key 大，且就算 left 先走也同样可以完成

以上就是挖坑法单躺排序的思想

单躺排序逻辑的实现

int PartSort_DigPit(int* a, int left, int right)
{
	// 保存 key 的值
	int key = a[left];

	// 坑的下标
	int hole = left;

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

		// 填坑
		a[hole] = a[right];
		// 赋值新坑的下标
		hole = right;

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

		a[hole] = a[left];
		hole = left;

	}

	// 把 key 放在最终位置
	a[hole] = key;

	return hole;
}

快速排序算法的实现（挖坑法）

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

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

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

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

除了挖坑法单躺的思想和 hoare 版本单躺的思想有差异，其他的思路都是一样的
这里就不过多赘述，直接看结论

代码验证：