選擇排序

如果有一組數(shù)，按從大到小排列，遍歷列表，找出最大的數(shù)并添加到一個新列表，再次這樣做，找出第二大的數(shù)，以此類推，這樣便可得到一個有序列表。

示例

// 找出最大元素
function findLargest(arr){
    let largest = arr[0];
    let largestIndex = 0;
    for (let i in arr){
        if (arr[i] > largest) {
            largest = arr[i];
            largestIndex = i;
        }
    } 
    return largestIndex;
}

// 對數(shù)組進(jìn)行排序 
function selectionSort(arr){ 
    let newArr = []
    while(arr.length > 0){
        let largest = findLargest(arr);
        newArr.push(arr.splice(largest, 1)[0])
    }
    return newArr
}
console.log(selectionSort([5, 3, 6, 2, 10]));

選擇排序需要的總時間為 O(n × n)，即O(n2)。

需要檢查的元素數(shù)越來越少

隨著排序的進(jìn)行，每次需要檢查的元素數(shù)在逐漸減少，最后一次需要檢查的元素都只有一 個。既然如此，運(yùn)行時間怎么還是O(n2)呢?這個問題問得好，這與大O表示法中的常數(shù)相關(guān)，后面有機(jī)會我還詳細(xì)解釋一下。

沒錯，并非每次都需要檢查n個元素。第一次需要檢查n個元素，但隨后檢查的元素 數(shù)依次為n - 1, n - 2, ..., 2和1。平均每次檢查的元素數(shù)為1/2 × n，因此運(yùn)行時間為O(n × 1/2 × n)。 但大O表示法省略諸如1/2這樣的常數(shù)，因此簡單地寫 作O(n × n)或O(n2)。

選擇排序是一種靈巧的算法，但其速度不是很快。

快速排序

分而治之

在介紹快速排序之前先介紹一下“分而治之”（divide and conquer，D&C），一種著名的遞歸問題解決方法。
使用D&C解決問題的過程包括兩個步驟：

• 找出基線條件，這種條件必須盡可能簡單。
• 不斷將問題分解(或者說縮小規(guī)模)，直到符合基線條件。

D&C 的工作原理：

• 找出簡單的基線條件。
• 確定如何縮小問題的規(guī)模，使其符合基線條件。

D&C 并非可用于解決問題的算法，而是一種解決問題的思路。

快速排序

快速排序是一種常用的排序算法，比選擇排序快得多。例如，C 語言標(biāo)準(zhǔn)庫中的函數(shù) qsort 實(shí)現(xiàn)的就是快速排序?？焖倥判蛞彩褂昧?D&C。
首先根據(jù) D&C 的步驟，我們需要找到基線條件：數(shù)組為空或只包含一個元素。在這種情況下，只需原樣返回數(shù)組——根本就不用排序。然后縮小問題：分解數(shù)組，直到滿足基線條件。從數(shù)組中選一個元素，作為基準(zhǔn)值（pivot）。
接下來，找出比基準(zhǔn)值小的元素以及比基準(zhǔn)值大的元素，這個過程被稱為分區(qū)（partitioning），會得到：

• 一個由所有小于基準(zhǔn)值的數(shù)字組成的子數(shù)組
• 基準(zhǔn)值
• 一個由所有大于基準(zhǔn)值的數(shù)組組成的子數(shù)組

我們將得到的兩個子數(shù)組再進(jìn)行上述操作，直到都滿足基線條件。這樣我們便得到一個有序列表。

function quicksort(arr) {
    if (arr.length < 2){
        return arr
    } else {
        // 遞歸條件
        let pivot = arr[0];
        let less = [];
        let greater = [];
        for (let i in arr){
            if (arr[i] < pivot){
                less.push(arr[i])
            } else if (arr[i] > pivot){
                greater.push(arr[i])
            } 
        } 
        return [...quicksort(less), pivot, ...quicksort(greater) ]
    }
}
console.log(quicksort([5, 3, 6, 2, 10]));

分解數(shù)組的過程使用了歸納證明的思想，如果是兩個元素的數(shù)組我們可以輕易對其排序，那如果是三個元素呢，我們可以將其拆分為兩個元素的數(shù)組，和一個元素的數(shù)組，以此類推我們可以對任意長度數(shù)組進(jìn)行拆分，那么我們可以任意長度數(shù)組排序。

歸納證明

歸納證明是一種證明算法行之有效的方式，它分兩步:基線 條件和歸納條件。是不是有點(diǎn)似曾相識的感覺?例如，假設(shè)我要證明我能爬到梯子的最上面。 遞歸條件是這樣的:如果我站在一個橫檔上，就能將腳放到下一個橫檔上。換言之，如果我站 在第二個橫檔上，就能爬到第三個橫檔。這就是歸納條件。而基線條件是這樣的，即我已經(jīng)站 在第一個橫檔上。因此，通過每次爬一個橫檔，我就能爬到梯子最頂端。

對于快速排序，可使用類似的推理。在基線條件中，我證明這種算法對空數(shù)組或包含一個 元素的數(shù)組管用。在歸納條件中，我證明如果快速排序?qū)Π粋€元素的數(shù)組管用，對包含兩 個元素的數(shù)組也將管用;如果它對包含兩個元素的數(shù)組管用，對包含三個元素的數(shù)組也將管用， 以此類推。因此，我可以說，快速排序?qū)θ魏伍L度的數(shù)組都管用。這里不再深入討論歸納證明， 但它很有趣，并與D&C協(xié)同發(fā)揮作用。

快速排序的速度取決于選擇的基準(zhǔn)值，在最糟情況下，其運(yùn)行時間為O(n2)。