快速排序（Quick Sort） O(nlog2(n))

介绍

快速排序的基本思想：首先在序列中选择一个基准数（常用第一个作为基准），接下来将整个序列以基准数为分割点将序列分成独立的两部分，一边小一边大，接着继续对独立部分进行同样的操作。

算法描述

• 从序列中选择一个数作为基准，"pivot"
• 重新排列序列，将小于基准的数值放在左边，大于基准的数据放在右边，该基准值置于二者分割位置，该操作成为分区操作 "partition"。
• 递归（recusive）将两个独立分区进行同样的操作。

稳定性

不稳定,因为在排序得过程当中进行了数值位置交换，相同的值相对位置有可能发生改变

动图展示

quickSort.gif

代码实现

ps:动态展示代码实现核心方法使用partition。partition1是另一种两边向中间靠进行分区的算法。

public class QuickSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{27, 6, 27, 42, 23, 15, 38, 50, 35, 14, 40, 28};
        int[] res = quickSort(arrays, 0, arrays.length - 1);
        print(res);
    }

    public static int[] quickSort(int[] arr, int minIdx, int maxIdx) {
        print(arr);
        int partition = partition(arr, minIdx, maxIdx);
        if (minIdx < maxIdx) {
            quickSort(arr, minIdx, partition - 1);
            quickSort(arr, partition + 1, maxIdx);
        }
        return arr;
    }

    /**
     * 27   6   27  42  23  15  38  50  35  14  40  28
     * 14   6   23  15  27  42  38  50  35  27  40  28
     * 6    14  23  15  27  42  38  50  35  27  40  28
     * 6    14  23  15  27  42  38  50  35  27  40  28
     * 6    14  15  23  27  42  38  50  35  27  40  28
     * 6    14  15  23  27  42  38  50  35  27  40  28
     * 6    14  15  23  27  42  38  50  35  27  40  28
     * 6    14  15  23  27  28  38  35  27  40  42  50
     * 6    14  15  23  27  27  28  35  38  40  42  50
     * 6    14  15  23  27  27  28  35  38  40  42  50
     * 6    14  15  23  27  27  28  35  38  40  42  50
     * 6    14  15  23  27  27  28  35  38  40  42  50
     * 6    14  15  23  27  27  28  35  38  40  42  50
     * 6    14  15  23  27  27  28  35  38  40  42  50
     * 6    14  15  23  27  27  28  35  38  40  42  50
     * 6    14  15  23  27  27  28  35  38  40  42  50
     */
    public static int partition(int[] arr, int minIdx, int maxIdx) {
        int pivotIdx = minIdx;
        int idx = pivotIdx + 1;
        for (int i = minIdx; i <= maxIdx; i++) {
            if (arr[i] < arr[pivotIdx]) {
                swap(arr, i, idx);
                idx++;
            }
        }
        idx--;
        swap(arr, idx, pivotIdx);
        return idx;
    }

    /**
     * 27   6   27  42  23  15  38  50  35  14  40  28
     * 6    14  27  42  23  15  38  50  35  27  40  28
     * 6    14  27  42  23  15  38  50  35  27  40  28
     * 6    14  27  42  23  15  38  50  35  27  40  28
     * 6    14  27  42  23  15  38  50  35  27  40  28
     * 6    14  15  42  23  27  38  50  35  27  40  28
     * 6    14  15  42  23  27  38  50  35  27  40  28
     * 6    14  15  23  27  27  38  50  35  28  40  42
     * 6    14  15  23  27  27  38  50  35  28  40  42
     * 6    14  15  23  27  27  38  50  35  28  40  42
     * 6    14  15  23  27  27  38  50  35  28  40  42
     * 6    14  15  23  27  27  38  50  35  28  40  42
     * 6    14  15  23  27  27  38  50  35  28  40  42
     * 6    14  15  23  27  27  28  50  35  38  40  42
     * 6    14  15  23  27  27  28  50  35  38  40  42
     * 6    14  15  23  27  27  28  35  38  40  42  50
     */
    public static int partition1(int[] arr, int minIdx, int maxIdx) {
        int pivotIdx = minIdx;
        while (minIdx < maxIdx) {
            while (arr[minIdx] < arr[pivotIdx] && minIdx < maxIdx) {
                minIdx++;
            }
            while (arr[maxIdx] >= arr[pivotIdx] && maxIdx > minIdx) {
                maxIdx--;
            }
            if (minIdx < maxIdx) {
                swap(arr, minIdx, maxIdx);
            }
        }
        swap(arr, minIdx, pivotIdx);
        return minIdx;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}