十大排序演算法JavaScript實現總結

来源:https://www.cnblogs.com/z937741304/archive/2019/10/07/11629213.html
-Advertisement-
Play Games

花費了幾周的時間斷斷續續的練習和模仿與使用JavaScript代碼實現了十大排序演算法。 裡面有每種演算法的動圖和靜態圖片演示，看到圖片可以自己先按照圖片的思路實現一下。 github中正文鏈接，點擊查看 兩年前端學習筆記：https://github.com/zhangyachang/Notes 歡迎 ...


花費了幾周的時間斷斷續續的練習和模仿與使用JavaScript代碼實現了十大排序演算法。

裡面有每種演算法的動圖和靜態圖片演示，看到圖片可以自己先按照圖片的思路實現一下。

 

github中正文鏈接，點擊查看

兩年前端學習筆記：https://github.com/zhangyachang/Notes 歡迎點個star

 

 

排序演算法說明

1.冒泡排序(Bubble Sort) 　　1.演算法描述    2.演算法描述和實現    3.冒泡排序動圖演示

2.選擇排序（Selection Sort    1.演算法簡介     2.演算法描述和實現     3.選擇排序動圖演示

3.插入排序(Insertion Sort)     1.演算法簡介     2.演算法的描述和實現     3.插入排序動圖演示

4.希爾排序(Shell Sort)     1.演算法簡介     2.演算法描述和實現     3.希爾排序圖示

5.歸併排序(Merge Sort)     1.演算法簡介      2.演算法描述和實現     3.歸併排序動圖演示

6.快速排序(Quick Sort)     1.演算法簡介     2.演算法描述和實現     3.快速排序動圖演示

7.堆排序（Heap Sort）     1.演算法簡介     2.演算法描述和實現      3.堆排序動圖演示

8.計數排序(Counting Sort)     1.演算法簡介     2.演算法描述和實現     3.計數排序動圖演示

9.桶排序（Bucket Sort）     1.演算法簡介     2.演算法描述和實現     3.桶排序圖示

10.基數排序（Radix Sort）     1.演算法簡介     2.演算法描述和實現     3.基數排序動圖演示後記

 

排序演算法說明

1.排序的定義

對一序列對象根據某個關鍵字進行排序

輸入：n個數：a1,a2,a3,...,an 輸出：n個數的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an'。

再講的形象點就是排排坐，調座位，高的站後面，矮的站前面。

2.對於評述演算法優劣術語的說明

穩定：如果a原本在b前面，而a=b,排序之後a仍然在b的前面；不穩定：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；

內排序：所有排序操作都在記憶體中完成；外排序：由於數據太大，因此把數據放在磁碟中，而排序通過磁碟和記憶體的數據傳輸才能進行；

時間複雜度：一個演算法執行所耗費的時間。空間複雜度：運行完一個程式所需記憶體的大小。

3.排序演算法圖片總結

 

 

 

圖片名詞解釋：n：數據規模 k 桶的個數 in-place：占用常數記憶體，不占用額外記憶體 Out-place：占用額外記憶體。

 

 

 

1.冒泡排序(Bubble Sort)

好的，開始總結第一個排序演算法，冒泡排序。我想對於它每個學過C語言的都會瞭解的吧，這可能是很多人接觸的第一個排序演算法。

1.演算法描述

冒泡排序是一種簡單的排序演算法。它重覆的走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重覆的進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢”浮“到數列的頂端。

2.演算法描述和實現

具體的演算法描述如下

  • <1>.比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

  • <2>.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數。

  • <3>.針對所有的元素重覆以上的操作，除了最後一個；

  • <4>.重覆步驟1~3，直到排序完成。

JavaScript代碼實現：

function bubbleSort(arr) {
  let len = arr.length;

  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {  // 相鄰元素兩兩對比
        let tmp = arr[j];         // 元素交換
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }

  return arr;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

改進冒泡排序：設置一標誌性變數post，用於記錄每趟排序中最後一次交換的位置。由於post位置之後的記錄均已交換到位，故在進行下一趟排序時只要掃描到post位置即可。

改進後演算法如下。

function bubbleSort2(arr) {
  let i = arr.length - 1;
  while (i > 0) {
    let pos = 0;
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        pos = j; // 記錄最後修改位置
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
    i = pos;
  }
  return arr;
}
​
​
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1];
console.log(bubbleSort2(arr));

傳統冒泡排序中每一趟排序操作只能找到一個最大值或最小值,我們考慮利用每趟排序中進行正向和反向兩遍冒泡的方法可以得到兩個最終值（最大者和最小者），從而使排序躺數幾乎減少了一半。

改進後的排序演算法實現為

function bubbleSort3(arr) {
  var low = 0;
  var high = arr.length - 1;
  var tmp, j;
  console.time('2.改進後的冒泡排序耗時');
  while (low < high) {

    for (j = low; j < high; j++) {
      // 這裡排序出最高的
      if (arr[j] > arr[j + 1]) { // 正向冒泡，找出最大者
        tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
    high--;

    for (j = high; j > low; j--) { // 反向冒泡 找出最小者
      if (arr[j] < arr[j - 1]) {
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
      }
    }
    low++;
  }
  console.timeEnd('2.改進後的冒泡排序耗時');
  return arr;
}


var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

 

 

 

 由圖可以看出改進後的冒泡排序明顯的時間複雜度更低了，耗時更短了。

3.冒泡排序動圖演示

 

演算法分析

  • 最佳情況：T(n) = O(n)  當輸入值的數據已經是正序時（都已經是正序了，為毛何必還排序呢....）

  • 最差情況：T(n) = O(n2)  當輸入的數據是反序時(卧槽，我直接反序不就完了....)

  • 平均情況：T(n) = O(n2)

 

2.選擇排序（Selection Sort）

表現最穩定的排序演算法之一（這個穩定性不是指演算法層面上的穩定哈），因為無論是什麼數據進去都是O(n²)的時間複雜度......所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的記憶體空間了吧。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。

1.演算法簡介

選擇排序（Selection-sort）是一種簡單直觀的排序演算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小(大)元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

2.演算法描述和實現

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體演算法描述如下：

  • <1>.初始狀態：無序區為R[1,...n]，有序區為空；

  • <2>.第i趟排序（i=1,2,3,4,...n-1）開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中-選出關鍵字最小的記錄R[k],將它與無序區的第1個記錄R交換，使R[1,...i]和R[i+1...n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；

  • <3>.n-1趟結束，數組有序化了。

 

JavaScript代碼實現

// 選擇排序
function selectionSort(arr) {
  var length = arr.length;
  var minIndex, tmp;
  console.time("選擇排序耗時");
  for (var i = 0; i < length - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    tmp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = tmp;
  }
  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));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

3.選擇排序動圖演示

演算法分析

  • 最佳情況：T(n) = O(n)

  • 最差情況：T(n) = O(n2)

  • 平均情況：T(n) = O(n2)

 

3.插入排序(Insertion Sort)

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。當然，如果你說你打撲克牌摸排的時候從來不按牌的大小調整牌，那估計這輩子你對插入排序的演算法都不會產生任何興趣了...

1.演算法簡介

插入排序（Insertion-Sort）的演算法描述是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描找到對應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把一排序元素逐步向後挪威，為最新元素提供插入空間。

2.演算法的描述和實現

一般來說，插入排序都採用in-place在數組上實現。具體的演算法描述如下：

  • <1>.從第一個元素開始，該元素可以認為已經被排序。

  • <2>.取出下一個元素，在已經排序的元素序列中從後向前掃描

  • <3>.如果該元素（已排序）大於新元素，將該元素移到下一位置

  • <4>.重覆步驟3，直到找到已排序的元素小於或等於新元素的位置；

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

  • <6>.重覆步驟2~5

 

JavaScript代碼實現：

// 這個是我的實現，感覺代碼好長的樣子...
// 插入排序
function insertionSort(arr) {

  console.log('列印這個東西', Object.prototype.toString.call(arr), Object.prototype.toString.call(arr).slice(8, -1) === 'Array');

  var length = arr.length;
  var tmp;
  console.time('選擇排序耗時');
  for (var i = 0; i < length; i++) {
    let tmp = arr[i];
    for (var j = i; j >= 0; j--) {
      if (j === 0) {
        arr[0] = tmp;
        break;
      }

      if (tmp < arr[j - 1]) {
        arr[j] = arr[j - 1];
      } else {
        arr[j] = tmp;
        break;
      }
    }
  }
  console.timeEnd('選擇排序耗時');
  return arr;
}
// 10 7 8

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(insertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

JavaScript代碼實現

// 插入排序
function insertionSort(arr) {
  if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array') {
    console.time('插入排序耗時');
    for (var i = 1, length = arr.length; i < length; i++) {
      var key = arr[i];
      var j = i - 1;
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
    console.timeEnd('插入排序耗時');
    return arr;
  } else {
    return `array is not an array`;
  }
}
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(insertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

改進插入排序：查找插入位置時使用二分查找的方式

function binaryInsertionSort(arr) {
  if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array') {
    console.time('二分插入排序耗時');
    var length = arr.length;
    for (var i = 1; i < length; i++) {

      var left = 0;
      var key = arr[i];
      var right = i - 1;

      while (left <= right) {
        var middle = parseInt((left + right) / 2);
        if (key < arr[middle]) {
          right = middle - 1;
        } else {
          left = middle + 1;
        }
      }

      for (var j = i - 1; j >= left; j--) {
        arr[j + 1] = arr[j]
      }
      arr[left] = key;
    }
    console.timeEnd('二分插入排序耗時');
    return arr;
  } else {
    throw new Error('arr is not arr');
  }
}

 改進前後對比

 

 

 

3.插入排序動圖演示

演算法分析

  • 最佳情況：輸入數組按升序排序。T(n) = O(n)

  • 最壞情況：輸入數組按降序排序。T(n) = O(n2)

  • 平均情況：T(n) = O(n2)

4.希爾排序(Shell Sort)

1959年Sheel發明：第一個突破O(n^2)的排序演算法；是簡單插入排序的改進版；它與插入排序的不同之處在於，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。

1.演算法簡介

希爾排序的核心在於間隔序列的設定。既可以提前設好間隔序列，也可以動態的定義間隔序列。動態定義間隔序列的演算法是《演算法（第4版）的合著者Robert Sedgewick提出的》。

2.演算法描述和實現

先將整個待排序的記錄序列分割成為若幹子序列分別進行直接插入排序，具體演算法描述：

  • <1>.選擇一個增量序列t1，t2，...，tk，其中ti>tj，tk = 1

  • <2>.按增量序列個數k，對序列進行k趟排序；

  • <3>.每趟排序，根據對應的增量ti，將待排序列分割成若幹長度為m的子序列，分別對各子表進行直接插入排序。僅增量因數為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。

JavaScript代碼實現

function shellSort(arr) {
  console.log('調用了函數方法');

  var len = arr.length;
  var tmp;
  var gap = 1;
  console.time('希爾排序耗時');
  while (gap < len / 5) { // 動態定義間隔序列
    gap = gap * 5 + 1;
    console.log('gap -------- ', gap);
  }
    
  // 在這個裡面其實是對每一組數據又進行了插入排序 真的是寫不出來不知道，想通了寫出來一次感覺就簡單了
    
  for (gap; gap > 0; gap = Math.floor(gap / 5)) {
    console.log('gap ===== >', gap);
    for (var i = 0; i < len; i++) {
      tmp = arr[i];
      for (var j = i - gap; j >= 0 && tmp < arr[j]; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = tmp;
    }
  }
  console.timeEnd('希爾排序耗時');
  return arr;
}

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

3.希爾排序圖示

 

演算法分析

  • 最佳情況：T(n) = O(nlog2 n)

  • 最壞情況：T(n) = O(nlog2 n)

  • 平均情況：T(n) =O(nlog n)

5.歸併排序(Merge Sort)

和選擇排序一樣，歸併排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是O(n log n)的時間複雜度。代價是需要額外的記憶體空間。

1.演算法簡介

歸併排序時建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。歸併排序是一種穩定的排序方法。將已有的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，成為2-路歸併。

2.演算法描述和實現

具體演算法描述如下：

  • <1>.把長度為n的輸入序列分成兩個長度為n/2的子序列；

  • <2>.對這兩個子序列分別採用歸併排序。

  • <3>.將兩個排序好的子序列合併成一個最終的排序序列。

JavaScript代碼實現

// 這個思想有點難啊，看起來和之前的二叉樹的中序遍歷差不多

function mergeSort(arr) { // 採用自上而下的遞歸方法
  // console.log('mergeSort', arr);
  var length = arr.length;
  if (length < 2) {
    return arr;
  }

  var middle = Math.floor(length / 2);
  var left = arr.slice(0, middle);
  var right = arr.slice(middle);
  // console.log('mergeSort', 'left', left, 'right', right);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  var result = [];
  console.log('left', left, 'right', right);
  // 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));

3.歸併排序動圖演示

 

演算法分析：

  • 最佳情況：T(n) = O(n)

  • 最差情況：T(n) = O(nlogn)

  • 平均情況：T(n) = O(nlogn)

 

6.快速排序(Quick Sort)

快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數據最快的演算法之一了。

1.演算法簡介

快速排序的基本思想：通過一趟排序將待記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

2.演算法描述和實現

快速排序使用分治法來把一個串（list）分為兩個子串（sub-list）。具體演算法描述如下：

  • <1>.從數列中挑出一個元素，稱為“基準”(pivot)

  • <2>.重新排序數列，所有元素比基準值小的擺放在最前面，所有元素比基準值大的擺在基準的後面（相同的可任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（Partition）操作；

  • <3>.遞歸的（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

 

JavaScript代碼實現：

// 這個裡面的核心代碼是我寫的，比它的好像差一些 它的核心原理有點沒看懂，和下麵的那個動圖演示有點不一樣，他選擇的基準是右側的那個。
// 感覺不是這種排列方法

function quickSort(arr, left, right) {
  if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof length === 'number' && typeof right === 'number') {

    // console.log('進來的數組', JSON.stringify(arr), 'left ==>', left, 'right===>', right);
    if (left < right) {
      var key = arr[left]; // 起始位置
      var setPos = left + 1; // 設置的位置
      var tmp;
      for (var i = left + 1; i <= right; i++) {
        if (arr[i] < key) {
          tmp = arr[i]; // 交換位置，並將下次小於的位置+1
          arr[i] = arr[setPos];
          arr[setPos] = tmp;
          setPos++;
        }
      }
      // 迴圈完成之後將key與 pos-1的位置交換
      arr[left] = arr[setPos - 1];
      arr[setPos - 1] = key;
      // console.log('每一次排序', '當前key值===>', key, '排序完成當前數組===>', JSON.stringify(arr));

      quickSort(arr, left, setPos - 2);
      quickSort(arr, setPos, right);
      // console.log('arr=======>', arr);
    }
  } else {
    return 'array is not an Array or left or right is not a number!';
  }
  return arr;
}


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

 

這個演算法寫法，感覺沒有我的寫法正常思維

function quickSort(array, 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;
            for (var j = left; j <= right; j++) {
                if (array[j] <= x) {
                    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!';
    }
}

3.快速排序動圖演示

 

這個演算法看起來簡單了許多

function quickSort(arr) {
  if (arr.length <= 1) { return arr };
  var pivoIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivoIndex, 1)[0]; // 將要選擇排序的那一位選舉出來 摘出來
  var left = [];
  var right = [];

  // 小的放左邊，大的放右邊
  for (var i = 0, len = arr.length; i < len; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  console.log('left', left, 'right', right);
  return quickSort(left).concat([pivot], quickSort(right));
}

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// var arr = [7, 3, 2, 10, 13, 8, 5];
console.log(quickSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

 

演算法分析：

  • 最佳情況：T(n) = O(nlogn)

  • 最差情況：T(n) = O(n2)

  • 平均情況：T(n) = O(nlogn)

 

7.堆排序（Heap Sort）

堆排序可以說是一種利用堆的概念來排序的選擇排序。

1.演算法簡介

堆排序（HeapSort）是指利用堆這種數據結構所涉及的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子節點的鍵值或索引總是小於（或者大於）它的父節點。

 

2.演算法描述和實現

具體演算法描述如下

  • <1>.將初始待排序的關鍵字序列（R1，R2...Rn）構建成大頂堆，此堆為初始的無序區。

  • <2>.將堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區[R1,R2,...Rn-1]和新的有序區(Rn),且滿足R[1,2...n-1]<R[n];

  • <3>.由於交換後新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區（R1，R2...Rn-1）調整為新堆，然後再將R[1]與無序區最後一個元素交換，得到新的無序區（R1，R2...Rn-2）和新的有序區（Rn-1，Rn）。不斷重覆此過程直到有序區的元素個數為n-1，則整個排序過程完成。

JavaScript代碼實現：

/*
  方法說明：堆排序
  @param {Array} arr 待排序數組
*/

function heapSort(arr) {
  console.log('堆排序');


  console.log();
  if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array') {

    var heapSize = arr.length;
    var temp;

    console.log('待排序數組的長度===>', heapSize);


    console.log('建造之前的堆的樣式', JSON.stringify(arr));
    // 建造堆
    for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      heapify(arr, i, heapSize);
    }
    console.log('堆初始化完成之後的樣式', JSON.stringify(arr));

    // 現在要把最大的放到最後一個，最後一個放到第一個，把堆的大小減少一個，在慢慢的把最大的迴圈上去
    console.time('堆排序耗時');
    for (var j = heapSize - 1; j >= 1; j--) {
      temp = arr[0];
      arr[0] = arr[j];
      arr[j] = temp;
      heapify(arr, 0, --heapSize);
    }
    console.timeEnd('堆排序耗時');
    return arr;
  } else {
    return 'array is not array';
  }
}

/*
  建堆：維護堆的性質
  @param {Array} arr 數組
  @param {Number} x 數組下標
  @param {Number} len 堆大小
*/
function heapify(arr, x, len) {
  if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') {
    var l = 2 * x + 1; // 左下標
    var r = 2 * x + 2; // 右下標
    var largest = x; // 預設最大的是父節點
    var temp; // 用於交換數據存儲的中間值

    // 尋找到一個堆中的最大值
    if (l < len && arr[l] > arr[largest]) {
      largest = l;
    }
    if (r < len && arr[r] > arr[largest]) {
      largest = r;
    }

    // 如果最大者不是父節點 則交換位置
    if (largest != x) {
      temp = arr[x];
      arr[x] = arr[largest];
      arr[largest] = temp;
      // 遞歸尋找
      heapify(arr, largest, len);
    }
  } else {
    return 'arr is not an array or x is not a number';
  }
}


var arr = [91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81, 22];
console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]

3.堆排序動圖演示

 

演算法分析

  • 最佳情況：T(n) = O(nlogn)

  • 最差情況：T(n) = O(nlogn)

  • 平均情況：T(n) = O(nlogn)

8.計數排序(Counting Sort)

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。

1.演算法簡介

計數排序（Counting sort）是一種穩定的排序演算法。計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等於i的元素的個數。然後根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序。

 

2.演算法描述和實現

具體演算法描述如下

  • <1>.找出待排序的數組中的最大和最小的元素；

  • <2>.統計數組中每個值為i的元素出現的次數，存入數組C的第i項；

  • <3>.對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）;

  • <4>.反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

 

JavaScript代碼實現

function countingSort(arr) {
  console.log('計數排序');

  var len = arr.length;
  var B = [];
  var C = [];
  var min = max = arr[0];

  console.time('計數排序耗時');
  // 初始化計數排序
  for (var i = 0; i < len; i++) {
    min = min <= arr[i] ? min : arr[i];
    max = max >= arr[i] ? max : arr[i];
    C[arr[i]] = C[arr[i]] ? C[arr[i]] + 1 : 1;
  }
  console.log('初始化結束之後', JSON.stringify(C));
  var k = 0;
  for (var j = min; j < max; j++) {
    C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
  }

  console.log('計算完成之後', JSON.stringify(C));
  console.log('計算完成之後arr', JSON.stringify(arr));
  // 現在C的下標就是這個值，C的內容就是這個值的個數
  debugger;
  for (var k = len - 1; k >= 0; k--) {
    console.log('C[arr[l] - 1]===>', C[arr[k]] - 1, 'arrk===>', arr[k]);
    B[C[arr[k]] - 1] = arr[k];
    C[arr[k]]--;
  }
  console.timeEnd('計數排序耗時');
  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)); //[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

 

3.計數排序動圖演示

 

演算法分析

當輸入的元素是n個0到k之間的整數時，它的運行時間是O(n + k)。計數排序不是比較排序，排序的速度快於任何比較排序演算法。由於用來計數的數組C的長度取決於待排序數組中數據的範圍（等於待排序數組的最小值的差加上1），這使得計數排序對於數據範圍很大的數組，需要大量時間和記憶體。

 

  • 最佳情況：T(n) = O(n + k)

  • 最差情況：T(n) = O(n+k)

  • 平均情況：T(n) = O(n+k)

 

9.桶排序（Bucket Sort）

桶排序是計數排序的升級版。它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。

1.演算法簡介

桶排序(Bucket sort)的工作原理：假設輸入數據服從均勻分佈，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序）

2.演算法描述和實現

具體演算法描述如下：

  • <1>.設置一個定量的數組當做空桶；

  • <2>.遍歷輸入數據，並且把數據一個一個放到對應的桶里去；

  • <3>.對每個不是空的桶進行排序；

  • <4>.從不是空的桶里把排好序的數據拼接起來。

/*
  方法說明：桶排序
  @param {Array} 數組
  @param {Number} 桶的數量
*/

function bucketSort(arr, num) {
  if (arr.length <= 1) {
    return arr;
  }
  var len = arr.length;
  var buckets = [];
  var result = [];
  var min = max = arr[0];
  var regex = '/^[1-9]+[0-9]*$/';
  var space, n = 0;

  console.log('排序長度 ===>', len);

  // 定義桶的數量
  num = num || (num > 1 && regex.test(num) ? num : 10);
  console.log('桶排序耗時');
  // 尋找到最大值和最小值
  for (var i = 0; i < len; i++) {
    min = (min <= arr[i]) ? min : arr[i];
    max = (max >= arr[i]) ? max : arr[i];
  }
  console.log('最大值===> max', max, '最小值===> min', min);

  space = (max - min + 1) / num;

  for (var j = 0; j < len; j++) {
    var index = Math.floor((arr[j] - min) / space);
    console.log(`第${j}項，值==> ${arr[j]} 桶的索引為 ${index}, space ===> ${space}`);
    if (buckets[index]) { // 非空桶，插入排序
      var key = arr[j];
      var k = buckets[index].length - 1;
      while (k >= 0 && buckets[index][k] > key) {
        buckets[index][k + 1] = buckets[index][k];
        k--;
      }
      buckets[index][k + 1] = key;
    } else { // 空桶初始化
      buckets[index] = [];
      buckets[index].push(arr[j]);
    }
  }

  while (n < num) {
    result = result.concat(buckets[n]);
    n++;
  }
  console.log('桶排序完成===>', buckets);
  return result;
}



var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bucketSort(arr, 4));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

 

/*方法說明：桶排序
@param  array 數組
@param  num   桶的數量*/
function bucketSort(array, num) {
    if (array.length <= 1) {
        return array;
    }
    var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0;
    num = num || ((num > 1 && regex.test(num)) ? num : 10);
    console.time('桶排序耗時');
    for (var i = 1; i < len; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
    }
    space = (max - min + 1) / num;
    for (var j = 0; j < len; j++) {
        var index = Math.floor((array[j] - min) / space);
        if (buckets[index]) {   //  非空桶，插入排序
            var k = buckets[index].length - 1;
            while (k >= 0 && buckets[index][k] > array[j]) {
                buckets[index][k + 1] = buckets[index][k];
                k--;
            }
            buckets[index][k + 1] = array[j];
        } else {    //空桶，初始化
            buckets[index] = [];
            buckets[index].push(array[j]);
        }
    }
    while (n < num) {
        result = result.concat(buckets[n]);
        n++;
    }
    console.timeEnd('桶排序耗時');
    return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bucketSort(arr,4));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

 

3.桶排序圖示

 

 

演算法分析

桶排序最好情況下使用線性時間O(n),桶排序的時間複雜度，取決於對各個桶之間數據進行排序的時間複雜度，因為其他部分的時間複雜度都為O(n)。很顯然，桶劃分的越小，各個桶之間的數據越少，排序所用的時間也會越少。但相應的的空間消耗就會增大。

  • 最佳情況：T(n) = O(n + k)

  • 最差情況：T(n) = O(n + k)

  • 平均情況：T(n) = O(n2)

 

10.基數排序（Radix Sort）

基數排序也是非比較的排序演算法，對每一位進行排序，從最低位開始排序，複雜度為O(kn),為數組長度，k為數組中的數的最大的位數；

 

1.演算法簡介

基數排序時按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優先順序排序。最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前。基數排序基於分別排序，分別收集，所以是穩定的。

 

2.演算法描述和實現

具體演算法描述如下：

  • <1>.取得數組中的最大數，並取得位數。

  • <2>.arr為原始數組，從最低位開始取每個位組成radix數組；

  • <3>.對radix進行計數排序（利用計數排序適用於小範圍數的特點）

 

JavaScript代碼實現

/*
  基數排序適用於：
    (1)數據範圍比較小,建議小於1000
    (2)每個數值都要大於等於0
  
  @param {Array} arr 待排序數組
  @param {Number} 最大位數
*/
function radixSort(arr, maxDigit) {
  var mod = 10;
  var dev = 1;
  var counter = [];

  console.time('基數排序耗時');
  for (var i = 0; i < maxDigit; i++ , mod *= 10, dev *= 10) {
    for (var j = 0, len = arr.length; j < len; j++) {
      var bucket = parseInt((arr[j] % mod) / dev);
      con
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • SUSE CaaS Platform 4 - 使用 Ceph RBD 作為持久存儲（動態）
    存儲類 存儲類（storage class）是kubernetes資源類型，它是由管理員為管理PV之便而按需創建的類別 存儲類好處是支持 PV 的動態創建，系統按PVC的需求標準動態創建適配的PV會為存儲管理帶來極大的靈活性。 PV的動態供給，其重點是在存儲類的定義，其分類大概是對存儲的性能進行分類 ...
  • 資料庫系統（二）--關係型資料庫之關係代數
    關係型資料庫-關係操作集合 1、 基本的關係操作 關係模型中常用的關係操作包括查詢(Query)操作和插入(Insert)、刪除 (Delete)、修改(Update)操作兩大部分。 查詢操作分為：選擇、投影、連接、除、並、差、交、笛卡爾積等； 五種基本操作：選擇、投影、並、差、笛卡爾積； 關係操作 ...
  • ES 32 - Elasticsearch 數據建模的探索與實踐
    本篇博文通過對ES中不同類型的欄位的建模方案進行說明, 並結合實際案例, 演示了index、stored、dynamic等參數的使用, 並歸納了ES處理關聯關係、避免太多的欄位、避免正則查詢、避免空值引起聚合結果失真等最佳實踐. 如有疑問, 留言區見
  • Mysql 單表查詢where初識
    Mysql 單表查詢where初識 準備數據 數據基本測試 where 條件過濾 比較運算符 , 邏輯運算符, 範圍判斷, 空判斷, 模糊查詢 邏輯運算符: and, or, not Null 判斷 is null; is not null 範圍查詢 in; between...and in 用於離 ...
  • 【乾貨總結】:可能是史上最全的MySQL和PGSQL對比材料
    關鍵詞：PostgreSQL 11、MySQL5.7 比較版本：PostgreSQL 11 VS MySQL5.7（innodb引擎） Oracle官方社區版 版權情況：PostgreSQL 11（免費開源）、MySQL5.7 Oracle官方社區版（免費開源） ...
  • Python學習日記(三十六) Mysql資料庫篇 四
    MySQL作業分析 五張表的增刪改查: 完成所有表的關係創建 創建教師表(tid為這張表教師ID,tname為這張表教師的姓名) 創建班級表(cid為這張表班級ID,caption為這張表班級門號) 創建課程表(cid為這張表課程ID,cname為課程名稱,teacher_id為任課教師的ID) 創 ...
  • Jetpack系列：應用內導航的正確使用方法
    今天小編要分享的還是Android Jetpack庫的基本使用方法，本篇介紹的內容是Jetpack Navigation組件，讓我們一起學習，為完成年初制定的計劃而努力吧！ 組件介紹 導航，是指提供用戶在應用程式中的不同內容之間進行瀏覽、退出的交互功能。如我們在Android手機上常常用到的物理/虛 ...
  • axios 源碼解析(中) 代碼結構
    axios現在最新的版本的是v0.19.0，本節我們來分析一下它的實現源碼，首先通過 gitHub地址獲取到它的源代碼,地址:https://github.com/axios/axios/tree/v0.19.0 下載後就可以看到axios的目錄結構,主目錄下有一個index.js文件，該文件比較簡 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類