【数据结构】排序——快速排序

前言

本篇博客我们继续介绍一种排序——快速排序，让我们看看快速排序是怎么实现的

💓 个人主页：小张同学zkf

⏩ 文章专栏：数据结构

若有问题评论区见📝

🎉欢迎大家点赞👍收藏⭐文章

1.快速排序（hoare方法）

2.快速排序（挖坑法）

3.快速排序（前后指针法）

4.快速排序（非递归法）

5.快速排序特性

1.快速排序（hoare方法）

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

// 假设按照升序对 array 数组中 [left, right) 区间中的元素进行排序

void QuickSort ( int array [], int left , int right )

{

if ( right - left <= 1 )

return ;

// 按照基准值对 array 数组的 [left, right) 区间中的元素进行划分

int div = partion ( array , left , right );

// 划分成功后以 div 为边界形成了左右两部分 [left, div) 和 [div+1, right)

// 递归排 [left, div)

QuickSort ( array , left , div );

// 递归排 [div+1, right)

QuickSort ( array , div + 1 , right );

}

我们先看看快速排序的动图

整体思想，以左面的数据为key，然后先让right指针向右走，找比key位置上的值小的值，找到之后，停止移动，然后left指针向左移动找比key大的值，找到之后，交换left和right位置上的值，然后右指针继续找小，左指针继续找大，找到之后继续交换，重归此过程，直到左指针与右指针相遇，相遇的位置与key位置上的值交换，再把key赋值成相遇的位置。这是单趟排序。再将以key为中心分成两个左右区间再次递归到这个函数中，不断递归，直到最后的区间为1，或不存在区间。递归返回。

代码如下

但如果我们想让快排效率高，我们得考虑些极端情况，比如如果右边指针一直没找到比最左边的数大的，左右指针直接在key位置上相遇了。递归只有一个区间一直递归，就会大大降低了快排的效率，特别是在有序的情况下，所以，只有每次递归，key都在中间位置时，效率才最快，所以我们可以定义一个三数取中的函数，函数的返回值与left位置上的值交换就ok了。

那三数取中么写，其实很简单，就是比较最左边最右边以及最中间的值，谁是第二大的，返回第二大的就行。

三数取中代码如下

int sanshuquzhong(int* a,int left, int right)
{int mid = (left + right) / 2;if (a[left] >a [mid]){if (a[mid]>a[right]){return mid;}else{if (a[right] > a[left]){return left;}else{return right;}}}else{if (a[mid] < a[right]){return mid;}else{if (a[right] > a[left]){return right;}else{return left;}}}
}

有了三数取中，快排效率就明显提高，但是还是有人觉得快排不够快，确实，随着递归的深入，效率会越来越慢，所以为了加快效率，我们可以进行小区间优化

我们由图分析可知最后一次递归耗费次数最多，所以我们可以对最后几次小区间下手，用其他排序替换快排，从而让效率提高，我们可以在最后几个区间时用插入排序来进行

void charupaixu(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

ok,到这里我们的代码就写完了，我们想一个问题，为什么我们要选key，并且选的key在左边时，一定要右边指针先走才行，为什么这么规定那。如下图分析

这样快速排序（hoare方法）就初步得成，所有代码如下

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void swap(int* as, int* ak)
{int tmp = *as;*as = *ak;*ak = tmp;
}
void charupaixu(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}
int sanshuquzhong(int* a,int left, int right)
{int mid = (left + right) / 2;if (a[left] >a [mid]){if (a[mid]>a[right]){return mid;}else{if (a[right] > a[left]){return left;}else{return right;}}}else{if (a[mid] < a[right]){return mid;}else{if (a[right] > a[left]){return right;}else{return left;}}}
}
void kuaisupaixu(int* arr, int left,int right)
{if (right <= left){return;}if (right - left + 1 < 10)//小区间排序{charupaixu(arr + left, right -left+ 1);}int mid = sanshuquzhong(arr,left, right);//三数取中swap(&arr[mid], &arr[left]);int key = left;int begin = left;int end = right;while (begin<end){while (begin<end&&arr[end] >=arr[key]){end--;}while (begin<end&&arr[begin] <= arr[key]){begin++;}swap(&arr[end], &arr[begin]);}swap(&arr[begin], &arr[key]);key = begin;kuaisupaixu(arr,left,key-1);kuaisupaixu(arr,key+1,right);
}

2.快速排序（挖坑法）

随着快排的不断发展，人们优化了hoare方法，用挖坑法，虽然这种方法没有效率的提升，不过方便了人们对代码的理解再也不用考虑为什么要右边先走的问题

我们看一下这个方法的动图

其实就是把交换换成填补，定义一个临时变量为坑，最后把Key自然放进坑位就行，这个方法更方便我们理解

就是在hoare方法代码中微调一下就行

代码如下

// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{if (left >= right){return;}if (right - left + 1 < 10){charu(a+left, right - left + 1);}else{int mid = sanshuquzhong(a, left, right);swap(&a[mid], &a[left]);int key = a[left];int begin = left;int end = right;int keng = left;while (begin < end){while (begin < end && a[end] >= key){end--;}a[keng] = a[end];keng = end;while (begin < end && a[begin] <= key){begin++;}a[keng] = a[begin];keng = begin;}a[begin] = key;PartSort2(a, left, begin- 1);PartSort2(a, begin + 1, right);}}

3.快速排序（前后指针法）

快速排序还有另一种方法，也是最容易记住的，我们可以通过定义两个指针，刚开始一个指向key，一个指向key的下一个数，让前面那个指针一直向前走找比key小的数，第二个若找到比key小的数，那么前后指针之间的数就是比key大的数，++后指针再交换俩指针指向的数，前指针继续向前找，直到超过边界停止，最后key与此时后指针指向的书交换，并且key赋值于后指针的位置，递归key前key后空间

动图如下

我们可以画图分析一下

代码如下

// 快速排序前后指针法
void PartSort3(int* a, int left, int right)
{if (left >= right){return;}if (right - left + 1 < 10){charu(a + left, right - left + 1);}else{int mid = sanshuquzhong(a, left, right);swap(&a[mid], &a[left]);int key = left;int man = left;int kuai = left + 1;while (kuai <= right){if (a[kuai] < a[key] && ++man != kuai){swap(&a[man], &a[kuai]);}kuai++;}swap(&a[key], &a[man]);key = man;PartSort3(a, left, key - 1);PartSort3(a, key + 1, right);}
}

4.快速排序（非递归法）

前三种方法都是递归法，若不用递归我们该怎么弄，不用递归，我们就得需要栈这个结构，代码整体不变，把最后递归的部分改成把key左右两个区间全入栈，先右区间入栈再左区间入栈，因为栈是后进先出原则，出栈就是左区间先出栈，直到栈空，入栈的条件左指针小于Key-1,右指针大于key+1。

画图看一下

区间边界值入栈，来替代了递归

代码如下

#include "stack.h"
int yici(int* a,int left,int right)
{int mid = sanshuquzhong(a, left, right);swap(&a[mid], &a[left]);int key = left;int begin = left;int end = right;while (begin < end){while (begin < end && a[end] >= a[key]){end--;}while (begin < end && a[begin] <= a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[key], &a[begin]);key = begin;return key;
}
void QuickSortNonR(int* a, int left, int right)
{if (right - left + 1 < 10){charu(a + left, right - left + 1);}else{Stack as;StackInit(&as);StackPush(&as, right);StackPush(&as, left);while (!StackEmpty(&as)){int begin1 = StackTop(&as);StackPop(&as);int end1 = StackTop(&as);StackPop(&as);int key = yici(a, begin1, end1);if (key + 1 < end1){StackPush(&as, end1);StackPush(&as, key + 1);}if (key - 1 > begin1){StackPush(&as, key - 1);StackPush(&as, begin1);}}StackDestroy(&as);}
}