深圳幻海软件技术有限公司 欢迎您！
更多

全网最全的快速排序方法--Hoare快排 挖坑法快排 二路快排 三路快排 非递归快排

2023-05-08

int arr left
目录一.快速排序1.基本介绍2.基本思想二.Hoare快排0.前情知识1.交换数组中的两个元素2.指定范围的插入排序1.基本思路2.代码实现3.优化思路三.挖坑法快排(校招中适用)1.基本思路2.代码实现四.二路快排1.基本思路2.代码实现3.优化思路五.三路快排1.基本思路2.代码实现六.非递归快

目录

一.快速排序

1.基本介绍

2.基本思想

二.Hoare快排

0.前情知识

1.交换数组中的两个元素

2.指定范围的插入排序

1.基本思路

2.代码实现

3.优化思路

三.挖坑法快排(校招中适用)

1.基本思路

2.代码实现

四.二路快排

1.基本思路

2.代码实现

3.优化思路

五.三路快排

1.基本思路

2.代码实现

六.非递归快排的实现

1.思路分析

2.代码实现

一.快速排序

1.基本介绍

快速排序（Quicksort）由英国计算机科学家Tony Hoare于1959年发明，是一种经典的排序算法，被广泛应用于计算机科学领域。快速排序（Quick Sort）是一种常见的基于比较的排序算法，也是最常用的排序算法之一。

快速排序是一种

排序方法
最好
平均
最坏
空间复杂度
稳定性
快速排序
O(n * log(n))
O(n * log(n)) O(n^2) O(log(n)) ~ O(n) 不稳定

稳定性:如果a原本在b前面，并且a=b,排序之后a仍然在b的前面,那么就成这个算法是稳定的,否则就是不稳定的;

2.基本思想

以下是快速排序的基本思路

  1. 选择一个基准元素（pivot）。

  2. 将序列中所有小于基准元素的元素放在基准元素的左侧，所有大于基准元素的元素放在右侧。

  3. 递归地对基准元素左侧和右侧的子序列进行排序。

  4. 递归结束后，整个序列就变得有序。

以下介绍的各种快排的思路都大致一样的,主要就是在划分的策略不一样,基本思路都是一样的

二.Hoare快排

0.前情知识

1.交换数组中的两个元素

  1.     public static void swap(int[] arr, int i, int j) {
  2.         int temp = arr[i];
  3.         arr[i] = arr[j];
  4.         arr[j] = temp;
  5.     }

2.指定范围的插入排序

  1.     /**
  2.      * 将区间[left,right]的元素进行插入排序
  3.      *
  4.      * @param arr
  5.      * @param left
  6.      * @param right
  7.      */
  8.     private static void insertSortInterval(int[] arr, int left, int right) {
  9.         for (int i = left + 1; i <= right; ++i) {
  10.             for (int j = i; j > left && arr[j] < arr[j - 1]; --j) {
  11.                 swap(arr, j, j - 1);
  12.             }
  13.         }
  14.     }

1.基本思路

我们这里重点介绍分区的方法,因为这几个快速排序的区别主要就是在分区的方法,快速排序的基本思路我们在上面已经说出,在这里就不赘述了.

这里来讲解分区的方法,也就是partition部分的代码.

其实简而言之而很好理解,我们选取左端的值作为中轴值,定义两个指针i,j,  j从右端向左进行遍历,当遍历到比中轴值(pivot)小的数时候,停止,i从左端向右进行遍历,当遍历到比中轴值大的时候,停止,这个时候交换位置i和位置j的元素 ,当i==j的时候,停止循环,然后交换位置left和i(j)的元素,此时i左边的元素比arr[i]小,i右边的元素比arr[i]大,返回此时的位置i.

初始情况:

第一次交换

第二次交换

 结束循环

中轴值交换操作

此时pivot=6左边的元素都比6的值小,右边的值都比pivot大了,这样一次分区结束.

2.代码实现

  1.     //Hoare版快排
  2.     public static void quickSortHoare(int[] arr) {
  3.         quickSortHoareInternal(arr, 0, arr.length - 1);
  4.     }
  5.  
  6.     private static void quickSortHoareInternal(int[] arr, int left, int right) {
  7.         if (left >= right) {
  8.             return;
  9.         }
  10.         int pivotIndex = partitionHoare(arr, left, right);
  11.         quickSortHoareInternal(arr, left, pivotIndex - 1);
  12.         quickSortHoareInternal(arr, pivotIndex + 1, right);
  13.  
  14.     }
  15.  
  16.     private static int partitionHoare(int[] arr, int left, int right) {
  17.         //选取最左边的元素作为中轴值
  18.         int pivot = arr[left];
  19.         int i = left, j = right;
  20.         while (i < j) {
  21.             //从右边找到比pivot小的元素
  22.             while (i < j && arr[j] >= pivot) {
  23.                 j--;
  24.             }
  25.  
  26.             //从左边找到比pivot大的元素
  27.             while (i < j && arr[i] <= pivot) {
  28.                 i++;
  29.             }
  30.             swap(arr, i, j);
  31.  
  32.         }
  33.         //将中轴值元素和i==j时的位置交换,此时i左边的元素都比pivot小,右边都比pivor大
  34.         swap(arr,i,left);
  35.         return i;
  36.  
  37.     }

3.优化思路

优化一:学习过插入排序我们知道,对于小数组来说,插入排序的效率可谓是十分的高,对于长度小于64的小数组,我们不妨直接使用插入排序进行排序

  1.     private static void quickSortHoareInternal(int[] arr, int left, int right) {
  2.         if (right - left <= 64) {
  3.             insertSortInterval(arr, left, right);
  4.             return;
  5.         }
  6.         int pivotIndex = partitionHoare(arr, left, right);
  7.         quickSortHoareInternal(arr, left, pivotIndex - 1);
  8.         quickSortHoareInternal(arr, pivotIndex + 1, right);
  9.  
  10.     }

优化二:我们来考虑这样一个问题,当我们需要排序的数组基本有序的时候,我们每次还是选择数组的第一个元素作为中轴值,这样我们要进行递归O(n)的空间复杂度,这个时候快速排序就退化为了冒泡排序,时间复杂度为O()

那我们该如何选取中轴值呢?

第一种方法:随机选取中轴值

生成一个范围为[left,right]的随机数生成下标为index,将index与left交换,之后就和我们之前的代码一模一样了.

  1.     private static int partitionHoare(int[] arr, int left, int right) {
  2.         //优化,选取随机值
  3.         int index = ThreadLocalRandom.current().nextInt(left, right + 1);
  4.         swap(arr, index, left);
  5.         int pivot = arr[left];
  6.         int i = left, j = right;
  7.         while (i < j) {
  8.             //从右边找到比pivot小的元素
  9.             while (i < j && arr[j] >= pivot) {
  10.                 j--;
  11.             }
  12.  
  13.             //从左边找到比pivot大的元素
  14.             while (i < j && arr[i] <= pivot) {
  15.                 i++;
  16.             }
  17.             swap(arr, i, j);
  18.  
  19.         }
  20.         swap(arr, i, left);
  21.         return j;
  22.  
  23.     }

第二种方法:三数中值分割法

我们都希望我们选取的中轴值恰好为待排序数组的中值,这样递归的次数一定是最少的,因此我们可以使用三数取中的方法来进行估算中值(当然最坏情况也可能取到第二小的情况,但概率相对来说很小),我们通常选取左端,右端,中心位置上的三个元素的中值作为枢纽元素.来看代码实现

  1.     public static void median(int[] arr, int left, int right) {
  2.         //中间索引下标,相当于(left+right)/2
  3.         int center = left + ((right - left) >> 1);
  4.         if (arr[center] < arr[left]) {
  5.             swap(arr, center, left);
  6.         }
  7.         if (arr[right] < arr[left]) {
  8.             swap(arr, right, left);
  9.         }
  10.         if (arr[right] < arr[center]) {
  11.             swap(arr, center, right);
  12.         }
  13.         swap(arr, left, center);//此时中值被交换到了最左边位置
  14.     }
  15.  
  16.     private static int partitionHoare(int[] arr, int left, int right) {
  17.         median(arr,left,right);
  18.         int pivot = arr[left];
  19.         int i = left, j = right;
  20.         while (i < j) {
  21.             //从右边找到比pivot小的元素
  22.             while (i < j && arr[j] >= pivot) {
  23.                 j--;
  24.             }
  25.  
  26.             //从左边找到比pivot大的元素
  27.             while (i < j && arr[i] <= pivot) {
  28.                 i++;
  29.             }
  30.             swap(arr, i, j);
  31.  
  32.         }
  33.         swap(arr, i, left);
  34.         return j;
  35.  
  36.     }

三.挖坑法快排(校招中适用)

1.基本思路

挖坑法快排的基本思路:我们先把pivot的值保留下来,此时相当于在pivot位置(也就是left位置)挖了一个坑,然后我们开始循环,循环条件和Hoare快排一样,j从右端向左找到比pivot小的元素,将arr[j]的值填到之前挖的坑(也就是left位置),然后在j位置挖一个坑,i从左端开始寻找比pivot大的元素,找到后将它填到j位置(之前挖的坑),以此类推,最终i==j,这是挖的最后一个坑,将pivot值填入到arr[i]的位置,此时我们挖坑填坑操作完成,arr[i]左边的元素都比它小,右边的元素都比它大

可以看出来的是:相对于Hoare快排来说,交换的次数大大减少

 第一次挖坑填坑

 第二次挖坑填坑

 第三次挖坑填坑

 第四次挖坑填坑

 第五次挖坑填坑

最后一次arr[i]=pivot

2.代码实现

优化的地方和Hoare快排一样,这里直接给出优化之后的代码,这里采用了随机值选取中轴值的方法.

  1.     //挖坑法快排
  2.     public static void quickSortHole(int[] arr) {
  3.         quickSortHoleInternal(arr, 0, arr.length - 1);
  4.     }
  5.  
  6.     private static void quickSortHoleInternal(int[] arr, int left, int right) {
  7.         if (right - left <= 64) {
  8.             insertSortInterval(arr, left, right);
  9.             return;
  10.         }
  11.         int pivotIndex = partitionByHole(arr, left, right);
  12.         quickSortHoleInternal(arr, left, pivotIndex - 1);
  13.         quickSortHoleInternal(arr, pivotIndex + 1, right);
  14.  
  15.     }
  16.  
  17.     private static int partitionByHole(int[] arr, int left, int right) {
  18.         //优化,选取随机值
  19.         int index = ThreadLocalRandom.current().nextInt(left, right + 1);
  20.         swap(arr, index, left);
  21.         int pivot = arr[left];
  22.         int i = left, j = right;
  23.         while (i < j) {
  24.             //从右边找到比pivot小的元素
  25.             while (i < j && arr[j] >= pivot) {
  26.                 j--;
  27.             }
  28.             //将这个小的元素放到左边
  29.             arr[i] = arr[j];
  30.             //从左边找到比pivot大的元素
  31.             while (i < j && arr[i] <= pivot) {
  32.                 i++;
  33.             }
  34.             //将这个大的元素放到右边
  35.             arr[j] = arr[i];
  36.  
  37.         }
  38.         //最后一定是i==j退出
  39.         arr[j] = pivot;
  40.         return j;
  41.  
  42.     }

四.二路快排

1.基本思路

二路快排其实就是分区进行,也是国外教材上实现的快排的方法(算法4),总体的效率要比挖坑法和Hoare法要快一些.

主要就是维护两个分区,一个分区的值全比pivot的值小,另一个分区的值大于等于pivot的值,最终分区完毕之后的结果如下图所示:

维护的小于pivot的区间为[left+1,j]  维护的大于等于pivot的区间为[j+1,i-1] 其中i指向的是正在遍历到的元素位置,j指向的是小于pivot区间的最后位置,j+1是大于等于pivot的开始位置.白色的区域表示未遍历到的区域.

现在我们来讨论两种情况,一种是当arr[i]>=pivot的时候,这个时候我们只需要将i指向位置的变为黄色,也就是将i++处理,这是时候大于等于pivot的区间就相当于增加了一个元素

另一种是arr[i]<pivot的时候,这个时候我们只需要将arr[i]的元素和arr[j+1]的元素进行交换,并且要将j++,然后将i++,这样小于pivot的区间就增加了一个元素.

这样一种循环下去,直到i遍历完最后一个元素的时候,这个时候我们将j位置的元素和left位置的元素进行交换,这样就实现了pivot元素左边的元素小于pivot,pivot右边的元素大于等于pivot.

 具体的代码实现看下面

2.代码实现

  1.     // 算法4的分区快排
  2.     public static void quickSort(int[] arr) {
  3.         quickSortInternal(arr, 0, arr.length - 1);
  4.     }
  5.  
  6.     private static void quickSortInternal(int[] arr, int left, int right) {
  7.         if (right - left <= 64) {
  8.             insertSortInterval(arr, left, right);
  9.             return;
  10.         }
  11.         int p = partition(arr, left, right);
  12.         quickSortInternal(arr, left, p - 1);
  13.         quickSortInternal(arr, p + 1, right);
  14.     }
  15.  
  16.     //二路快排,左半部分小于pivot,右半部分大于等于pivot
  17.     private static int partition(int[] arr, int left, int right) {
  18.         int randomIndex = ThreadLocalRandom.current().nextInt(left, right + 1);
  19.         swap(arr, left, randomIndex);
  20.         int pivot = arr[left];
  21.         // arr[l + 1..j] < pivot
  22.         int j = left;
  23.         // arr[j + 1..i) >= pivot
  24.         for (int i = left + 1; i <= right; i++) {
  25.             if (arr[i] < pivot) {
  26.                 swap(arr, j + 1, i);
  27.                 j++;
  28.             }
  29.         }
  30.         swap(arr, j, left);
  31.         return j;
  32.     }

3.优化思路

当我们出现大量相同元素的时候,这个时候二路快排的其实效率并不是很快,因为要进行很多次无用的递归处理,这个时候我们是否可以考虑单独分成一个分区是等于pivot的呢?确实是可以实现的,这个时候我们采用三路快排的方式,可以很大程度上解决我们所说的问题

五.三路快排

1.基本思路

三路快排的实现思路和二路快排的实现思路基本一样,只不过多维护一个等于pivot的区间,这样我们进行递归的时候,就没必要递归的进行等于pivot的区间部分,大大提高了快速排序的效率.

以下为三路快排分区的格局:

维护小于pivot的区间为[left,lt],维护等于pivot的区间为[lt+1,i-1],维护大于pivot的区间为[gt,right]. i表示正在遍历到的位置索引,当i>=gt的时候遍历结束白色的区域表示未遍历到的区域.

三路快排有三种情况需要考虑

1.当arr[i]>pivot的时候,我们可以将arr[i]与arr[lt+1]进行交换,并且将i++,这个时候小于pivot的区间增加

2.当arr[i]==pivot的时候,我们直接将i++即可,这个时候等于pivot的区间增加,处理结束

3.当arr[i]>pivot的时候,我们可以将arr[i]与arr[gt-1]进行交换,并且gt--,表示大于pivot的区间增加.这个时候i不需要增加,因为交换的区域是白色的区域,没有遍历到的,我们需要下一次进行判断

 最终当i==gt的时候循环结束,我们将arr[left]和arr[lt]的元素进行交换

递归的条件现在为left-->lt-1      gt-->right

2.代码实现

  1.     //三路快排(对于处理含有重复元素的数组很有效)
  2.     public static void quickSort3(int[] arr) {
  3.         quickSort3Internal(arr, 0, arr.length - 1);
  4.     }
  5.  
  6.     private static void quickSort3Internal(int[] arr, int left, int right) {
  7.         if (right - left <= 64) {
  8.             insertSortInterval(arr, left, right);
  9.             return;
  10.         }
  11.         int radomIndex = ThreadLocalRandom.current().nextInt(left, right + 1);
  12.         //此时left位置为中轴值
  13.         swap(arr, left, radomIndex);
  14.         int pivot = arr[left];
  15.         //区间[left+1,lt]的值<pivot
  16.         int lt = left;
  17.         //区间[gt,right]的值>pivot
  18.         int gt = right + 1;
  19.         //区间(lt,gt)的元素==pivot
  20.         //目前遍历到的位置
  21.         int i = left + 1;
  22.         //终止条件i与gt重合
  23.         while (i < gt) {
  24.             if (arr[i] < pivot) {
  25.                 swap(arr, i, lt + 1);
  26.                 lt++;
  27.                 i++;
  28.             } else if (arr[i] > pivot) {
  29.                 swap(arr, i, gt - 1);
  30.                 gt--;
  31.             } else {//相等的情况
  32.                 i++;
  33.  
  34.             }
  35.         }
  36.         swap(arr, left, lt);
  37.         quickSort3Internal(arr, left, lt - 1);
  38.         quickSort3Internal(arr, gt, right);
  39.  
  40.     }

六.非递归快排的实现

1.思路分析

其实非递归的快排也是很好实现的,我们仔细观察之前的代码可以发现,其实快速排序的代码是很像二叉树的前序遍历的,都是先处理,然后向左进行递归处理,向右进行递归处理:对二叉树递归和迭代实现不清楚的可以看这篇博客:树的遍历方式(前中后,层序遍历,递归,迭代,Morris遍历)

我们在实现迭代二叉树前序遍历的时候采用了栈这种结构,我们在这里也要借用栈来实现快速排序的非递归实现.那我们在栈中要保存什么信息呢,我们在进行递归实现快速排序的时候,每一次递归的都是left和right进行改变的递归,这里我们肯定是要保存left和right的,然后取出来left和right进行分区(partition)处理,但是我们需要注意的是保存的顺序应该时反向的,也就是先保存right,再保存left,因为栈性质:先进后出,这样才能保证和递归的顺序是一致的.

具体看代码的实现.

2.代码实现

  1.     //非递归快排(挖坑)
  2.     public static void quickSortNoRecursion(int[] arr) {
  3.         LinkedList<Integer> stack = new LinkedList<>();
  4.         stack.push(arr.length - 1);
  5.         stack.push(0);
  6.         while (!stack.isEmpty()) {
  7.             Integer left = stack.pop();
  8.             Integer right = stack.pop();
  9.             if (right - left <= 64) {
  10.                 insertSortInterval(arr, left, right);
  11.                 continue;
  12.             }
  13.             int pivotIndex = partitionByHole(arr, left, right);
  14.             stack.push(right);
  15.             stack.push(pivotIndex + 1);
  16.             stack.push(pivotIndex - 1);
  17.             stack.push(left);
  18.  
  19.         }
  20.  
  21.  
  22.     }
  23.     //这里使用的挖坑法快排的划分方式,也可以使用别的快排的划分方式
  24.     private static int partitionByHole(int[] arr, int left, int right) {
  25.         //优化,选取随机值
  26.         int index = ThreadLocalRandom.current().nextInt(left, right + 1);
  27.         swap(arr, index, left);
  28.         int pivot = arr[left];
  29.         int i = left, j = right;
  30.         while (i < j) {
  31.             //从右边找到比pivot小的元素
  32.             while (i < j && arr[j] >= pivot) {
  33.                 j--;
  34.             }
  35.             //将这个小的元素放到左边
  36.             arr[i] = arr[j];
  37.             //从左边找到比pivot大的元素
  38.             while (i < j && arr[i] <= pivot) {
  39.                 i++;
  40.             }
  41.             //将这个大的元素放到右边
  42.             arr[j] = arr[i];
  43.  
  44.         }
  45.         //最后一定是i==j退出
  46.         arr[j] = pivot;
  47.         return j;
  48.  
  49.     }

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45765 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪