该方法没有效率的提升

发布时间：2025-06-24 17:49:54  作者：北方职教升学中心  阅读量：854

动图演示（hoare版）

三、

直接插入排序在同是O(N^2)的情况下，它的速度要更快

因为通常情况下，它是达不到O(N^2)，只有在完全有序的情况下，才能达到O(N^2)

所以同级情况下，它要比其它排序更快一点，它的实践意义也在于此。时间复杂度分析

在比较理想的情况下，快排的递归结构接近完全二叉树，所以层数为logn层，每一层排序次数近似为n，（即单趟的时间复杂度为n）

故时间复杂度为：O(nlogn)

但是在有序场景下使用快排会性能会下降，时间复杂度为O(N^2)

如下图所示：

• 当key在左边时，右边R找小就会找不到，然后一直往左走，直到在key处相遇，
• 然后自己跟自己交换，结束一趟的排序。代码实现（hoare版）

  void swap(int* a, int* b){	int tmp = *a;	*a = *b;	*b = tmp;}//hoare版void QuickSort(int* a, int left, int right) //参数为数组下标{	//递归结束条件 	if (left >= right)	{		return;	}	int keyi = left;	int begin = left;	int end = right;	//单趟排序	while (begin < end)	{		while (begin < end && a[end] >= a[keyi])		{			end--;		}		while (begin < end && a[begin] <= a[keyi])		{			begin++;		}		swap(&a[begin], &a[end]);	}	swap(&a[begin], &a[keyi]);	keyi = begin;	//将begin下标位置赋给keyi	//分割出左右区间	// [left, keyi-1] keyi [keyi+1, right]		//整体排序 递归	QuickSort(a, left, keyi - 1);	QuickSort(a, keyi+1,right);}

  五、

  目录

  一、相遇场景分析

  6.1 ❥ 相遇位置一定比key要小的原因

  我们发现，每次L与R相遇时与key进行交换时，L的值都小于key，这是为什么呢？

  这里对他们相遇的场景进行分析：

  相遇时无非两种场景，要么R遇见L，要么L遇见R

  L遇R：

  R先走，找小，停下来。

  该方法没有效率的提升（因为单趟排序效率无提升空间，至少都得遍历一遍）

  但理解起来更简单，因为它们相遇的位置是坑，所以不用分析左边做key，右边先走的问题，也不用分析相遇位置比key小的原因

  9.1 ❥ 动图演示

  

  9.2 ❥ 思路详解

  1. 将序列的第一个元素作为基准值，存放在临时变量key中，此时的第一个坑位形成
  2. L指向第一个元素，R指向最后一个元素
  3. R开始向前移动，R--，找比key小的值，找到后，将R指向的值填入L的坑位，此时R形成一个坑位
  4. 然后L开始向后移动，L++，找比key大的值，找到后，将L指向的值填入R的坑位，此时L形成一个坑位
  5. R和L交错移动，形成新的坑位，直到R与L相遇
  6. 此时将key值填入L和R共同所指向的坑位
  7. 单趟排序完成
  8. 然后分割左右区间进行递归排序
  9. 最后排成一个有序序列

  

  9.3 ❥ 代码实现

  //挖坑法void QuickSort1(int*a,int left,int right){	//递归结束条件 	if (left >= right)	{		return;	}	int key = a[left];	int begin = left;	int end = right;	//单趟排序	while (begin < end)	{		while (begin<end&&a[end] >= key)		{			end--;		}		a[begin] = a[end];	//甩给右区间坑		while (begin<end&&a[begin] <= key)		{			begin++;		}		a[end] = a[begin];	//甩给左区间坑	}	a[begin] = key;	//将key填入相遇的坑	//进行递归排序	QuickSort1(a, left, begin - 1);	QuickSort1(a, begin + 1, right);	}

  ---

  十、时间复杂度分析

  八、挖坑法

  这里的挖坑法是以单趟排序的思路优化出的挖坑法。易错提醒

  六、

  R停下条件是：遇见比key小的值，R停的位置一定比key小，L没有找到大的，遇见R停下

  所以说：L遇R，它们相遇的位置就是R的位置

  

  R遇L：

  R先走，找小，没有找到比key小的，直接跟L相遇了。

  其基本思想为：

  1. 任取待排序元素序列中的某元素作为基准值，按照该排序将待排序集合分割成两个子序列
  2. 左子序列中所有元素均小于基准值，右子序列中的所有元素均大于基准值
  3. 然后分别对左右两部分重复上述操作，直到将无序序列排列成有序序列。

  六、

  L停留的位置是上一轮交换的位置

  上一轮交换，把比key小的值，换到了L的位置

6.2 ❥ 右边为key，左边先走

我们发现，上面相遇场景都是左边做key，如果右边做key，让左边先走呢？

右边做key时：相遇位置一定比key要大

如下图所示：

结论：

• 左边做key，右边先走，可以保证相遇位置一定比key小
• 右边做key，左边先走，可以保证相遇位置一定比key大

6.3 ❥ 一边为key，另一边先走的原因

有人肯定会疑惑，为什么要一边做key，另一边先走，不可以做key的一边先走吗？

可以验证一下：

上图是让key在左边，且左边先走，在8相遇，然后与key==5进行交换

交换完后，5换到了数组下标为5的位置，并没有换到他所对应的正确位置，且左区间的8比5大。

当然，引入小区间优化会使得效率低下，增加了算法的复杂度。分割出左右区间。前后指针法

前后指针法只是单趟逻辑改变，整体递归思路并没有改变。前后指针法

10.1 ❥ 动图演示

10.2 ❥ 思路详解

10.3 ❥ 代码实现

---

一、

我们知道，快排是当一趟排完之后，左区间都比key小，右区间都比key大，且key刚好在正确位置上，这样才可以继续分左右区间进行递归排序。

该方法没有效率的提升。挖坑法

9.1 ❥ 动图演示

9.2 ❥ 思路详解

9.3 ❥ 代码实现

十、

八、

四、

小区间优化目的：

当待排区间长度小于等于某个阈值时，不再递归分割排序，减少递归调用的深度和对栈空间的使用，避免过度分割导致的效率下降，可以在处理小规模数据时获得更好的性能，从而提高整体排序算法的效率。

代码如下：

//直接插入算法void InsertSort(int* a, int n){	for (int i = 0; i < n - 1; i++)	{		int end = i;		int tmp = a[end + 1];		while (end >= 0)		{			if (tmp < a[end]) 			{				a[end + 1] = a[end];				end--;			}			else			{				break;			}		}		a[end + 1] = tmp;	}}//交换算法void swap(int* a, int* b){	int tmp = *a;	*a = *b;	*b = tmp;}//三数取中int GetMidi(int* a, int left, int right){	int midi = (left + right) / 2;	if (a[left] > a[right])	{		if (a[left] < a[midi]) 		{			return left;		}		else if (a[midi] < a[right])			{			return right;		}		else			{			return midi;		}	}	else	{		if (a[right] < a[midi])			{			return right;		}		else if (a[midi] < a[left])			{			return left;		}		else 		{			return midi;		}	}}//hoare版void QuickSort(int* a, int left, int right) //参数为数组下标{	if (left >= right)	{		return;	}	// 小区间优化，不再递归分割排序，减少递归的次数	if ((right - left + 1) < 10)	{		InsertSort(a + left, right - left + 1);	}	else	{		 //三数取中		int midi = GetMidi(a, left, right);		swap(&a[left], &a[midi]);		int keyi = left;		int begin = left;		int end = right;		while (begin < end)		{			while (begin < end && a[end] >= a[keyi])			{				end--;			}			while (begin < end && a[begin] <= a[keyi])			{				begin++;			}			swap(&a[begin], &a[end]);		}		swap(&a[begin], &a[keyi]);		keyi = begin;		QuickSort(a, left, keyi - 1);		QuickSort(a, keyi + 1, right);	}}

---

九、思路分析（图文）

以下以升序为例：

简言之，就是先进行单趟的排序，单趟排完之后，key已经放在它合适的位置上，分割出了一个左区间和右区间，然后进行递归排序，当左右区间都有序时，那么就整体有序。基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。快排的优化

• 经过时间复杂度的分析，发现当前的快排算法还是存在一些缺陷的，那就是在有序场景下使用快排会性能会下降，此外，还有可能导致栈溢出。快排的优化

  8.1 ❥ key值的选取

  8.1.1 随机数选key

  8.1.2 三数取中

  8.2 ❥ 小区间优化

  九、

• 所以快排在此还是有较为明显的缺陷的，面对这些缺陷，我们在此应怎么解决呢？
• 我们知道，时间复杂度为O(nlogn)的前提是每次区间的划分都是二分，也就是每次选择交换的key，都是接近中间位置的值，哪怕不那么接近二分，但整体深度是logn就可以
• 所以key值的选取非常关键，如果固定的选择最左边（下标为0）的值，就有可能选到最小的值，然后出现效率退化栈溢出的风险
• 那如何选key才能避免有序的情况下效率退化呢？
• 下面提供了两种选取key值的方式

8.1 ❥ key值的选取

8.1.1 随机数选key

• 如果想要输出给定范围[a,b]内的随机数，需要使用rand()%(b-a+1)+a
• 缺陷：可能刚刚好选到最大或者最小值

代码如下：

void rand_key(int* a, int left, int right){	int randi = left + (rand() % (right - left + 1));	swap(&a[left], &a[randi]);}

8.1.2 三数取中

所谓三数取中，就是从最左边，最右边，最中间三个位置，选择中间的值（不大不小的值）作为key（赋值给key）

代码如下：

int GetMidi(int* a, int left, int right){	int midi = (left + right) / 2;	if (a[left] > a[right])	{		if (a[left] < a[midi]) // r<l<m		{			return left;		}		else if(a[midi]<a[right])	//m<r<l		{			return right;		}		else	//r<m<l		{			return midi;		}	}	else	{		if (a[right]<a[midi])	//l<r<m		{			return right;		}		else if (a[midi]<a[left])	//m<l<r		{			return left;		}		else   //l<m<r		{			return midi;		}			}	}

注意

这里是选出的中间值还应跟最左边的值进行交换，还应该让最左边的值作为key

8.2 ❥ 小区间优化

为何要有小区间优化：

当将一组待排序列进行快排，递归到只剩下5个值时，我们还要进行选key，分割左右区间等操作让5个值有序，此刻使用递归调用花费代价太大（最后一层递归调用就要占整体递归调用的50%），这就引入了小区间优化的方式。

10.1 ❥ 动图演示

10.2 ❥ 思路详解

• 将key指向序列的第一个元素，设为基准值
• prev指向key的位置，cur指向prev的下一个位置
• 对cur进行判断：

如果cur>=key，则cur++ 

如果cur<key，prev++，交换cur和prev所指向的值，然后cur++

• 再对cur进行判断，直到cur++到序列的最后一个元素的下一个位置，交换prev与key的值
• 此时单趟排序完成
• 然后分割左右区间进行递归排序
• 最后排成一个有序序列

10.3 ❥ 代码实现

void swap(int* a, int* b){	int tmp = *a;	*a = *b;	*b = tmp;}//前后指针法void QuickSort2(int* a, int left, int right){	if (left >= right)	{		return;	}		//单趟排序	int keyi = left;	int prev = left;	int cur = left + 1;	while (cur<=right)	{		if (a[cur] < a[keyi]) //cur的值比keyi的值小		{			prev++;			if (prev != cur)	//判断prev与cur是否指向同一位置			{				swap(&a[prev], &a[cur]);			}		}		cur++;	}	swap(&a[prev], &a[keyi]);	QuickSort2(a, left, prev - 1);	QuickSort2(a, prev + 1, right);	}