快速排序学习记录

算法思想 快速排序法（详解）_李小白~的博客-CSDN博客_快速排序

以下为java版：

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5,3,6,45,-5,0,10,18,1};
        quickSort(arr,0,8);
        for(int i = 0; i < arr.length-1; i++){
            System.out.println(arr[i]);
        }
    }
    public static void quickSort(int[] arr,int left, int right){
        if(left > right)
            return;
        int base = arr[left];
        int i = left;
        int j = right;
        int t = 0;

        while(i != j){
            while(arr[j] >= base && i < j){
                j--;
            }
            while(arr[i] <= base && i < j){
                i++;
            }
            if(i < j){
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        arr[left] = arr[i];
        arr[i] = base;
        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
    }
}

---

另外摘自leetcode的大佬的更加简洁明了的代码：

「排序算法」快速排序 - 力扣（LeetCode）

---

public class QuickSort {
    public static void main(String[] args) {
        QuickSort qs = new QuickSort();
        int[] arr = {5,3,6,45,-5,0,10,18};
        qs.quickSort(arr,0,7);
        for(int i = 0; i < arr.length; i++){
            System.out.println(arr[i]);
        }

    }
    public void quickSort(int[] arr,int left, int right){
        //子数组长度为1时终止递归
        if(left >= right)
            return;
        //哨兵划分操作
        int i = partition(arr, left, right);
        //递归左（右）子数组执行哨兵划分、
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

     int partition(int[] arr, int left, int right){
        //以 arr[1]为基准数
        int i = left, j = right;
        while(i < j){
            while(arr[i] <= arr[j] && i < j) j--;
            while(arr[i] >= arr[i] && i > j) i++;
            swap(arr, i, j);
        }
        swap(arr, i, left);
        return i;
    }

    void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

---

算法思想简述：

---

该代码调用三个函数，分别是快速排序主函数，哨兵划分函数，交换函数，每次进入quickSort函数时，首先判断是否结束当前排序，然后对左右哨兵进行划分，进入哨兵函数，将基准值放到哨兵相遇处，并且保证左边都是小于基准值，右边都是大于基准值的，按照此方法进行递归划分，最后排序完毕。