国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JS中可能用得到的全部的排序算法

verano / 1209人閱讀

本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法,文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現,如果喜歡請點贊支持~謝謝.

原文: http://louiszhai.github.io/20...

導讀

排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道冒泡啊?!), 要知道學習一門技術最好的時間是三年前, 但愿我現在補習還來得及(捂臉).

因此本篇重拾了出鏡概率比較高的十來種排序算法, 逐一分析其排序思想, 并批注注意事項. 歡迎對算法提出改進和討論.

冒泡排序

冒泡排序需要兩個嵌套的循環. 其中, 外層循環移動游標; 內層循環遍歷游標及之后(或之前)的元素, 通過兩兩交換的方式, 每次只確保該內循環結束位置排序正確, 然后內層循環周期結束, 交由外層循環往后(或前)移動游標, 隨即開始下一輪內層循環, 以此類推, 直至循環結束.

Tips: 由于冒泡排序只在相鄰元素大小不符合要求時才調換他們的位置, 它并不改變相同元素之間的相對順序, 因此它是穩定的排序算法.

由于有兩層循環, 因此可以有四種實現方式.

方案 外層循環 內層循環
1 正序 正序
2 正序 逆序
3 逆序 正序
4 逆序 逆序

四種不同循環方向, 實現方式略有差異.

如下是動圖效果(對應于方案1: 內/外層循環均是正序遍歷.

如下是上圖的算法實現(對應方案一: 內/外層循環均是正序遍歷).

//先將交換元素部分抽象出來
function swap(i,j,array){
  var temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}
function bubbleSort(array) {
  var length = array.length, isSwap;
  for (var i = 0; i < length; i++) {            //正序
    isSwap = false;
    for (var j = 0; j < length - 1 - i; j++) {     //正序
      array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
    }
    if(!isSwap)
      break;
  }
  return array;
}

以上, 排序的特點就是: 靠后的元素位置先確定.

方案二: 外循環正序遍歷, 內循環逆序遍歷, 代碼如下:

function bubbleSort(array) {
  var length = array.length, isSwap;
  for (var i = 0; i < length; i++) {            //正序
    isSwap = false;
    for (var j = length - 1; j >= i+1; j--) {     //逆序
      array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array);
    }
    if(!isSwap)
      break;
  }
  return array;
}

以上, 靠前的元素位置先確定.

方案三: 外循環逆序遍歷, 內循環正序遍歷, 代碼如下:

function bubbleSort(array) {
  var length = array.length, isSwap;
  for (var i = length - 1; i >= 0; i--) {     //逆序
    isSwap = false;
    for (var j = 0; j < i; j++) {            //正序
      array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
    }
    if(!isSwap)
      break;
  }
  return array;
}

以上, 由于內循環是正序遍歷, 因此靠后的元素位置先確定.

方案四: 外循環逆序遍歷, 內循環逆序遍歷, 代碼如下:

function bubbleSort(array) {
  var length = array.length, isSwap;
  for (var i = length - 1; i >= 0; i--) {                //逆序
    isSwap = false;
    for (var j = length - 1; j >= length - 1 - i; j--) { //逆序
      array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array);
    }
    if(!isSwap)
      break;
  }
  return array;
}

以上, 由于內循環是逆序遍歷, 因此靠前的元素位置先確定.

以下是其算法復雜度:

平均時間復雜度 最好情況 最壞情況 空間復雜度
O(n2) O(n) O(n2) O(1)

冒泡排序是最容易實現的排序, 最壞的情況是每次都需要交換, 共需遍歷并交換將近n2/2次, 時間復雜度為O(n2). 最佳的情況是內循環遍歷一次后發現排序是對的, 因此退出循環, 時間復雜度為O(n). 平均來講, 時間復雜度為O(n2). 由于冒泡排序中只有緩存的temp變量需要內存空間, 因此空間復雜度為常量O(1).

雙向冒泡排序

雙向冒泡排序是冒泡排序的一個簡易升級版, 又稱雞尾酒排序. 冒泡排序是從低到高(或者從高到低)單向排序, 雙向冒泡排序顧名思義就是從兩個方向分別排序(通常, 先從低到高, 然后從高到低). 因此它比冒泡排序性能稍好一些.

如下是算法實現:

function bothwayBubbleSort(array){
  var tail = array.length-1, i, isSwap = false;
  for(i = 0; i < tail; tail--){
    for(var j = tail; j > i; j--){    //第一輪, 先將最小的數據冒泡到前面
      array[j-1] > array[j] && (isSwap = true) && swap(j,j-1,array);
    }
    i++;
    for(j = i; j < tail; j++){        //第二輪, 將最大的數據冒泡到后面
      array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
    }
  }
  return array;
}
選擇排序

從算法邏輯上看, 選擇排序是一種簡單且直觀的排序算法. 它也是兩層循環. 內層循環就像工人一樣, 它是真正做事情的, 內層循環每執行一遍, 將選出本次待排序的元素中最小(或最大)的一個, 存放在數組的起始位置. 而 外層循環則像老板一樣, 它告訴內層循環你需要不停的工作, 直到工作完成(也就是全部的元素排序完成).

Tips: 選擇排序每次交換的元素都有可能不是相鄰的, 因此它有可能打破原來值為相同的元素之間的順序. 比如數組[2,2,1,3], 正向排序時, 第一個數字2將與數字1交換, 那么兩個數字2之間的順序將和原來的順序不一致, 雖然它們的值相同, 但它們相對的順序卻發生了變化. 我們將這種現象稱作 不穩定性 .

如下是動圖效果:

如下是上圖的算法實現:

function selectSort(array) {
  var length = array.length, min;
  for (var i = 0; i < length - 1; i++) {
    min = i;
    for (var j = i + 1; j < length; j++) {
      array[j] < array[min] && (min = j); //記住最小數的下標
    }
    min!=i && swap(i,min,array);
  }
  return array;
}

以下是其算法復雜度:

平均時間復雜度 最好情況 最壞情況 空間復雜度
O(n2) O(n2) O(n2) O(1)

選擇排序的簡單和直觀名副其實, 這也造就了它"出了名的慢性子", 無論是哪種情況, 哪怕原數組已排序完成, 它也將花費將近n2/2次遍歷來確認一遍. 即便是這樣, 它的排序結果也還是不穩定的. 唯一值得高興的是, 它并不耗費額外的內存空間.

插入排序

插入排序的設計初衷是往有序的數組中快速插入一個新的元素. 它的算法思想是: 把要排序的數組分為了兩個部分, 一部分是數組的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先將第一部分排序完成, 然后再插入這個元素. 其中第一部分的排序也是通過再次拆分為兩部分來進行的.

插入排序由于操作不盡相同, 可分為 直接插入排序 , 折半插入排序(又稱二分插入排序), 鏈表插入排序 , 希爾排序 .

直接插入排序

它的基本思想是: 將待排序的元素按照大小順序, 依次插入到一個已經排好序的數組之中, 直到所有的元素都插入進去.

如下是動圖效果:

如下是上圖的算法實現:

function directInsertionSort(array) {
  var length = array.length, index, current;
  for (var i = 1; i < length; i++) {
    index = i - 1;         //待比較元素的下標
    current = array[i];     //當前元素
    while(index >= 0 && array[index] > current) { //前置條件之一:待比較元素比當前元素大
      array[index+1] = array[index];    //將待比較元素后移一位
      index--;                           //游標前移一位
      //console.log(array);
    }
    if(index+1 != i){                   //避免同一個元素賦值給自身
      array[index+1] = current;            //將當前元素插入預留空位
      //console.log(array);
    }        
  }
  return array;
}

為了更好的觀察到直接插入排序的實現過程, 我們不妨將上述代碼中的注釋部分加入. 以數組 [5,4,3,2,1] 為例, 如下便是原數組的演化過程.

可見, 數組的各個元素, 從后往前, 只要比前面的元素小, 都依次插入到了合理的位置.

Tips: 由于直接插入排序每次只移動一個元素的位置, 并不會改變值相同的元素之間的排序, 因此它是一種穩定排序.

折半插入排序

折半插入排序是直接插入排序的升級版. 鑒于插入排序第一部分為已排好序的數組, 我們不必按順序依次尋找插入點, 只需比較它們的中間值與待插入元素的大小即可.

Tips: 同直接插入排序類似, 折半插入排序每次交換的是相鄰的且值為不同的元素, 它并不會改變值相同的元素之間的順序. 因此它是穩定的.

算法基本思想是:

取0 ~ i-1的中間點( m = (i-1)>>1 ), array[i] 與 array[m] 進行比較, 若array[i] < array[m] , 則說明待插入的元素array[i] 應該處于數組的 0 ~ m 索引之間; 反之, 則說明它應該處于數組的 m ~ i-1 索引之間.

重復步驟1, 每次縮小一半的查找范圍, 直至找到插入的位置.

將數組中插入位置之后的元素全部后移一位.

在指定位置插入第 i 個元素.

注: x>>1 是位運算中的右移運算, 表示右移一位, 等同于x除以2再取整, 即 x>>1 == Math.floor(x/2) .

如下是算法實現:

function binaryInsertionSort(array){
  var current, i, j, low, high, m;
  for(i = 1; i < array.length; i++){
    low = 0;
    high = i - 1;
    current = array[i];

    while(low <= high){            //步驟1&2:折半查找
      m = (low + high)>>1;
      if(array[i] >= array[m]){//值相同時, 切換到高半區,保證穩定性
        low = m + 1;        //插入點在高半區
      }else{
        high = m - 1;        //插入點在低半區
      }
    }
    for(j = i; j > low; j--){     //步驟3:插入位置之后的元素全部后移一位
      array[j] = array[j-1];
    }
    array[low] = current;         //步驟4:插入該元素
  }
  return array;
}

為了便于對比, 同樣以數組 [5,4,3,2,1] 舉例?. 原數組的演化過程如下(與上述一樣):

雖然折半插入排序明顯減少了查詢的次數, 但是數組元素移動的次數卻沒有改變. 它們的時間復雜度都是O(n2).

希爾排序

希爾排序也稱縮小增量排序, 它是直接插入排序的另外一個升級版, 實質就是分組插入排序. 希爾排序以其設計者希爾(Donald Shell)的名字命名, 并于1959年公布.

算法的基本思想:

將數組拆分為若干個子分組, 每個分組由相距一定"增量"的元素組成. 比方說將[0,1,2,3,4,5,6,7,8,9,10]的數組拆分為"增量"為5的分組, 那么子分組分別為 [0,5], [1,6], [2,7], [3,8], [4,9] 和 [5,10].

然后對每個子分組應用直接插入排序.

逐步減小"增量", 重復步驟1,2.

直至"增量"為1, 這是最后一個排序, 此時的排序, 也就是對全數組進行直接插入排序.

如下是排序的示意圖:

可見, 希爾排序實際上就是不斷的進行直接插入排序, 分組是為了先將局部元素有序化. 因為直接插入排序在元素基本有序的狀態下, 效率非常高. 而希爾排序呢, 通過先分組后排序的方式, 制造了直接插入排序高效運行的場景. 因此希爾排序效率更高.

我們試著抽象出共同點, 便不難發現上述希爾排序的第四步就是一次直接插入排序, 而希爾排序原本就是從"增量"為n開始, 直至"增量"為1, 循環應用直接插入排序的一種封裝. 因此直接插入排序就可以看做是步長為1的希爾排序. 為此我們先來封裝下直接插入排序.

//形參增加步數gap(實際上就相當于gap替換了原來的數字1)
function directInsertionSort(array, gap) {
  gap = (gap == undefined) ? 1 : gap;       //默認從下標為1的元素開始遍歷
  var length = array.length, index, current;
  for (var i = gap; i < length; i++) {
    index = i - gap;    //待比較元素的下標
    current = array[i];    //當前元素
    while(index >= 0 && array[index] > current) { //前置條件之一:待比較元素比當前元素大
      array[index + gap] = array[index];    //將待比較元素后移gap位
      index -= gap;                           //游標前移gap位
    }
    if(index + gap != i){                   //避免同一個元素賦值給自身
      array[index + gap] = current;            //將當前元素插入預留空位
    }
  }
  return array;
}

那么希爾排序的算法實現如下:

function shellSort(array){
  var length = array.length, gap = length>>1, current, i, j;
  while(gap > 0){
    directInsertionSort(array, gap); //按指定步長進行直接插入排序
    gap = gap>>1;
  }
  return array;
}

同樣以數組[5,4,3,2,1] 舉例?. 原數組的演化過程如下:

對比上述直接插入排序和折半插入排序, 數組元素的移動次數由14次減少為7次. 通過拆分原數組為粒度更小的子數組, 希爾排序進一步提高了排序的效率.

不僅如此, 以上步長設置為了 {N/2, (N/2)/2, ..., 1}. 該序列即希爾增量, 其它的增量序列 還有Hibbard:{1, 3, ..., 2^k-1}. 通過合理調節步長, 還能進一步提升排序效率. 實際上已知的最好步長序列是由Sedgewick提出的(1, 5, 19, 41, 109,…). 該序列中的項或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1. 具體請戳 希爾排序-維基百科 .

Tips: 我們知道, 單次直接插入排序是穩定的, 它不會改變相同元素之間的相對順序, 但在多次不同的插入排序過程中, 相同的元素可能在各自的插入排序中移動, 可能導致相同元素相對順序發生變化. 因此, 希爾排序并不穩定.

歸并排序

歸并排序建立在歸并操作之上, 它采取分而治之的思想, 將數組拆分為兩個子數組, 分別排序, 最后才將兩個子數組合并; 拆分的兩個子數組, 再繼續遞歸拆分為更小的子數組, 進而分別排序, 直到數組長度為1, 直接返回該數組為止.

Tips: 歸并排序嚴格按照從左往右(或從右往左)的順序去合并子數組, 它并不會改變相同元素之間的相對順序, 因此它也是一種穩定的排序算法.

如下是動圖效果:

歸并排序可通過兩種方式實現:

自上而下的遞歸

自下而上的迭代

如下是算法實現(方式1:遞歸):

function mergeSort(array) {  //采用自上而下的遞歸方法
  var length = array.length;
  if(length < 2) {
    return array;
  }
  var m = (length >> 1),
      left = array.slice(0, m),
      right = array.slice(m); //拆分為兩個子數組
  return merge(mergeSort(left), mergeSort(right));//子數組繼續遞歸拆分,然后再合并
}
function merge(left, right){ //合并兩個子數組
  var result = [];
  while (left.length && right.length) {
    var item = left[0] <= right[0] ? left.shift() : right.shift();//注意:判斷的條件是小于或等于,如果只是小于,那么排序將不穩定.
    result.push(item);
  }
  return result.concat(left.length ? left : right);
}

由上, 長度為n的數組, 最終會調用mergeSort函數2n-1次. 通過自上而下的遞歸實現的歸并排序, 將存在堆棧溢出的風險. 親測各瀏覽器的堆棧溢出所需的遞歸調用次數大致為:

Chrome v55: 15670

Firefox v50: 44488

Safari v9.1.2: 50755

以下是測試代碼:

function computeMaxCallStackSize() {
  try {
    return 1 + computeMaxCallStackSize();
  } catch (e) {
    // Call stack overflow
    return 1;
  }
}
var time = computeMaxCallStackSize();
console.log(time);

為此, ES6規范中提出了尾調優化的思想: 如果一個函數的最后一步也是一個函數調用, 那么該函數所需要的棧空間將被釋放, 它將直接進入到下次調用中, 最終調用棧里只保留最后一次的調用記錄.

雖然ES6規范如此誘人, 然而目前并沒有瀏覽器支持尾調優化, 相信在不久的將來, 尾調優化就會得到主流瀏覽器的支持.

以下是其算法復雜度:

平均時間復雜度 最好情況 最壞情況 空間復雜度
O(nlog?n) O(nlog?n) O(nlog?n) O(n)

從效率上看, 歸并排序可算是排序算法中的"佼佼者". 假設數組長度為n, 那么拆分數組共需logn步, 又每步都是一個普通的合并子數組的過程, 時間復雜度為O(n), 故其綜合時間復雜度為O(nlogn). 另一方面, 歸并排序多次遞歸過程中拆分的子數組需要保存在內存空間, 其空間復雜度為O(n).

快速排序

快速排序借用了分治的思想, 并且基于冒泡排序做了改進. 它由C. A. R. Hoare在1962年提出. 它將數組拆分為兩個子數組, 其中一個子數組的所有元素都比另一個子數組的元素小, 然后對這兩個子數組再重復進行上述操作, 直到數組不可拆分, 排序完成.

如下是動圖效果:

如下是算法實現:

function quickSort(array, left, right) {
  var partitionIndex,
      left = typeof left == "number" ? left : 0,
      right = typeof right == "number" ? right : array.length-1;
  if (left < right) {
    partitionIndex = partition(array, left, right);//切分的基準值
    quickSort(array, left, partitionIndex-1);
    quickSort(array, partitionIndex+1, right);
  }
  return array;
}
function partition(array, left ,right) {   //分區操作
  for (var i = left+1, j = left; i <= right; i++) {//j是較小值存儲位置的游標
    array[i] < array[left] && swap(i, ++j, array);//以第一個元素為基準
  }
  swap(left, j, array);            //將第一個元素移至中間
  return j;
}

以下是其算法復雜度:

平均時間復雜度 最好情況 最壞情況 空間復雜度
O(nlog?n) O(nlog?n) O(n2) O(nlog?n)

快速排序排序效率非常高. 雖然它運行最糟糕時將達到O(n2)的時間復雜度, 但通常, 平均來看, 它的時間復雜為O(nlogn), 比同樣為O(nlogn)時間復雜度的歸并排序還要快. 快速排序似乎更偏愛亂序的數列, 越是亂序的數列, 它相比其他排序而言, 相對效率更高. 之前在 捋一捋JS的數組 一文中就提到: Chrome的v8引擎為了高效排序, 在排序數據超過了10條時, 便會采用快速排序. 對于10條及以下的數據采用的便是插入排序.

Tips: 同選擇排序相似, 快速排序每次交換的元素都有可能不是相鄰的, 因此它有可能打破原來值為相同的元素之間的順序. 因此, 快速排序并不穩定.

堆排序

1991年的計算機先驅獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德(Robert W.Floyd) 和威廉姆斯(J.Williams) 在1964年共同發明了著名的堆排序算法(Heap Sort).

堆排序是利用堆這種數據結構所設計的一種排序算法. 它是選擇排序的一種. 堆分為大根堆和小根堆. 大根堆要求每個子節點的值都不大于其父節點的值, 即array[childIndex] <= array[parentIndex], 最大的值一定在堆頂. 小根堆與之相反, 即每個子節點的值都不小于其父節點的值, 最小的值一定在堆頂. 因此我們可使用大根堆進行升序排序, 使用小根堆進行降序排序.

并非所有的序列都是堆, 對于序列k1, k2,…kn, 需要滿足如下條件才行:

ki <= k(2i) 且 ki<=k(2i+1)(1≤i≤ n/2), 即為小根堆, 將<=換成>=, 那么則是大根堆. 我們可以將這里的堆看作完全二叉樹, k(i) 相當于是二叉樹的非葉子節點, k(2i) 則是左子節點, k(2i+1)是右子節點.

算法的基本思想(以大根堆為例):

先將初始序列K[1..n]建成一個大根堆, 此堆為初始的無序區.

再將關鍵字最大的記錄K[1] (即堆頂)和無序區的最后一個記錄K[n]交換, 由此得到新的無序區K[1..n-1]和有序區K[n], 且滿足K[1..n-1].keys≤K[n].key

交換K[1] 和 K[n] 后, 堆頂可能違反堆性質, 因此需將K[1..n-1]調整為堆. 然后重復步驟2, 直到無序區只有一個元素時停止.

如下是動圖效果:

如下是算法實現:

function heapAdjust(array, i, length) {//堆調整
  var left = 2 * i + 1,
      right = 2 * i + 2,
      largest = i;
  if (left < length && array[largest] < array[left]) {
    largest = left;
  }
  if (right < length && array[largest] < array[right]) {
    largest = right;
  }
  if (largest != i) {
    swap(i, largest, array);
    heapAdjust(array, largest, length);
  }
}
function heapSort(array) {
  //建立大頂堆
  length = array.length;
  for (var i = length>>1; i >= 0; i--) {
    heapAdjust(array, i, length);
  }
  //調換第一個與最后一個元素,重新調整為大頂堆
  for (var i = length - 1; i > 0; i--) {
    swap(0, i, array);
    heapAdjust(array, 0, --length);
  }
  return array;
}

以上, ①建立堆的過程, 從length/2 一直處理到0, 時間復雜度為O(n);

②調整堆的過程是沿著堆的父子節點進行調整, 執行次數為堆的深度, 時間復雜度為O(lgn);

③堆排序的過程由n次第②步完成, 時間復雜度為O(nlgn).

Tips: 由于堆排序中初始化堆的過程比較次數較多, 因此它不太適用于小序列. 同時由于多次任意下標相互交換位置, 相同元素之間原本相對的順序被破壞了, 因此, 它是不穩定的排序.

計數排序

計數排序幾乎是唯一一個不基于比較的排序算法, 該算法于1954年由 Harold H. Seward 提出. 使用它處理一定范圍內的整數排序時, 時間復雜度為O(n+k), 其中k是整數的范圍, 它幾乎比任何基于比較的排序算法都要快( 只有當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序, 如歸并排序和堆排序).

使用計數排序需要滿足如下條件:

待排序的序列全部為整數

排序需要額外的存儲空間

算法的基本思想:

計數排序利用了一個特性, 對于數組的某個元素, 一旦知道了有多少個其它元素比它小(假設為m個), 那么就可以確定出該元素的正確位置(第m+1位)

初始化游標i為0, 并準備一個緩存數組B, 長度為待排序數組A的最大值+1, 循環一遍待排序數組A, 在緩存數組B中存儲A的各個元素出現的次數.

①將B中的當前元素item與0比較, 若大于0, 則往待排序數組A中寫入一項A[i] = item; 然后i++, item—; 然后重復步驟①, 直到item==0, 則進入到B的下一個元素中.

遍歷緩存數組B, 即循環執行步驟2. 最終所有有效元素都將依次寫回待排序數組A的第1,2,...n項.

如下是動圖效果:

如下是算法實現:

function countSort(array, max) {
    var tempLength = max + 1,
        temp = new Array(tempLength),
        index = 0,
        length = array.length;   
    //初始化緩存數組各項的值
    for (var i = 0; i < length; i++) {
        if (!temp[array[i]]) {
            temp[array[i]] = 0;
        }
        temp[array[i]]++;
    }
    //依次取出緩存數組的值,并寫入原數組
    for (var j = 0; j < tempLength; j++) {
        while(temp[j] > 0) {
            array[index++] = j;
            temp[j]--;
        }
    }
    return array;
}

Tips: 計數排序不改變相同元素之間原本相對的順序, 因此它是穩定的排序算法.

桶排序

桶排序即所謂的箱排序, 它是將數組分配到有限數量的桶子里. 每個桶里再各自排序(因此有可能使用別的排序算法或以遞歸方式繼續桶排序). 當每個桶里的元素個數趨于一致時, 桶排序只需花費O(n)的時間. 桶排序通過空間換時間的方式提高了效率, 因此它需要額外的存儲空間(即桶的空間).

算法的基本思想:

桶排序的核心就在于怎么把元素平均分配到每個桶里, 合理的分配將大大提高排序的效率.

如下是算法實現:

function bucketSort(array, bucketSize) {
  if (array.length === 0) {
    return array;
  }

  var i = 1,
      min = array[0],
      max = min;
  while (i++ < array.length) {
    if (array[i] < min) {
      min = array[i];                //輸入數據的最小值
    } else if (array[i] > max) {
      max = array[i];                //輸入數據的最大值
    }
  }

  //桶的初始化
  bucketSize = bucketSize || 5; //設置桶的默認大小為5
  var bucketCount = ~~((max - min) / bucketSize) + 1, //桶的個數
      buckets = new Array(bucketCount); //創建桶
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = []; //初始化桶
  }

  //將數據分配到各個桶中,這里直接按照數據值的分布來分配,一定范圍內均勻分布的數據效率最為高效
  for (i = 0; i < array.length; i++) {
    buckets[~~((array[i] - min) / bucketSize)].push(array[i]);
  }

  array.length = 0;
  for (i = 0; i < buckets.length; i++) {
    quickSort(buckets[i]); //對每個桶進行排序,這里使用了快速排序
    for (var j = 0; j < buckets[i].length; j++) {
      array.push(buckets[i][j]); //將已排序的數據寫回數組中
    }
  }
  return array;
}

Tips: 桶排序本身是穩定的排序, 因此它的穩定性與桶內排序的穩定性保持一致.

實際上, 桶也只是一個抽象的概念, 它的思想與歸并排序,快速排序等類似, 都是通過將大量數據分配到N個不同的容器中, 分別排序, 最后再合并數據. 這種方式大大減少了排序時整體的遍歷次數, 提高了算法效率.

基數排序

基數排序源于老式穿孔機, 排序器每次只能看到一個列. 它是基于元素值的每個位上的字符來排序的. 對于數字而言就是分別基于個位, 十位, 百位 或千位等等數字來排序. (不明白不要緊, 我也不懂, 請接著往下讀)

按照優先從高位或低位來排序有兩種實現方案:

MSD: 由高位為基底, 先按k1排序分組, 同一組中記錄, 關鍵碼k1相等, 再對各組按k2排序分成子組, 之后, 對后面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序后. 再將各組連接起來, 便得到一個有序序列. MSD方式適用于位數多的序列.

LSD: 由低位為基底, 先從kd開始排序,再對kd-1進行排序,依次重復,直到對k1排序后便得到一個有序序列. LSD方式適用于位數少的序列.

如下是LSD的動圖效果:

)

如下是算法實現:

function radixSort(array, max) {
    var buckets = [],
        unit = 10,
        base = 1;
    for (var i = 0; i < max; i++, base *= 10, unit *= 10) {
        for(var j = 0; j < array.length; j++) {
            var index = ~~((array[j] % unit) / base);//依次過濾出個位,十位等等數字
            if(buckets[index] == null) {
                buckets[index] = []; //初始化桶
            }
            buckets[index].push(array[j]);//往不同桶里添加數據
        }
        var pos = 0,
            value;
        for(var j = 0, length = buckets.length; j < length; j++) {
            if(buckets[j] != null) {
                while ((value = buckets[j].shift()) != null) {
                      array[pos++] = value; //將不同桶里數據挨個撈出來,為下一輪高位排序做準備,由于靠近桶底的元素排名靠前,因此從桶底先撈
                }
            }
        }
    }
    return array;
}

以上算法, 如果用來比較時間, 先按日排序, 再按月排序, 最后按年排序, 僅需排序三次.

基數排序更適合用于對時間, 字符串等這些整體權值未知的數據進行排序.

Tips: 基數排序不改變相同元素之間的相對順序, 因此它是穩定的排序算法.

小結

各種排序性能對比如下:

排序類型 平均情況 最好情況 最壞情況 輔助空間 穩定性
冒泡排序 O(n2) O(n) O(n2) O(1) 穩定
選擇排序 O(n2) O(n2) O(n2) O(1) 不穩定
直接插入排序 O(n2) O(n) O(n2) O(1) 穩定
折半插入排序 O(n2) O(n) O(n2) O(1) 穩定
希爾排序 O(n^1.3) O(nlogn) O(n2) O(1) 不穩定
歸并排序 O(nlog?n) O(nlog?n) O(nlog?n) O(n) 穩定
快速排序 O(nlog?n) O(nlog?n) O(n2) O(nlog?n) 不穩定
堆排序 O(nlog?n) O(nlog?n) O(nlog?n) O(1) 不穩定
計數排序 O(n+k) O(n+k) O(n+k) O(k) 穩定
桶排序 O(n+k) O(n+k) O(n2) O(n+k) (不)穩定
基數排序 O(d(n+k)) O(d(n+k)) O(d(n+kd)) O(n+kd) 穩定

注: 桶排序的穩定性取決于桶內排序的穩定性, 因此其穩定性不確定. 基數排序中, k代表關鍵字的基數, d代表長度, n代表關鍵字的個數.

愿以此文懷念下我那遠去的算法課程.

未完待續...

感謝 http://visualgo.net/ 提供圖片支持. 特別感謝 不是小羊的肖恩 在簡書上發布的 JS家的排序算法 提供的講解.

本問就討論這么多內容,大家有什么問題或好的想法歡迎在下方參與留言和評論.

本文作者: louis

本文鏈接: http://louiszhai.github.io/20...

參考文章

JS家的排序算法 - 簡書

白話經典算法系列之三 希爾排序的實現 - MoreWindows Blog - 博客頻道 - CSDN.NET

算法與數據結構(十三) 冒泡排序、插入排序、希爾排序、選擇排序(Swift3.0版) - 青玉伏案 - 博客園

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/82023.html

相關文章

  • JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

    摘要:之所以把歸并排序快速排序希爾排序堆排序放在一起比較,是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此,快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學好前端,先練好內功,只有內功深厚者,前端之路才...

    haitiancoder 評論0 收藏0
  • Deep in JS - 收藏集 - 掘金

    摘要:今天同學去面試,做了兩道面試題全部做錯了,發過來給道典型的面試題前端掘金在界中,開發人員的需求量一直居高不下。 排序算法 -- JavaScript 標準參考教程(alpha) - 前端 - 掘金來自《JavaScript 標準參考教程(alpha)》,by 阮一峰 目錄 冒泡排序 簡介 算法實現 選擇排序 簡介 算法實現 ... 圖例詳解那道 setTimeout 與循環閉包的經典面...

    enali 評論0 收藏0
  • 深入淺出 JavaScript Array.prototype.sort 排序算法

    摘要:快速排序是不穩定的排序算法。瀏覽器的實現不同有什么影響排序算法不穩定有什么影響舉個例子某市的機動車牌照拍賣系統,最終中標的規則為按價格進行倒排序相同價格則按照競標順位即價格提交時間進行正排序。 本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復雜度,看看它有多快? 3、...

    itvincent 評論0 收藏0
  • 基于 Javascript 排序算法

    摘要:適用于數據比較少或基本有序的情況。插入排序時間復雜度為,空間復雜度為,屬于穩定排序。算法適用于少量數據的排序。就像下圖這樣,可以理解桶的意思下圖是整個排序過程示意圖基數排序時間復雜度為,空間復雜度為,屬于穩定排序。 寫在前面 個人感覺:javascript對類似排序查找這樣的功能已經有了很好的封裝,以致于當我們想對數組排序的時候只需要調用arr.sort()方法,而查找數組元素也只需要...

    tommego 評論0 收藏0
  • JavaScript 數據結構與算法之美 - 桶排序、計數排序、基數排序

    摘要:之所以把計數排序桶排序基數排序放在一起比較,是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位,范圍太大,顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法為王。 想學好前端,先練好內功,只有內功深厚者...

    Awbeci 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<