老狗啃骨头之算法-快速排序

快速排序（Quick Sort）

  快速排序，又称分区交换排序，简称快排。它也是一种交换排序，它是一种在处理大量数据方面有优势的算法。当数据量巨大的时候，冒泡排序这种中规中矩，挨次遍历逐个对比的玩法，估计会让人抓毛的，于是据说在公元1960年，一位叫东尼·霍尔（C. A. R. Hoare）的大神，沐浴斋戒，焚香祷告…..苦思冥想，终得所创。

  快速排序是利用分治策略，分而排之，通过一次排序操作将样本数据分割成独立的两部分，并使其中一部分所有数据值都小于另一部分；然后被分割的两部分进行递归做同样的操作，依次再分，直至排序完成。
  排序算法这种涉及二分的算法，其过程一般递归进行，这在数据结构的层面上，会利用到堆栈，相对于一般线性结构算法，在特定的情况下表现出质的计算效率的提升，这也是我们学习数据结构和算法的精髓之处。

1：选一基准元素（习惯上选首尾元素，其实随机亦可）；
2：遍历对比，将小于基准元素的都放置在之前，将大于基准元素的都放置在之后（相等的可随意安置）；此时基准元素将处在其数据样本排好顺序的正确位置；
3：然后对基准元素两侧的数据，分别依次执行1～3操作，直至排序完成。

import java.util.Arrays;

/** 
* @author    :Veiking
* @version    :2020年10月15日
* 说明        :快速排序算法
*/
public class QuickSort {
    // 排序方法入口
    public static int[] sort(int[] arrays) {
        int begin = 0;
        int end = arrays.length-1;
        doSort(arrays, begin, end);
        return arrays;
    }
    /**
     * 快速排序方法主体，其核心是寻得一基准元素，小的放在前，大的放在后，将数组二分且分别依此排序
     * @param arrays
     * @param begin
     * @param end
     * @return
     */
    public static int[] doSort(int[] arrays, int begin, int end) {
        // 不得越界，也是数组排序处理完毕的标识
        if(begin=base) {
                end--;
            }
            // 将这个小于基准元素的值放置数组前方刚才那个放到数组尾部元素原先的位置
            arrays[begin] = arrays[end];
        }
        // 直至遍历完毕，这个begin也已经和end重合了，把选定的基准元素放到这个位置，整个数组排序完毕后，这个元素正确的位置
        arrays[begin] = base;
        return begin;
    }

    // 执行
    public static void main(String[] args) {
        int[] input = new int[]{3, 6, 9, 5, 13, 15, 4, 11, 1, 12, 16, 2, 14, 10, 7, 8};
        System.out.println("样本初始样本数据："+Arrays.toString(input));
        int[] output = QuickSort.sort(input);
        System.out.println("快速排序结果数据："+Arrays.toString(output));
    }
}
)>

  快速排序算法的基本性能，归纳如下图：

1、 时间复杂度

  快速排序之所以相对冒泡排序比较快，是因为快排两头跳跃式的遍历交换，实际上避免和减少了像冒泡那种老实巴交在相邻元素间一次又一次的逐次操作，从而在数据量大的时候，能凸显优势。
  当然喝凉水也有塞牙缝的时候，遇到极端特例，每次去的基准元素，都是最小（或最大）的，这时候快速排序也会变成处理相邻数据逐个对比交换的情况，差不多跟冒泡基本一样了，最差时间复杂度跟冒泡排序一样悲催，所以最差时间复杂度是O(n2)；
  当快排的每一次的操作，都能将数据样本平分的时候，递归数组的平均长度和处理深度，都接近最优，我们说快排的最优时间复杂度为O(nlog2n)；
  但快排的特点是用于数据量大的时候，我们知道，一般数据样本多且复杂的时候，整体就越接近随机，越是随机，每次操作都越接近于平分，故我们把快排的最优时间复杂度，当作它的平均时间复杂度，即平均时间复杂度，也为O(nlog2n)。
  不难得出结论，一般来说：数据量越大，快排的优势越明显；数据样本越随机无序，快排表现的性能越好。

2、 空间复杂度

  快速排序，在实现的过程中运用了二分策略，每一次都需要开辟空间用于存储基准元素，取其平均，可以认为快速排序的空间复杂度为O(nlog2n)。

3、稳定性

  在快速排序中，由于是分区跳跃式的交换，等值元素有可能会因为分区导致相对顺序不定，所以快速排序是不稳定的算法。