【初探数据结构】快速排序的四种实现方式（Hoare，挖坑，前后指针，非递归）

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感兴趣的朋友

前言

快速排序是一种高效的分治排序算法，核心思想是通过选定基准元素将数组划分为两部分，递归排序子数组。本文详细介绍四种实现方式：Hoare法、挖坑法、前后指针法及非递归实现，并分析其优缺点。

一、Hoare法（左右指针法）

实现步骤：

1. 选基准：选最左边的元素作为基点
2. 双指针移动：
   • 右指针先向左找比基准小的元素。
   • 左指针向右找比基准大的元素。
     💡：选左作为基点，一定要右指针先动；若选右作基点，就左指针先动
3. 交换与相遇：交换左右指针的元素，直到左右指针相遇，最后将基准放到相遇位置。
4. 递归分区：以相遇位置为分界点，递归处理左右子数组。

代码（有缺陷）：

int PartSort1(int* a, int left, int right) {
    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[key], &a[left]);
    return left;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
		int keyi = PartSort1(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
}

有没有发现什么端倪呢？😜

发现问题

问题1

当基点每轮都是最大或者最小的元素时，性能会大幅下降，时间复杂度来到了$O(N^2)$

也就是说，会递归N次。

问题2

画图我们可以发现，这个递归的逻辑实际上就是一颗二叉树。

学过二叉树的我们知道，二叉树随着层数的增加，结点成指数增长，二叉树的最后一层的结点甚至占总结点数的一半，也就是说，递归的深度越大，递归的代价会越来越高。那么，有什么改进的办法呢？

解决问题（优化方案）

选取基准的优化

核心思想：避免基点最大或最小

1. 随机数定key法
   通过rand函数实现

srand((unsigned int)time(NULL));
	int randi = left + rand() % (right - left);
	swap(&a[left], &a[randi]);
	int key = left;

2. 三数取中定key法
   通过条件语句即可实现

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

int main()
{
	int mid = GetMidNumi(a, left, right);
	if (mid != left)
		swap(&a[left], &a[mid]);
	int key = left;
}

💡：三数取中法的效果略高于随机定数，因为随机定数依然有概率选到最大最小数（尽管这可能是极小概率事件）
后文选取基点均用三数取中法。

区间优化

递归的最后几层不再进行递归，直接用插入排序即可
插入排序不再赘述【初探数据结构】直接插入排序与希尔排序详解

if ((right - left + 1) > 10) {
		int keyi = PartSort1(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	else
		InsertSort(a+left,(right-left+1));

正确代码：

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
	//随机数定key
	/*srand((unsigned int)time(NULL));
	int randi = left + rand() % (right - left);
	swap(&a[left], &a[randi]);*/

	//三数选中定key(效果相比随机法相对较高)
	int mid = GetMidNumi(a, left, right);
	if (mid != left)
		swap(&a[left], &a[mid]);
	int key = left;
	while (left < right)
	{
		//right先走
		//right向左找小
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		//left向右找大
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		swap(&a[right], &a[left]);
	}
	swap(&a[key], &a[left]);
	key = left;
	return key;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	//区间优化
	if ((right - left + 1) > 10) {
		int keyi = PartSort1(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
	else
		InsertSort(a+left,(right-left+1));
}

二、挖坑法

实现步骤：

1. 挖坑：选取基准后，将其值保存，原位置视为“坑”。
2. 填坑：
   • 右指针向左找比基准小的元素，填入左坑，形成新坑。
   • 左指针向右找比基准大的元素，填入右坑，形成新坑。
3. 基准归位：当左右指针相遇时，将基准值填入最后的坑中。
4. 递归分区。

代码要点：

int PartSort2(int* a, int left, int right) {
    int mid = GetMidNumi(a, left, right);
    if (mid != left)
    	swap(&a[left], &a[mid]);
    int key = a[left], 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;
}

优点：减少元素交换次数，逻辑更直观。

三、前后指针法

实现步骤：

1. 初始化指针：prev指向基准位置，cur从prev+1开始遍历。
2. 元素交换：
   • 若cur指向的元素小于基准，prev先右移，再交换prev和cur的元素。
3. 基准归位：遍历结束后，将基准与prev位置的元素交换。
4. 递归分区。

代码要点：

int PartSort3(int* a, int left, int right) {
    int mid = GetMidNumi(a, left, right);
    if (mid != left) swap(&a[left], &a[mid]);
    int key = left, cur = left + 1, prev = left;
    while (cur <= right) {
        if (a[cur] < a[key] && ++prev != cur) 
            swap(&a[prev], &a[cur]);
        cur++;
    }
    swap(&a[prev], &a[key]);
    return prev;
}

优点：代码简洁，适合单链表排序。

四、非递归实现（栈模拟递归）

实现步骤：

1. 栈初始化：将初始区间[left, right]压入栈。
2. 循环处理：
   • 弹出栈顶区间，进行分区。
   • 将左右子区间压入栈（需注意顺序）。
3. 终止条件：栈为空时排序完成。

代码要点：

void QuickSortNonR(int* a, int left, int right) {
    ST st;
    STInit(&st);
    STPush(&st, right);  // 先压右边界
    STPush(&st, left);   // 再压左边界
    while (!STEmpty(&st)) {
        int begin = STTop(&st); STPop(&st);
        int end = STTop(&st); STPop(&st);
        if (begin < end) {
            int keyi = PartSort3(a, begin, end);
            // 压入右子区间
            STPush(&st, end);
            STPush(&st, keyi + 1);
            // 压入左子区间
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDestroy(&st);
}

注意事项：

• 栈操作顺序：需确保先处理左子区间，再处理右子区间，压栈顺序应为右子右界→右子左界→左子右界→左子左界。
• 栈的实现：需确认栈的Push和Pop操作符合后进先出（LIFO）特性。

五、对比与优化

优化策略：

1. 三数取中：避免最坏时间复杂度。
2. 小区间插入排序：对长度较小的子数组使用插入排序（如代码中(right-left+1) > 10时优化）。

六、总结

快速排序时间复杂度$O(N\ast logN)$
快速排序的四种实现方式各有适用场景：

• Hoare法适合教学和理解分治思想。
• 挖坑法在减少交换次数时表现优异。
• 前后指针法代码简洁，适合扩展。
• 非递归实现解决了递归栈溢出的问题，适合工程应用。

gitee源码

理解每种方法的核心逻辑和细节，才能在实际应用中灵活选择最优方案。