摘要：快速排序看名字知特點就是快效率高它是處理大數據最快的排序算法之一奇妙的記憶點內排序不穩定基本思想通過一趟排序把待排序記錄分為獨立的兩部分其中一部分記錄的關鍵字都比另一部分的關鍵字笑則分別對兩部分繼續進行排序以達到整個序列有序自己的理解其實就

看名字知特點,就是快,效率高.它是處理大數據最快的排序算法之一.
奇妙的記憶點:

內排序

不穩定

通過一趟排序把待排序記錄分為獨立的兩部分,其中一部分記錄的關鍵字都比另一部分的關鍵字笑,則分別對兩部分繼續進行排序,以達到整個序列有序.
自己的理解:
其實就是用分治法的思路,將一個數組分為兩半,進行無線分割排序.
首先在數列中取一個值,成為"關鍵字/基準"(pivot);
然后比它小的放前面,大的放后面,相同的話隨便放.
遞歸的把我們分為兩半的數組再次分半排序.

//方法一
function quickSort(array, left, right) {//傳入參數為數組,left,right為排序區域下標
    console.time("1.快速排序耗時");
    if (Object.prototype.toString.call(array).slice(8, -1) === "Array" && typeof left === "number" && typeof right === "number") {//判斷傳入參數的正確性
        if (left < right) { //正確性判斷
            var x = array[right], i = left - 1, temp;//x變量為待排序數組末尾
            for (var j = left; j <= right; j++) {    //從左到右
                if (array[j] <= x) {
                    i++;//注意i先增在交換
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
            quickSort(array, left, i - 1);
            quickSort(array, i + 1, right);
        }
        console.timeEnd("1.快速排序耗時");
        return array;
    } else {
        return "array is not an Array or left or right is not a number!";
    }
}

//方法二
var quickSort2 = function(arr) {
    console.time("2.快速排序耗時");
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
console.timeEnd("2.快速排序耗時");
　　return quickSort2(left).concat([pivot], quickSort2(right));
};

var arr=[3,49,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
console.log(quickSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

記憶點

best condition: T(n) = O(nlog n)

baddest condition: T(n) = O(n^2)

average condition: T(n) = O(nlog n)

不受輸入數據影響,但是表現比選擇排序好.代價是需要額外的內存空間.
奇妙的記憶點:

外排序(需要額外的內存空間)

穩定的排序算法(排序后元素原始順序不會變化)

分治法(Divide and Conquer)

將已有序的子序列合并,從而得到完全有序的序列.也稱為2-路歸并.

function mergeSort(arr) {  //采用自上而下的遞歸方法
    var len = arr.length; //獲取傳入數組的長度
    if(len < 2) {   //如果為單個元素則直接返回
        return arr;
    }
    var middle = Math.floor(len / 2),//取中點
        left = arr.slice(0, middle), //取左邊區間
        right = arr.slice(middle);   //取右邊區間
    return merge(mergeSort(left), mergeSort(right));//調用歸并函數
}

function merge(left, right)//傳入兩個區間
{
    var result = [];//新建變量用于保存結果
    console.time("歸并排序耗時");
    while (left.length && right.length) { //當左區間右區間存在時
        if (left[0] <= right[0]) {  //將區間中較小的一位從區間數組中放到結果數組中.
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    //下面兩個while是為了解決遺留元素問題
    while (left.length) 
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());
    console.timeEnd("歸并排序耗時");
    return result;//返回結果
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
/*10次歸并
歸并排序耗時: 0ms
歸并排序耗時: 0ms
歸并排序耗時: 0ms
歸并排序耗時: 0ms
歸并排序耗時: 0ms
歸并排序耗時: 0ms
歸并排序耗時: 0ms
歸并排序耗時: 0ms
歸并排序耗時: 0ms
歸并排序耗時: 0ms
[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]      */

記憶點

best condition: T(n) = O(n)

baddest condition: T(n) = O(nlog n)

average condition: T(n) = O(nlog n)