大家的反馈是我更新最大动力

发布时间：2025-06-24 18:03:25  作者：北方职教升学中心  阅读量：676

这时，left 小兵来了， 两个小兵相遇，相遇的位置就是 right 小兵停下的位置，即相遇的位置比 key 位置上的值要小。

实现非递归的思路：

1. 入栈一定要保证先入右，再入左。
2. 交换后 cur++，prev++。大家的反馈是我更新最大动力。再 key = prev。
3. right 小兵停下后，left 小兵再走，直到遇到一个比 key 值要大的数字就停下。

可以确定：两个小兵相遇的位置一定是一个坑。

 由快排思想可以推出快速排序的大致框架如下：

#include <stdio.h>    // 假设按照升序对array数组中[begin, end]区间中的元素进行排序void QuickSort(int array[], int begin, int end) {    if (begin >= end)	{		return;	}      // 按照基准值对array数组的 [begin, end]区间中的元素进行划分 int keyi = PartSort(array, begin, end);      // 划分成功后以keyi为边界形成了左右两部分 [begin, keyi-1] keyi [div+1, end]     // 左部分都是比 keyi 位置上的值小的部分，右部分都是比 keyi 位置上的值大的部分。
三：快速排序——动态演示图
快速排序递归演示图：
我们发现它大致就是一个二叉树的前序遍历形态。经过几轮交换之后，相遇的位置就是 left 小兵的位置，此时，因为经过了上一轮 left 位置上的值 与 right 位置上的值 交换。
挖坑法思路过程分析：
先将 key 的值存起来，注意：此处的 key 存的是值，而不是位置下标。 
四：***快速排序——单趟排序****
将区间按照基准值划分为左右两半部分的常见方式有：1.霍尔法；2.挖坑法；3.前后指针法
4.1：霍尔法
        因为霍尔是最早实现快速排序的人，所以霍尔法也是整个快排最早的版本。
当一个数组序列中含有多个相同元素的时候，单纯的使用常规法已经不能发挥出独属于快排的全部威力了。排序完：[ left , keyi - 1 ] keyi [ keyi + 1 , right ]
重复2，3过程直到栈为空。
注意：基准值 key 在左边， right 小兵先走；基准值 key 在右边，left 小兵先走。
其基本思想为：
任取待排序元素序列中的某元素作为基准值，
按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，
然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。再进行快速排序，这种优化方法就能使该排序效率比原来高。	}    // left 与 right 相遇	Swap(&a[left], &a[keyi]);	keyi = left;            // 生成新的 keyi 位置	return keyi;}// 霍尔单趟排序之后， keyi 位置左边的部分都比 keyi位置的值要小，keyi 位置右边的部分都比 keyi位置的值要大。
当 a[cur] > key，交换 cur 和 right 位置上的值，right--。
// 单趟排序//		1.霍尔法int PartSort1(int* a, int left, int right){	int keyi = left;                // 记录下 key 的位置	while (left < right)            // 当 left 与 right 相遇时退出循环	{		// 右边找小		while (left < right && a[right] >= a[keyi])		{			--right;		}		// 左边找大		while (left < right && a[left] <= a[keyi])		{			++left;		}        // 此时 right 位置上的值要比 keyi 位置上的值小，left 位置上的值要比 keyi 位置上的值大        // 交换 left 位置与 right 位置上的值。 
二：快速排序——分析
        对于快速排序，重点就在于基准值 key 的位置，知道 key 的位置之后，分别再对左右两边部分再找 基准值 key 的位置，依次在各个部分区间内找 基准值 key，通过一遍又一遍的递归，到最后区间内只有一个数时，这个递归也就结束了。     // 递归排左部分[begin, keyi-1] QuickSort(array, begin, keyi);      // 递归排右部分[keyi+1, end] QuickSort(array, keyi+1, end);}int main(){	int a[] = { 2,5,7,1,4,9,6,3,8,0 };	int sz = sizeof(a) / sizeof(a[0]);    // 求取数组内元素个数	QuickSort(a, 0,sz-1);                // 传递的都是下标    return 0;}
        我们发现与二叉树前序遍历规则非常像，所以我们在分析快速排序过程中的递归框架时可想想二叉树前序遍历规则即可理解并快速写出来，在后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
right 小兵继续走，重复 2，3，4动作，直到 left 小兵与 right 小兵相遇
相遇之后，将相遇位置的值与基准值 key 位置上的值交换，让相遇位置置成新的 key。不过这种方法不仅是思路还是实现效率都比其他两中方法要好一些，同时这种方法也是大众比较流行的方法之一。
注意：有坑的小兵不走；填坑时，要先将原来的坑给补上，再建立新坑。
如下动图中，因为 hole坑在最左边，所以还是 right 小兵先走，找比 key值要小的值。具体情况，大家可以通过快速排序的动态演示图和递归分解图进行分析。找到之后，将 right 位置上的值放到原来的坑上，在将此时 right 位置 记作新坑。
【排序算法】——快速排序
目录
一：快速排序——思想
二：快速排序——分析
三：快速排序——动态演示图
四：快速排序——单趟排序
4.1：霍尔法
4.2：挖坑法
4.3：前后指针法
五：快速排序——递归实现
5.1：快速排序--->常规法
5.2：快速排序--->三路划分法
六：快速排序——非递归实现
七：快速排序——优化
7.1：快速排序优化--->三数取中选key法
7.2：快速排序优化--->随机数生成选key法
7.3：快速排序优化--->小区间改造
八：快速排序——特性总结
一：快速排序——思想与大致框架
        快速排序是Hoare（霍尔）于1962年提出的一种二叉树结构的交换排序方法。
key 位置在左边
就相遇位置值分析：
若 left 小兵与 right 小兵相遇，又有两种情况：1. left 小兵走的时候，遇到 right 小兵（L遇）；2.right 小兵走的时候，遇到 left 小兵（R遇L）。
right 位置上形成一个新坑后，left 小兵出发，找比 key 值要大的值。left 位置上的值就是上一轮交换中 right 停下位置上那个比 key 值小的值。因此就有一些大佬采用了三数取中的方法解决选 keyi 位置不合适的问题。
 霍尔法单趟过程分析：
先记录下基准值key的位置，让 left 和 right 向两端靠近（直至相遇）。
返回 key 位置的下标
  单趟排序前后指针法代码实现：
// 3.前后指针法int PartSort3(int* a, int left, int right){	int prev = left;            // 定义一个 prev “指针”	int cur = left + 1;         // 定义一个 cur “指针”	int keyi = left;            // 先确定基准值的位置	while (cur <= right)	{		while (a[cur] <= a[keyi] && ++prev != cur)    // cur指针找小，并且 prev先+1，加1之后再进行交换（简化代码）		{			Swap(&a[cur], &a[prev]);		}		++cur;	}	Swap(&a[prev], &a[keyi]);        // 交换 key 位置上的值与 prev 位置上的值	keyi = prev;	return keyi;}
五：快速排序——递归实现
5.1：快速排序--->常规法
所谓常规法，就是按照我们前面的思路对快速排序进行总结实现，无任何添加，即是常规。 
 三路划分法的思想：
当 a[cur] < key，交换 cur 和 left 位置上的值，left++，cur++。
三路划分法的本质：
小的甩到左边，大的甩到右边。
快速排序非递归代码实现：
// 快速排序--非递归法void QuickSortNonR(int* a, int begin, int end){	Stack st;            // 定义一个栈	STInit(&st);	STPush(&st, end);    // 栈：先入右	STPush(&st, begin);  // 再入左	while (!STEmpty(&st))	{		int left = STTop(&st);    // 取栈顶作为 区间的左边界		STPop(&st);		int right = STTop(&st);   // 取栈顶作为 区间的右边界		STPop(&st);		int keyi = PartSort2(a, left, right);    // 单趟排序得出 keyi		// [left,keyi-1]keyi[keyi+1,right]		if (left < keyi - 1)                // 判断该区间是否合法		{			STPush(&st, keyi - 1);			STPush(&st, left);		}		if (keyi + 1 < right)               // 判断该区间是否合法		{			STPush(&st, right);			STPush(&st, keyi + 1);		}	}	STDestroy(&st);}
效果演示：
七：快速排序——优化
7.1：快速排序优化--->三数取中选key法
        在快速排序问世以来，一些人发现，keyi 的位置，是影响快排效率的最大因素，将 keyi 放在合理的位置就可再次增大该排序的运行效率。
1. left 小兵走的时候，遇到 right 小兵
 因为是 key 位置在左边， right 小兵先走，所以当 right 小兵停下时，其位置上的值一定是比 key 位置上的值小的。
同理，key 位置在右边的时候，也是相同的情况分析。
所谓三数取中：就是取头，中，尾三个元素，比较大小，选择那个排在中间的数据作为基准值 keyi 。
right 小兵先走，直到遇到一个比 key 值要小的数字就停下。
交换 left 位置和 right 位置上的值。
// 快速排序--递归法void QuickSort(int* a, int begin, int end){	if (begin >= end)	{		return;	}	int mid = GetMidIndex1(a, begin, end);	Swap(&a[begin], &a[mid]);        // 再交换中间值位置与最左边位置	int keyi = PartSort3(a, begin, end);	// [beign,keyi-1] keyi [keyi+1,end]	QuickSort(a, begin, keyi - 1);	QuickSort(a, keyi + 1, end);}
7.2：快速排序优化--->随机数生成选key法
有人说，三数取中法有些死板，所取的值只能是固定位置，于是又有人在基于三数取中优化法之上，进行了再次优化——随机数生成选 key 法。找到之后，将 left 位置上的值放到原来的坑上，在将此时 left 位置 记作新坑。
取两次栈顶元素作为 区间的 left 和 right。
 单趟排序挖坑法代码实现：
// 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;        // 最后一个坑填 基准值 key	return hole;          // 返回基准值的下标}
4.3：前后指针法
这三种单趟排序的方法思想都是差不多的。