一、快速排序（Quick Sort）

1、快速排序是 1960 年發(fā)明的，到現(xiàn)在還沒有明顯優(yōu)于他的算法出現(xiàn)，這說明什么？

• 說明學(xué)習(xí)算法的有效性是很久很久的，五六十年都沒過期，真是一次學(xué)習(xí)，終生受益

image.png

2、快速排序的核心思想是什么（一句話概括）？

• 確定一個軸點元素(pivot)，小于 pivot 的放左邊，大于 pivot 的放右邊，等于 pivot 的元素放哪邊都可以

• 本質(zhì)： 逐漸將每一個元素都轉(zhuǎn)換成軸點元素

image.png

3、快速排序軸點的構(gòu)造過程如下（一定要能理解，重要，有空畫一畫）？

image.png

4、快速排序的代碼實現(xiàn)？(能回憶起大框架邏輯即可)

public class QuickSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        sort(0, array.length);
    }

    private void sort(int begin, int end) {
        if (end - begin < 2) return;
        int pivotIndex = pivotIndex(begin, end);
        sort(begin, pivotIndex);
        sort(pivotIndex + 1, end);
    }

    private int pivotIndex(int begin, int end) {
        T pivotValue = array[begin];
        end--; //讓 end 指向末尾元素

        while (begin < end) {
            while (begin < end) {
                if (cmp(pivotValue, array[end])  < 0 ) { //如果尾部元素大于軸點元素
                    end--;
                } else {  //如果尾部元素小于等于軸點元素，先交換，再掉頭
                    array[begin] = array[end];
                    begin++;
                    break;
                }
            }

            while (begin < end) {
                if (cmp(array[begin], pivotValue) < 0) { //如果頭部元素小于軸點元素
                    begin++;
                } else { //如果頭部元素大于等于軸點元素，先交換再掉頭
                    array[end] = array[begin];
                    end--;
                    break;
                }
            }
        }

        array[begin] = pivotValue;
        return begin;
    }
}

5、快速排序的時間復(fù)雜度如何計算？

image.png

image.png

6、如何避免快速排序的最壞時間復(fù)雜度的出現(xiàn)（從 pivot 選擇方面考慮）？

• 上述我們編寫的快速排序代碼存在一個問題，當(dāng)對 3w 個有序數(shù)組排序時，會發(fā)現(xiàn)棧溢出了，為什么？

棧溢出

• 因為我們上述代碼，對有序數(shù)列進(jìn)行排序，會退化成 O(n^2) 的最壞時間復(fù)雜度，導(dǎo)致開辟過多?？臻g，所以棧溢出了。

• 為了減低最壞情況的出現(xiàn)概率，一般采取的做法是：隨機選擇軸點元素

    //在pivotIndex加上一行隨機選擇 pivot 的代碼即可解決
    private int pivotIndex(int begin, int end) {
        //隨機選擇 pivot
        swap(begin, begin + (int)(Math.random() * (end - begin)));

        T pivotValue = array[begin];
        end--; //讓 end 指向末尾元素
...

image.png

7、為什么我們在快速排序確定 pivot 的時候，如果遇到和 pivot 相等的元素，選擇將它甩到對立面？

• 目的就是減少最壞復(fù)雜度情況出現(xiàn)

如果不將相等元素甩到對立面，對 1 萬個 1 進(jìn)行排序，發(fā)現(xiàn)快速排序的效率退化及其嚴(yán)重

如果將相等元素甩到對立面，對 1 萬個 1 進(jìn)行排序，快速排序的效率依然很高

image.png

二、希爾排序（Shell Sort）

1、希爾排序是什么（基本概念）？

image.png

2、希爾排序的實例（輔助理解希爾排序的核心思想）？希爾排序是對什么排序的優(yōu)化？

• 可以認(rèn)為希爾排序是對插入排序的優(yōu)化

  
  
  image.png

image.png

3、希爾排序的關(guān)鍵因素 - 步長序列？

image.png

image.png

    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }
    
    private List<Integer> sedgewickStepSequence() {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }

4、希爾排序的代碼實現(xiàn)？

image.png

• 可以看到，希爾排序就是內(nèi)部嵌套了個插入排序 （希爾其實在減少逆序?qū)?/code>）

對 3w 個無序數(shù)據(jù)排序，可以看到希爾排序?qū)Ρ炔迦肱判虼蟠蟮玫教嵘?/div>