0.简介

这里只讲一个算法，快速排序，原因在于其排序效率在同为 O(nlogn) 的几种排序方法中效率最高，因此经常被采用。再加上快速排序思想——分治法也确实非常实用，所以在各大厂的面试中被问到最多。

1 基本思想：

快速排序一般基于递归实现。其思路是这样的：
（1）选定一个合适的值，称为“主元”或者“枢纽”(pivot)。
（2）基于这个值，将数组分为两个子集，较小的分在左边，较大的分在右边。
（3）对两个子数组分别重复上述过程，直到每个数组只有一个元素。
（4）排序完成。

快速排序之所以快的原因是在于，主元只需要移动一次就会被放到最终的位置上。
最好情况：当每次选的主元恰好在它应该在的位置时(左边比他小，右边的比他大)，这是快速排序算法的最好情况，算法时间复杂度时O(nlogn)。
最坏情况：每次分区后都出现子序列的长度一个为 1 一个为 n-1，那真是糟糕透顶。这一定会导致我们的表达式变成：
T(n) = O(n) + T(1) + T(n-1) = O(n) + T(n-1)
这和插入排序和选择排序的关系式真是如出一辙，所以我们的最坏情况是 O(n²)。

2 代码实现：

细节实现的好与不好，大大影响快速排序的效率，有几个要注意点：

2.1 如何选主元？

（1）固定基准数
如果数组已经有序，用上面的方式显然非常不好，因为每次划分都只能使待排序序列长度减一。时间复杂度为 O(n²)。因此，使用第一个元素作为基准数是非常糟糕的。

（2）随机基准数
这是一种相对安全的策略。由于基准数的位置是随机的，那么产生的分割也不会总是出现劣质的分割。但是random函数本身就是消耗，所以这个办法也不是很好。

（3）选取三个数的中位数
虽然随机基准数方法选取方式减少了出现不好分割的几率，但是最坏情况下还是 O(n²)。为了缓解这个尴尬的气氛，就引入了「三数取中」这样的基准数选取方式。

// 选取pivot，中位数法
    private static int Median3(int arr[], int left, int right) {
        int center = (left + right) / 2;
        if (arr[left] > arr[center]) {
            swap(arr, left, center);
        }
        if (arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        if (arr[center] > arr[right]) {
            swap(arr, center, right);
        }
        //将中位数与数组的right-1位进行交换，因为right这一位肯定大于center，不用比较
        swap(arr, center, right-1);
        
        return arr[right - 1];
    }

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

这里我们不仅选取了中位数，还将数组进行了一定的修改，将pivot与数组的right-1位进行交换，因为right位置的值经过前面的比较肯定大于pivot，不用再进行比较，我们需要进行排序的是left+1到right-2位置的元素排序，这大大节省了效率。

2.2 如何进行子集划分：

优化子集划分有以下几个办法的：
（1）从两边向中间遍历的双向分区方式：

• 左边从left+1元素开始（注意是++i，所以不是从left开始，是从left+1开始，left在上一步里已经排好），找到大于arr[pivot]的元素然后停住。
• 右边从right-2元素开始，找小于arr[pivot]的元素然后停住。
• 如果i比j小，则交换两个元素的位置。

（2）优化小数组效率：

• 我们知道，如果待排数组的长度不大的话，快速排序的效率是不怎么高的，反而插入排序是不错的选择，所以，我们做了条件判断，待排数组的长度大于某个值的时候用快速排序，长度小于等于某个值的时候采用插入排序。这个值的大小不是确定的，不同的待排数组是不一样的。

2.3 代码：

    private static void quickSortStadard(int[] array, int N) {
        quickSort(arr, 0, N - 1);
    }
    
    private static void quickSort(int arr[], int left, int right) {
        if(right-left>3) {
        
        int pivot = Median3(arr, left, right);
        int i = left;
        int j = right - 1;
        for (;;) {
            // 一直移动指针，直到arr[i]>arr[pivot]
            while (arr[++i] < pivot) {
            }
            // 一直移动指针，直到arr[j]<arr[pivot]
            while (arr[--j] > pivot) {
            }
            if (i < j) {
                swap(arr, i, j);
            } else {
                break;
            }
        }
        // 把藏在right-1位置的主元放到i位置
        swap(arr, i, right - 1);
        // 左半部分递归
        quickSort(arr, left, i - 1);
        // 右半部分递归
        quickSort(arr, i + 1, right);
        }else {
            insertSort(arr, arr.length);
        }
    }

    public static void insertSort(int[] array, int N) {
        int i, j, temp = 0;
        for (i = 1; i < array.length; i++) {// 从数组的第二个元素开始循环
            temp = array[i];// 选中的元素
            for (j = i; j > 0 && array[j - 1] > temp; j--) {// 上一个元素是否大于选中的元素,
                array[j] = array[j - 1]; // 如果选中的元素大于之前的元素，则将之前的元素后移
            }
            array[j] = temp;// 再将选中的元素放在合适的位置
        }
    }