快排的三种方法（附源码）

女爷i 2024-03-27 12:43 25阅读 0赞

#### 文章目录 ####

*  快排
 *   *  1.挖坑法
     *  2.Hoare法
     *  3.前后指针

## 快排 ##

### 1.挖坑法 ###

**原理**：  
取出第一个元素，空出一个位置拿出来定义两个指针，l，r分别指向头和尾，r向左移动如果遇到小于第一个元素的，放入空位，l向右移动，找比第一个元素大的放入刚刚空出来的位置，再次重复，l、r相遇时，将第一个元素放入空的位置，再以其下标为界限，左右用相同的方法继续。所以称为挖坑法。

![在这里插入图片描述][b536e274d1e6463eac7ec8b65160e68c.png]

### 2.Hoare法 ###

**原理：**  
定义l，r从头尾开始，l找比第一个元素大的，r找比第一个元素小的，找到后交换两个元素，直到相遇时，将相遇的元素与第一个元素交换，如何以此基准（相遇时下标），再次左右进行。

![在这里插入图片描述][92f432f0565345c498decc27eb4d7537.png]

### 3.前后指针 ###

**原理：**  
定义指针prev（记录最近一个小于基准的下标），cur，从头开始向后走，将第一个元素作为基准，如果cur遇到小于基准的元素，prev先++，prev指向的元素与cur交换。如果遇到大的继续行走，prev不走。

初始情况：  
![在这里插入图片描述][ff5b1b994de640ba9dc372f217e81ba4.png]  
![在这里插入图片描述][882280438ca841899fec90f31ded9bba.png]  
**代码**  
注意：三种方法只是在划分找基准下标时不同，故前后指针排序只提供partition3()方法。

/*
        快速排序：
    
         */
        //方法一：挖坑法
        public static void quikSort(int[] array) {
        
            //不用一直变化定义的首尾变量封装方法
            quik(array, 0, array.length - 1);
        }
    
        //每一次排序
        private static void quik(int[] array, int start, int end) {
        
            //>=,时return，是会出现基准左右没有元素时，star>end
            if (start >= end) {
        
                return;
            }
            //左右分别调用quik
            //定义基准
            int pivot = partition(array, start, end);
            quik(array, start, pivot - 1);
            quik(array, pivot + 1, end);
        }
    
        //返回每一次划分的下标,left,right,移动
        private static int partition(int[] array, int left, int right) {
        
            int temp = array[left];
            //left==right,时将temp放入array[left]
            while (left < right) {
        
                //必须是判断大于或者等于的情况，
                // 直到小于时减减结束进入左边的循环
                while (left < right && array[right] >= temp) {
        
                    right--;
                }
                array[left] = array[right];
    
                while(left < right && array[left] <= temp) {
        
                    left++;
                }
                array[right] = array[left];
            }
            array[left]=temp;
            return left;
        }
        //方法2，Hoare法
        public static void quikSort2(int[] array) {
        
            //不用一直变化定义的首尾变量封装方法
            quik2(array, 0, array.length - 1);
        }
    
        //每一次排序
        private static void quik2(int[] array, int start, int end) {
        
            //>=,时return，是会出现基准左右没有元素时，star>end
            if (start >= end) {
        
                return;
            }
            //左右分别调用quik
            //定义基准
            int pivot = partition2(array, start, end);
            quik(array, start, pivot - 1);
            quik(array, pivot + 1, end);
        }
    
        private static int partition2(int[] array,int left,int right){
        
            int temp = array[left];
            int i = left;
            while(left<right){
        
                //以左边作为基准，要从右边先走
                while (array[right]>=temp&&right>left){
        
                    right--;
                }
                while(array[left]<=temp&&left<right){
        
                    left++;
                }
                swap(array,left,right);
    //            int temp2 = array[right];
    //            array[right] = array[left];
    //            array[left] = temp2;
            }
            //相遇时,交换原第一个元素与相遇元素
            //由于第一个元素下标在变化，所以需要记录为i
            swap(array,left,i);
    //        array[i] = array[left];
    //        array[left] = temp;
            return left;
        }
    
        //前后指针法，了解
        private static int partition3(int[]array,int left,int right){
        
            int prev = left;
            int cur = left+1;
            //cur走到尾结束
            while (cur<=right){
        
                //cur遇到小的（prev先++，此时prev指向的是大于基准的）交换，为了把小的放到前面
                //cur指向的值小于第一个元素并且prev前进一步不等于cur（prev与cur重合）时，
                if (array[cur]<array[left]&&array[++prev]!=array[cur]){
        
                    swap(array,cur,prev);
                }
                cur++;
            }
            swap(array,prev,left);
            return prev;
        }

[b536e274d1e6463eac7ec8b65160e68c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c36cd8a79ea743768314c5b211af93e2.png
[92f432f0565345c498decc27eb4d7537.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9506f7ded8ed4c75a065f230e674a6e5.png
[ff5b1b994de640ba9dc372f217e81ba4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e9b5631127ef41a3a2694359083c4217.png
[882280438ca841899fec90f31ded9bba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/dadb8645aacb4def96354eb68032f86e.png