【算法-排序算法-快速排序】

排序算法和搜索算法是我们最先接触到的基本的算法。越是基础越是重要。
排序算法常用的大概有五种左右，其中基本的三个为选择排序、冒泡排序、插入排序，高级一点有归并排序和快速排序。

本文主要介绍快排

快排的主要思路就是二分思想+递归调用，其中在判断中间索引位置又有两种思路，代码如下：

//思路一
public class QuickSort1 {

    public static void qs(int[] arrs, int low, int high) {
        if (low >= high) {
            return;
        }
        int partition = partition(arrs, low, high);
        qs(arrs, low, partition - 1);
        qs(arrs, partition + 1, high);
    }

    public static int partition(int[] arrs, int low, int high) {
        int i = low;//左侧哨兵
        int j = high;//右侧哨兵
        //以第一个元素为基准
        int temp = arrs[low];

        while (i < j) {
            while (i < j && arrs[j] >= temp) {
                j--;
            }
            while (i < j && arrs[i] <= temp) {
                i++;
            }
            swap(arrs, i, j);
        }
        swap(arrs, low, j);
        return i;
    }

    public static void swap(int[] arrs, int i, int j) {
        int tmp = arrs[i] + arrs[j];
        arrs[i] = tmp - arrs[i];
        arrs[j] = tmp - arrs[i];
    }

    public static void main(String[] args) {
        int[] a = {3, 21, 5, 8, 9, 6, 3, 1, 2, 5, 21, 9, 1, 3, 7, 4, 5};
        qs(a, 0, a.length - 1);
        System.out.println();
        for (int b : a) {
            System.out.print(b + " ");
        }
    }
}

//思路二
public class QuickSort2 {

    public static void qs(int[] arrs, int low, int high) {
        if (low >= high) {
            return;
        }
        int partition = partition(arrs, low, high);
        qs(arrs, low, partition - 1);
        qs(arrs, partition + 1, high);
    }

    public static int partition(int[] arrs, int low, int high) {
        int[] clone = arrs.clone();  //这里起始没有必要clone_20210315
        //以最后一个数为参考
        int i = low;
        int j = low;
        int temp = arrs[high];
        for (; i <= high; i++) {
            if (clone[i] < temp) {
                arrs[i] = arrs[j];
                arrs[j] = clone[i];
                j++;
            }
        }
        swap(arrs, j, high);
        return j;
    }

    public static void swap(int[] arrs, int i, int j) {
        int tmp = arrs[i] + arrs[j];
        arrs[i] = tmp - arrs[i];
        arrs[j] = tmp - arrs[i];
    }

    public static void main(String[] args) {
        int[] a = {3, 21, 5, 8, 9, 6, 3, 1, 2, 5, 21, 9, 1, 3, 7, 4, 5};
        qs(a, 0, a.length - 1);
        System.out.println();
        for (int b : a) {
            System.out.print(b + " ");
        }
    }
}