<h2>冒泡排序</h2>

原理：兩兩比較，不符合要求就調(diào)換位置。
代碼：

function bubble() {
    var change;
    var sort = [3, 6, 4, 9, 13, 2, 1];
    for (var i = 0; i < sort.length - 1; i++) { 
        for (var j = i; j < sort.length; j++) {
            if (sort[i] > sort[j]) {
                change = sort[i];
                sort[i] = sort[j]
                sort[j] = change;
            }    
        }
        console.log(sort)
    }
}
bubble()

效果截圖：

bubble.png

<h2>選擇排序</h2>

原理：在未排序序列中找到最小元素，存放到排序序列的起始位置。
代碼：

function selection() {
    var change;
    var sort = [3, 6, 4, 9, 13, 2, 1];
    for (var i = 0; i < sort.length; i++) {
        var min = i;
        for (var j = i + 1; j < sort.length + 1; j++) {
            if (sort[min] > sort[j]) {
                change = sort[min];
                sort[min] = sort[j]
                sort[j] = change;
            }
        }
        console.log(sort)
    }
}
selection()

效果截屏：

selection.png

<h2>插入排序</h2>
原理：對于每個未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
代碼：

function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
function insertion() {
    var sort=[3, 6, 4, 9, 13, 2, 1]
    var length = sort.length;
    for (var i = 1; i < length; i++) {
        for (var j = i; j > 0; j--) {
            if (sort[j - 1] > sort[j]) {
                swap(sort, j - 1, j);
            } else {
                break;
            }
        }
        console.log(sort)
    }
}

insertion();

效果截屏：

insertion.png

<h2>希爾排序</h2>
原理：將數(shù)組列在一個表中并對列分別進(jìn)行插入排序，重復(fù)這過程，不過每次用更長的列（步長更長了，列數(shù)更少了）來進(jìn)行。最后整個表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身還是使用數(shù)組進(jìn)行排序。
代碼：

function shell() {
    var sort = [9,8,7,6,5,4,3,2,1,0];
    var len = sort.length;
    gap = Math.floor(len / 2);
    while (gap !== 0) {
        for (var i = gap; i < len; i++) {
            var temp = sort[i];
            var j;
            for (j = i - gap; j >= 0 && temp < sort[j]; j -= gap) {
                sort[j + gap] = sort[j];
                console.log(sort+'A')
            }
            sort[j + gap] = temp;
            // console.log(sort+"B")

        }
        gap = Math.floor(gap / 2);
        console.log(sort+'C');
    }
}
shell();

效果截屏：

shell.png

<h2>歸并排序</h2>
原理：先考慮合并兩個有序數(shù)組，基本思路是比較兩個數(shù)組的最前面的數(shù)，誰小就先取誰，取了后相應(yīng)的指針就往后移一位。然后再比較，直至一個數(shù)組為空，最后把另一個數(shù)組的剩余部分復(fù)制過來即可。

代碼：

function merge(left, right) {
    var result = [];
    while (left.length && right.length) {
        if (left[0] < right[0])
            result.push(left.shift());
        else
            result.push(right.shift());
    }
    console.log(result.concat(left, right))
    return result.concat(left, right);
}

function mergeSort(a) {
    if (a.length === 1)
        return a;

    var work = [];

    for (var i = 0, len = a.length; i < len; i++)
        work.push([a[i]]);

    work.push([]); // 如果數(shù)組長度為奇數(shù)

    for (var lim = len; lim > 1; lim = (lim + 1) / 2) {
        for (var j = 0, k = 0; k < lim; j++, k += 2)
            work[j] = merge(work[k], work[k + 1]);

        work[j] = []; // 如果數(shù)組長度為奇數(shù)
    }
    return work[0];
}

console.log(mergeSort([9,8,7,6,5,4,3,2,1,0]));

效果截屏：

merge.png

<h2>快速排序</h2>
原理：從數(shù)列中挑出一個元素作為基準(zhǔn)數(shù)，將比基準(zhǔn)數(shù)大的放到右邊，小于或等于它的數(shù)都放到左邊，遞歸執(zhí)行，直至各區(qū)間只有一個數(shù)。
代碼：

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;//如果數(shù)組只有一個數(shù)，就直接返回；
    }

    var num = Math.floor(arr.length / 2);//找到中間數(shù)的索引值，如果是浮點(diǎn)數(shù)，則向下取整
    var numValue = arr.splice(num, 1);//找到中間數(shù)的值
    var left = [];
    var right = [];

    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < numValue) {
            left.push(arr[i]);//基準(zhǔn)點(diǎn)的左邊的數(shù)傳到左邊數(shù)組
        }
        else {
            right.push(arr[i]);//基準(zhǔn)點(diǎn)的右邊的數(shù)傳到右邊數(shù)組
        }
        console.log(arr)
    }
    return quickSort(left).concat(numValue, quickSort(right));//遞歸不斷重復(fù)比較
}
console.log(quickSort([9,8,7,6,5,4,3,2,1,0]));

效果截屏;

quick.png

<h2>堆排序</h2>
思想：由于堆是用數(shù)組模擬的。得到一個大根堆后，數(shù)組內(nèi)部并不是有序的。因此需要將堆化數(shù)組有序化。思想是移除根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算。第一次將heap[0]與heap[n-1]交換，再對heap[0...n-2]做最大堆調(diào)整。第二次將heap[0]與heap[n-2]交換，再對heap[0...n-3]做最大堆調(diào)整。重復(fù)該操作直至heap[0]和heap[1]交換。由于每次都是將最大的數(shù)并入到后面的有序區(qū)間，故操作完后整個數(shù)組就是有序的了。
代碼：

function heapSort(array) {
    function swap(array, i, j) {
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    function maxHeapify(array, index, heapSize) {
        var iMax,
            iLeft,
            iRight;
        while (true) {
            iMax = index;
            iLeft = 2 * index + 1;
            iRight = 2 * (index + 1);
            if (iLeft < heapSize && array[index] < array[iLeft]) {
                iMax = iLeft;
            }
            if (iRight < heapSize && array[iMax] < array[iRight]) {
                iMax = iRight;
            }
            if (iMax != index) {
                swap(array, iMax, index);
                index = iMax;
            } else {
                break;
            }
        }
        console.log(array)
    }

    function buildMaxHeap(array) {
        var i,
            iParent = Math.floor(array.length / 2) - 1;
        for (i = iParent; i >= 0; i--) {
            maxHeapify(array, i, array.length);
        }
    }

    function sort(array) {
        buildMaxHeap(array);
        for (var i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            maxHeapify(array, 0, i);
        }
        return array;
    }

    return sort(array);
}
console.log(heapSort([9, 8, 7, 6, 5, 4, 3, 2, 1, 0]))

效果截屏：

heap.png

<h2>總結(jié)</h2>

sort.jpg