野生前端的數據結構練習（10）希爾排序，歸并排序，快速排序

一.希爾排序

shell sort也稱縮小增量排序，是對插入排序算法的改進，其工作原理是定義一個間隔序列來表示排序過程中進行比較的元素之間有多遠的間隔，每次將具有相同間隔的數分為一組，進行插入排序，大部分場景中，間隔是可以提前定義好的，也可以動態生成。在較大的數據集上，希爾排序對于插排的優化效果是非常明顯的。

./**
 * 希爾排序示例代碼
 */
function shellSort(gaps, arr) {
    for(let g = 0; g < gaps.length; g++){
        let h = gaps[g];
        for(let i = gaps[h]; i < arr.length ; i++){
            for(let j = i; j >= h; j = j - h){
                if (arr[j] < arr[j-h]) {
                    swap(arr, j, j-h);
                }
            }
        }
    }
}

function swap(arr, a, b) {
    let temp;
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

如果覺得算法理解起來比較抽象，可以參考下面的動圖感受一下希爾排序的過程:

二.歸并排序

merge sort的基本思想是分治法，假設我們擁有兩個已經排好序的集合，規模為T(n/2)，現在要將這兩個集合合并為一個有序集合，合并的方法如下:

function merge(set1, set2) {
    let result = [];
    let p1 = 0;
    let p2 = 0;
    let index = p1;
    while (p1 < set1.length && p2 < set2.length){
        if (set1[p1] < set2[p2]) {
            result.push(set1[p1++]);
        } else {
            result.push(set2[p2++]);
        }
    }

    if(p1 === set1.length){
        result = result.concat(set2.slice(p2,set2.length))
    } else {
        result = result.concat(set1.slice(p1, set1.length));
    }

    return result;
}

也就是每次比較兩個已排序序列的第一個元素，把較小的拿出來放進結果數組里，當一個序列中的元素全部被取出后，把另一個序列剩下的元素一次性取出加入結果數組，也就是說通過一個線性階的算法(也就是時間復雜度為O(n))將兩個排好序的集合合并了。

分治思想是指將一個問題分解為若干規模更小但本質解法相同的問題，例如上面的例子中，對一個擁有n個元素的集合排序，可以拆分為對兩個n/2規模的集合排序，然后在使用上面的算法將其合并，而每個規模為n/2的問題又可以被拆分為兩個規模為n/4的問題來求解，當拆分至集合中只有一個元素時，將不需要進行集合內排序，僅進行自底向上的合并即可。

歸并排序的主邏輯代碼如下：

function mergeSort(Arr) {
    let left;
    let right;
    let pos;
    let result;
    if (Arr.length === 1) {
        return Arr;
    } else {
        pos = Math.floor(Arr.length / 2);
        left = Arr.slice(0, pos);
        right = Arr.slice(pos, Arr.length);
        result = merge(mergeSort(left), mergeSort(right));
        console.log('merge step:',result);
        return result;
    }
}
//使用數組進行測試
unSortArr = [5,2,4,16,7,23,28,56,12,19];
console.log(mergeSort(unSortArr));

結果如下：

三.快速排序

quick sort是處理大數據集最快的排序算法之一（需要注意的是在處理小數據集時排序性能反而可能下降），它也采用了分治法的思想。merge sort是先按照物理規模減半，在合并時進行排序，quick sort的基本過程是選擇一個元素作為基準值pivot，然后將比它大的和比它小的分別拆分為兩組，也就是說快排算法拆分得到的子序列并不一定是等規模的。快排的過程可以直觀地想象為復現一棵二叉搜索樹。

./**
 * 快速排序示例代碼
 */
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivot = arr[0];
    let left = [];
    let right = [];
    for(let i = 1; i < arr.length; i++){
        if (arr[i] >= pivot) {
            right.push(arr[i]);
        } else {
            left.push(arr[i]);
        }
    }
    return quickSort(left).concat(pivot).concat(quickSort(right));
}

let arr = [72,54,58,30,31,78,2,77,82,72];
console.log(quickSort(arr));