一扼倘、排序算法說明

• 排序的定義：對一序列對象根據(jù)某個關(guān)鍵字進行排序顶考。
  輸入：n個數(shù)：a1,a2,a3,...,an 輸出：n個數(shù)的排列:a1',a2',a3',...,an'钥勋，使得a1'<=a2'<=a3'<=...<=an'
• 對于評述算法優(yōu)劣術(shù)語的說明
• 穩(wěn)定：如果a原本在b前面惊科，而a=b属韧，排序之后a仍然在b的前面；
• 不穩(wěn)定：如果a原本在b的前面盏求，而a=b抖锥，排序之后a可能會出現(xiàn)在b的后面；
• 內(nèi)排序：所有排序操作都在內(nèi)存中完成碎罚；
• 外排序：由于數(shù)據(jù)太大磅废，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進行荆烈；
• 時間復雜度: 一個算法執(zhí)行所耗費的時間拯勉。
• 空間復雜度: 運行完一個程序所需內(nèi)存的大小。
• 總結(jié)

• 對比

  
  
  
  

  In-place: 占用常數(shù)內(nèi)存憔购，不占用額外內(nèi)存 Out-place: 占用額外內(nèi)存宫峦。

• 分類

  
  

二、詳解

1.冒泡排序（Bubble Sort）
冒泡排序是一種簡單的排序算法玫鸟。它重復地走訪過要排序的數(shù)列导绷，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來鞋邑。重復地進行直到?jīng)]有再需要交換诵次，也就是說該數(shù)列已經(jīng)排序完成。

• 算法描述
  <1>.比較相鄰的元素枚碗。如果第一個比第二個大逾一，就交換它們兩個；
  <2>.對每一對相鄰元素作同樣的工作肮雨，從開始第一對到結(jié)尾的最后一對遵堵，這樣在最后的元素應(yīng)該會是最大的數(shù)；
  <3>.針對所有的元素重復以上的步驟怨规，除了最后一個陌宿；
  <4>.重復步驟1~3，直到排序完成波丰。
• 算法實現(xiàn)

function bubbleSort(arr) {
    let length = arr.length;
    for(let i = 0;i < length-1;i++) {
        for(let j = 0;j < length-1-i;j++) {
            if(arr[j] > arr[j + 1]) { // 相鄰元素對比
                let temp = arr[j + 1]; // 交換位置
                arr[j + 1] = arr[j]; 
                arr[j] =temp; 
            }
        }
    }
    return arr;
}
let arr = [2, 1, 19, 30, 27];
console.log(bubbleSort(arr))

• 算法分析
• 最佳情況
  T(n) = O(n)（數(shù)據(jù)正序）
• 最差情況
  T(n) = O(n2)（數(shù)據(jù)反序）
• 平均
  T(n) = O(n2)

2.選擇排序（Selection Sort）
選擇排序(Selection-sort)是一種簡單直觀的排序算法壳坪。它的工作原理：首先在未排序序列中找到最小（大）元素掰烟，存放到排序序列的起始位置爽蝴，然后沐批，再從剩余未排序元素中繼續(xù)尋找最小（大）元素蝎亚，然后放到已排序序列的末尾九孩。以此類推，直到所有元素均排序完畢发框。

• 算法描述
• <1>.初始狀態(tài)：無序區(qū)為R[1..n]躺彬，有序區(qū)為空；
• <2>.第i趟排序(i=1,2,3...n-1)開始時梅惯，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(i..n）宪拥。排序開始時從無序區(qū)的第一個開始，對比后面的个唧，如果遇到比這個小的江解，就記錄下位置设预。該趟排序從當前無序區(qū)中選出最小的記錄R[k]徙歼，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)鳖枕；
• <3>.n-1趟結(jié)束魄梯，數(shù)組有序化了。
• 算法實現(xiàn)

function selectionSort(arr) {
    let len = arr.length;
    let minIndex, temp;
    for(let i = 0;i < len;i++) {
        minIndex = i;
        for(let j = i + 1;j < len; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.timeEnd('選擇排序耗時');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));

• 算法分析
• 最佳情況：T(n) = O(n2)
• 最差情況：T(n) = O(n2)
• 平均情況：T(n) = O(n2)

3.插入排序（Insertion-Sort）
插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法宾符。它的工作原理是通過構(gòu)建有序序列酿秸，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描魏烫，找到相應(yīng)位置并插入辣苏。

• 算法描述

• <1>.從第一個元素開始，該元素可以認為已經(jīng)被排序哄褒；

• <2>.取出下一個元素稀蟋，在已經(jīng)排序的元素序列中從后向前掃描；

• <3>.如果該元素（已排序）大于新元素呐赡，將該元素移到下一位置退客；

• <4>.重復步驟3，直到找到已排序的元素小于或者等于新元素的位置链嘀；

• <5>.將新元素插入到該位置后萌狂；

• <6>.重復步驟2~5。

• 算法實現(xiàn)

function insertionSort (array) {
    if(Object.prototype.toString.call(array).slice(8, -1) == 'Array') {
        console.time('插入排序耗時');
        for (let i = 1;i < array.length; i++) {
            let key = array[i];
            let j = i - 1;
            while(j >= 0 && array[j] > key) {
                array[j + 1] = array[j]; //與前面排好序的對比
                j--;
            }
            array[j + 1] = key; // 插入到最后對比的那個數(shù)后面
        }
        console.timeEnd('插入排序耗時：');
        return array;
    } else {
        return 'array is not an Array!';
    }
}

• 算法分析
• 最佳情況：輸入數(shù)組按升序排列怀泊。T(n) = O(n)
• 最壞情況：輸入數(shù)組按降序排列茫藏。T(n) = O(n2)
• 平均情況：T(n) = O(n2)

4.歸并排序（Merge Sort）
和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響霹琼，但表現(xiàn)比選擇排序好的多务傲，因為始終都是O(n log n）的時間復雜度冤留。代價是需要額外的內(nèi)存空間。
歸并排序是建立在歸并操作上的一種有效的排序算法树灶。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用纤怒。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并天通，得到完全有序的序列泊窘；即先使每個子序列有序，再使子序列段間有序像寒。若將兩個有序表合并成一個有序表烘豹，稱為2-路歸并。

• 算法描述
• <1>.把長度為n的輸入序列分成兩個長度為n/2的子序列诺祸；
• <2>.對這兩個子序列分別采用歸并排序携悯；
• <3>.將兩個排序好的子序列合并成一個最終的排序序列。
• 算法實現(xiàn)

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 (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));

• 算法分析
• 最佳情況：T(n) = O(n)
• 最差情況：T(n) = O(nlogn)
• 平均情況：T(n) = O(nlogn)

5.快速排序（Quick Sort）
快速排序快筷笨，而且效率高憔鬼！它是處理大數(shù)據(jù)最快的排序算法之一。
快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠治赶模渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分的關(guān)鍵字小轴或，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序仰禀。

• 算法描述
• <1>.從數(shù)列中挑出一個元素照雁，稱為 "基準"（pivot）；
• <2>.重新排序數(shù)列答恶，所有元素比基準值小的擺放在基準前面饺蚊，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后悬嗓，該基準就處于數(shù)列的中間位置污呼。這個稱為分區(qū)（partition）操作；
• <3>.遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序烫扼。
• 算法實現(xiàn)

let quickSort = function (arr) {
    console.time('快速排序耗時');
    if(arr.length <= 1) {return arr;}
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1) [0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    console.timeEnd('快速排序耗時');
　　return quickSort(left).concat([pivot], quickSort(right));
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr));

• 算法分析
• 最佳情況：T(n) = O(nlogn)
• 最差情況：T(n) = O(n2)
• 平均情況：T(n) = O(nlogn)

6.計數(shù)排序
計數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法曙求。計數(shù)排序使用一個額外的數(shù)組C，其中第i個元素是待排序數(shù)組A中值等于i的元素的個數(shù)映企。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置悟狱。它只能對整數(shù)進行排序。

• 算法描述
• <1>. 找出待排序的數(shù)組中最大和最小的元素堰氓；
• <2>. 統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)挤渐，存入數(shù)組C的第i項；
• <3>. 對所有的計數(shù)累加（從C中的第一個元素開始双絮，每一項和前一項相加）浴麻；
• <4>. 反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項得问，每放一個元素就將C(i)減去1。
• 算法實現(xiàn)

function countingSort(array) {
    var len = array.length,
        B = [],
        C = [],
        min = max = array[0];
    console.time('計數(shù)排序耗時');
    for (var i = 0; i < len; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
        C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
    }
    for (var j = min; j < max; j++) {
        C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
    }
    for (var k = len - 1; k >= 0; k--) {
        B[C[array[k]] - 1] = array[k];
        C[array[k]]--;
    }
    console.timeEnd('計數(shù)排序耗時');
    return B;
}
var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr)); 

• 算法分析
• 最佳情況：T(n) = O(n+k)
• 最差情況：T(n) = O(n+k)
• 平均情況：T(n) = O(n+k)