【JAVA】快速排序

快排，和冒泡排序一样，是同一类型的排序，都是交换排序

交换，涉及在遍历中比较，然后相互交换元素

冒泡排序是根据趟数两两比较，边比较边交换，快排也一样，不过冒泡是以顺序表的格式进行的，而快排则是建立在二叉树的基础上来完成遍历交换的~（个人理解）

快排有很多个版本，快速排序是一位名hoare的人发明的，快排有很多个版本，什么horae版本，什么挖坑法，什么双指针法，这里我们介绍horae版本，至于挖坑法和双指针以后有机会再说~

---

已经说了，快排基于二叉树的规则来进行排序，那么具体是怎么样的呢？

比如说我们先搞一个无序数组，然后定义left和right分别是数组的头尾下标

然后定义一个基准值  key  这个key  是用来划分数组的，当遍历交换完一次后，key下标所对应的值会在这个数组的某个位置，但是key左边的元素都会比key下标对应的元素小，key左边的元素都会比key下标对应的元素值要大，这就很类似于二分查找的时候的划分一样~

那具体是怎么样遍历和划分的呢？下面让老衲给你画张图即可

 

 下面我来解说一下第一轮的过程，首先给出了一个无序数组，把6设置为基准，然后存一份，接着right开始减减，遇到比6小的就停下来，所以right先减到了3后，停下不动，此时3比6这个基准小，然后right不动了，开始轮到left++，left的目的是寻找比基准6大的值，所以left++到了7，就停下，此时left对应的7比基准6大，接着把right的3和left的7开始交换，交换后left对应3，right对应7，接着right接着开始往下减减，寻找比基准6小的值，当减到4的时候right停止不动，然后接left开始++，寻找比6大的值，一直++到right，没有再比6大值，并且此时left和right相遇，暗示着第一轮循环结束，此时left和right相遇后，把它们相遇下标的值，也就是4，开始和最开始的基准，也就是下标为0的值，也就是6，开始交换：完成交换后，你会发现此时6的左边都是比6小的数，6的右边都是比6大的数，接着根据6所在的位置，开始划分成两部分，一部分比6小，一部分比6大

划分好后，我们现在只看比6小的部分，比6大的部分同理，看懂比6小的部分就行了

划分后，我们看比6小的 把它当做一个新数组  值 为  4   2   3 

然后根据上面的过程再来一遍，我们把这个数组的0下标元素4看作基准值，然后right对应3，我们开始right--，我们发现此时right的3就是比4小的，所以不动，接着left开始++，找比4大的，一直++到3，没发现比4大的，此时left和right又相遇了，接着再次划分，只有比4小的部分，没有比4大的部分了，那么我们就划分出比4小的部分

划分出3  2  后，我们按照刚才的过程再来一遍，把3看作基准，right--找比3小的，left++找比3大的，直到left和right再次相遇，然后再划分

一直到最后只剩下一个节点2的时候，就完成了遍历，接着返回，没错，就是递归的返回，所以快排要基于二叉树加上递归来实现，嘻嘻~~~

---

下面展示代码，再说说细节~

public class 快排 {
    public static void main(String[] args) {
        int[] arr = {3,5,2,1,43,33,22,64,74,25,13,27,98,56,100,21,7};
        quickSort(arr);
        for(int x : arr){
            System.out.print(x + " ");
        }
 
    }
 
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
 
    private static void quick(int[] array, int left, int right) {
 
        //递归结束条件:这里代表只有一个根   大于号：有可能没有子树  1  2  3   4  1为基准，pivot-1就越界了
        if(left >= right){
            return;
        }
 
        int pivot = partition(array, left, right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
 
    public static int partition(int[] array,int start, int end){
        int i = start;//这里存开始时基准的下标，为了循环结束后，相遇值和基准值交换时能找到基准值的下标
        int key = array[start];//这是基准
        while (start < end){
            while (start < end && array[end] >= key){
                end--;
            }
            while (start < end && array[start] <= key){
                start++;
            }
            swap(array,start,end);
        }
        //到这里s和e相遇，把相遇值和基准值交换
        swap(array,start,i);
        return start;//返回基准下标
    }
 
    public static void swap(int[] array, int n, int m){
        int temp = array[n];
        array[n] = array[m];
        array[m] = temp;
    }
 
}

写快排就3个主要方法，一个是交换swap，一个是找基准partition，一个是递归过程quick方法，递归直到left >= right 的时候返回~

---

第一个方法quick是递归用的，主要是划分数组的功能，返回条件是left >= right

假如你的数组是1 2 3 4的话，我们让第一个元素为基准，如果要划分的话，只能划分比1大的部分，方法里面又会自动划分比1小的部分，也就是基准下标减一，那么就越界了

---

为什么要right先动，而不是left先动，那是因为我们以left为基准，如果left先动，划分好后，你会发现基准左边的值存在比基准大的值，而我们的策略是基准左边比基准小，基准右边比基准大~

---

partition方法里面有一个大while包含着两个小while，小while是独立的while，

所以要加上start < end

同时&&后面的array【end】 >= key, 为什么要是等于呢？如果不等于，假如你的数组头和尾相同

比如说   3  7 5  8  4   3，就会出现死循环了，3不大于3，而是等于3~

---

ok到这里就结束战斗了，老衲要去睡觉了~