devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】七大排序之快速排序详解（挖坑法快排，非递归快排，二路快排，三路快排）_快速排序过程

作者：菜鸟追梦旅行 | 2024-05-06 12:21:28

赞

踩

快速排序过程

目录

1.快速排序核心思路

2.挖坑法快速排序（递归）

2.1步骤

 2.2代码（详细注释）

3.非递归快排（用栈实现快速排序）

3.1思路

3.2代码

 4.二路快排

4.1思路

4.2代码

5.三路快排

5.1思路

5.2代码

1.快速排序核心思路

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程。

补充：选取分区点时尽可能的随机，保证分区点两侧都有元素。

分区点的选择：

1.三数取中法：在无序数组的首，中，尾这三个数据中，选择一个排在中间的数据作为分区点。

2.随机数法：在无序数组中随机选取一个数作为分区点。

2.挖坑法快速排序（递归）

2.1步骤

    1.设定一个分区点（一般为序列的最左边元素，也可以是最右变的元素）此时最左边的是一个坑。这里选择最左边元素7作为分区点。


    2.开辟两个指针，分别指向序列的头结点和尾结点（选取的分区点在左边，则先从右边出发。反之，选取的分区点在右边，则先从左边出发）。


    3.从右指针出发依次遍历序列，如果找到一个值比所选的分区点要小，则将此指针所指的值放在坑里，左指针向前移。此时j遍历到1这个位置,1<7，将1填入i所指的坑里。


    4.后从左指针出发（选取的分区点在左边，则后从左边出发。反之，选取的分区点在右边，则后从右边出发），依次便利序列，如果找到一个值比所选的分区点要大，则将此指针所指的值放在坑里，右指针向前移。


  5.  依次循环步骤4,5，直到左指针和右指针重合时，我们把分区点放入这连个指针重合的位置。

 2.2代码（详细注释）

  1.     //挖坑法快速排序
  2.     public static void quickSortHole(int[] arr){
  3.         quickSortInternal(arr,0,arr.length);
  4.     }
  5.  
  6.     private static void quickSortInternal(int[] arr, int l, int r) {
  7.         //小数组使用直接插入排序最快
  8.         if(r-l<=64){
  9.             insertionSort(arr,l,r);
  10.             return;
  11.         }
  12.         //先找到第一次排序后分区点的索引
  13.         int p=partitionByHole(arr,l,r);
  14.         //将分区点左边元素进行快速排序
  15.         quickSortInternal(arr,l,p-1);
  16.         //将分区点右边元素进行快速排序
  17.         quickSortInternal(arr,p+1,r);
  18.     }
  19.  
  20.     private static int partitionByHole(int[] arr, int l, int r) {
  21.         //这里分区点定位最左边的值
  22.         int pivot=arr[l];
  23.         //两个指针，分别指向序列的头节点和尾节点
  24.         int i=l;
  25.         int j=r;
  26.         while(i<j){
  27.             //先从后向前遍历
  28.             while(i<j && arr[j]>pivot){
  29.                 j--;
  30.             }
  31.             //此时j指针停在第一个小于pivot的地方，将这个值放入i所指的坑里，那么j所指的地方就变为了一个坑
  32.             swap(arr,i,j);
  33.             //然后从前向后遍历
  34.             while(i<j && arr[i]<pivot){
  35.                 i++;
  36.             }
  37.             //此时i指针停在第一个大于pivot的地方，将这个值放入j所指的坑里
  38.             swap(arr,i,j);
  39.         }
  40.         //此时，i和j指向同一位置，回填分区点
  41.         arr[i]=pivot;
  42.         return i;
  43.     }
  44.  
  45.     //直接插入排序,选取无序区间的第一个元素插入到有序区间的正确位置上
  46.     private static void insertionSort(int[] arr, int l, int r) {
  47.         //无序区间[i,r)
  48.         //有序区间[l,i)
  49.         //无序区间的每一个元素遍历一遍
  50.         for(int i=l+1;i<r;i++){
  51.             //将无序区间的第一个元素与有序区间的元素比较
  52.             for(int j=i;j>l;j--){
  53.                 if(arr[j]<arr[j-1]){
  54.                     swap(arr,j,j-1);
  55.                 }
  56.             }
  57.         }
  58.     }
  59.  
  60.     private static void swap(int[] arr, int i, int j) {
  61.         int temp=arr[i];
  62.         arr[i]=arr[j];
  63.         arr[j]=temp;
  64.     }

3.非递归快排（用栈实现快速排序）

3.1思路

递归调用的本质就是栈，栈是一个先进后出的数据结构。

1.将区间的左右两边入栈。让right取栈顶元素（是我们后入的区间的右边），再删除栈顶的元素。同样，让left取先入但是后出的元素（区间的左边）。此时我们拿到了一个区间[left,right],我们对这个区间进行一次快速排序。

2.此时一个分区点到了正确的位置，我们继续对左边区间和右边区间的首尾入栈。

3.当栈为空时，说明排序完成。

3.2代码

  1.     //非递归的快排(栈)
  2.     public static void quickSortNonRecursion(int[] arr){
  3.         Deque<Integer>stack=new ArrayDeque<>();
  4.         stack.push(arr.length-1);
  5.         stack.push(0);
  6.         while(!stack.isEmpty()){
  7.             int l=stack.pop();
  8.             int r=stack.pop();
  9.             if(l>=r){
  10.                 continue;
  11.             }
  12.             int p=partitionByHole(arr,l,r);
  13.             //处理左半区间
  14.             stack.push(p-1);
  15.             stack.push(l);
  16.             //处理右半区间
  17.             stack.push(r);
  18.             stack.push(p+1);
  19.         }
  20.     }
  21.     private static int partitionByHole(int[] arr, int l, int r) {
  22.         //这里分区点定位最左边的值
  23.         int pivot=arr[l];
  24.         //两个指针，分别指向序列的头节点和尾节点
  25.         int i=l;
  26.         int j=r;
  27.         while(i<j){
  28.             //先从后向前遍历
  29.             while(i<j && arr[j]>pivot){
  30.                 j--;
  31.             }
  32.             //此时j指针停在第一个小于pivot的地方，将这个值放入i所指的坑里，那么j所指的地方就变为了一个坑
  33.             swap(arr,i,j);
  34.             //然后从前向后遍历
  35.             while(i<j && arr[i]<pivot){
  36.                 i++;
  37.             }
  38.             //此时i指针停在第一个大于pivot的地方，将这个值放入j所指的坑里
  39.             swap(arr,i,j);
  40.         }
  41.         //此时，i和j指向同一位置，回填分区点
  42.         arr[i]=pivot;
  43.         return i;
  44.     }
  45.  
  46.     //直接插入排序,选取无序区间的第一个元素插入到有序区间的正确位置上
  47.     private static void insertionSort(int[] arr, int l, int r) {
  48.         //无序区间[i,r)
  49.         //有序区间[l,i)
  50.         //无序区间的每一个元素遍历一遍
  51.         for(int i=l+1;i<r;i++){
  52.             //将无序区间的第一个元素与有序区间的元素比较
  53.             for(int j=i;j>l;j--){
  54.                 if(arr[j]<arr[j-1]){
  55.                     swap(arr,j,j-1);
  56.                 }
  57.             }
  58.         }
  59.     }
  60.  
  61.     private static void swap(int[] arr, int i, int j) {
  62.         int temp=arr[i];
  63.         arr[i]=arr[j];
  64.         arr[j]=temp;
  65.     }

 4.二路快排

对于上面我写的快排，将小于等于基准值的数据全都放到了左边，大于的放到右边了，那么这样就会出现问题。不管是当条件大于等于还是小于等于，当数组中重复元素非常多的时候，等于基准值的元素太多，那么数组就会分成极度不平衡的两个部分，因为等于基准值的一部分总是集中在数组的一边。

此时，使用二路快排就可以进行优化，阻止效率的降低。

4.1思路

1.正如其名，选取最左边为分区点，将整个区间分为两条路，一路是大于等于分区点的元素（橙色部分），一路是小于与分区点的元素（粉色部分）。分区点v的下标此时为l，i指向当前正在扫描的数组元素。区间[l+1,j]为小于分区点的元素区间，区间[j+1,i]为大于等于分区点元素的区间。

 2.当arr[i]>=v时，直接i++即可。

 3.当arr[i]<v时，交换arr[j+1]和arr[i]。然后j++。

 4.当扫描完数组之后，将分区点和j所指元素交换，回填分区点，数组为如下分区。

4.2代码

  1.     //二路快排
  2.     public static void quickSort2(int[] arr){
  3.         quickSortInternal(arr,0,arr.length);
  4.     }
  5.  
  6.     private static void quickSortInternal(int[] arr, int l, int r) {
  7.         if(r-l<=64){
  8.             insertionSort(arr,l,r);
  9.             return;
  10.         }
  11.         int p=partition(arr,l,r);
  12.         quickSortInternal(arr,l,p-1);
  13.         quickSortInternal(arr,p+1,r);
  14.     }
  15.  
  16.     private static int partition(int[] arr, int l, int r) {
  17.         //最左边元素作为分区点
  18.         int v=arr[l];
  19.         //初始j指向l
  20.         int j=l;
  21.         //初始i指向分区点后面第一个元素
  22.         for(int i=l+1;i<r;i++){
  23.             if(arr[i]<v){
  24.                 swap(arr,i,j+1);
  25.                 j++;
  26.             }
  27.         }
  28.         //回填分区点
  29.         swap(arr,l,j);
  30.         return j;
  31.     }

5.三路快排

三路快排就是在快速排序的基础上进一步优化的，它将数据分为三个部分：大于分区点，小于分区点和等于分区点。

5.1思路

1.将数据分为三个部分，i指向当前数组正在处理的元素。

区间[l+1,lt]为小于分区点的元素区间

区间[lt+1,i]为等于分区点的元素区间

区间[gt,r]为大于分区点的元素区间

 2.当arr[i]==v时,i++即可。

3.当arr[i]>v时，交换arr[i]和arr[gt-1]

 4.当arr[i]<v时，交换arr[i]和arr[lt]。当i和gt重合时，整个数组交换完毕。

5.2代码

  1.     //三路快排
  2.     public static void quickSort3(int[] arr){
  3.         quickSortInternal3(arr,0,arr.length-1);
  4.     }
  5.  
  6.     private static void quickSortInternal3(int[] arr, int l, int r) {
  7.         if(r-l<=64){
  8.             insertionSort(arr,l,r);
  9.             return;
  10.         }
  11.         int v=arr[l];
  12.         int lt=l;
  13.         int gt=r+1;
  14.         int i=l+1;
  15.         //终止条件为i和gt重合
  16.         while(i<gt){
  17.             if(arr[i]<v){
  18.                 swap(arr,lt+1,i);
  19.                 lt++;
  20.                 i++;
  21.             }else if(arr[i]>v){
  22.                 swap(arr,gt-1,i);
  23.                 gt--;
  24.             }else{
  25.                 i++;
  26.             }
  27.         }
  28.         //回填分区点
  29.         swap(arr,l,lt);
  30.         quickSortInternal3(arr,l,lt-1);
  31.         quickSortInternal3(arr,gt,r);
  32.     }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/544167
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号