JS實現快速排序

Jrain 發布于2019-08-22 18:31 / 1006人閱讀

摘要：看了一篇通俗易懂的快排文章快排，下面一步一步實現整個過程。快排的基本思想上面鏈接的文章對快排的思路提出了一個很形象的概念挖坑填數分治法，分三個步驟實現從數組中取出一個數作為基準。

看了一篇通俗易懂的快排文章快排，下面一步一步實現整個過程。

快排的基本思想

上面鏈接的文章對快排的思路提出了一個很形象的概念：挖坑填數 + 分治法，分三個步驟實現：

從數組中取出一個數作為基準(pivot)。

在原數組中進行移動，將大于基準的數放到基準右邊，小于基準的數放到基準左邊，在基準左右形成兩個子數組。

在左右子數組中反復執行步驟1、2，直到所有子數組只剩下一個數。

詳細步驟

初始數組如下所示，取第一個數為基準，此時：i = 0， j = 9， pivot = arr[0] = 36，此時 i = 0 的位置就挖了一個坑，等待小于36的數來填這個坑。i 先不變，j-- 從后往前找小于基準的數：

i= 0， j = 8 時，24 < 36，將 arr[8] 挖出，放入 arr[0] 的“坑中”（實際上在寫程序時，是 arr[8] 與 arr[0] 交換）。接著arr[8] 的坑怎么填？調換順序從前往后找比基準大的數（i++，j 不變）：

i= 3， j = 8 時，43 > 36，將 arr[3] 挖出，放入 arr[8] 的“坑中”。接著去找數填 arr[3] 的坑，調換順序從后往前找比基準小的數：

i= 3， j = 5 時，20 > 36，反向查找：

i= j = 5 時，退出，第一趟排序完成，以 arr[5] = 36 為界分為左右兩個子數組：

接著在左右兩個子數組中重復上面的排序過程，直到每個子數組的長度為1，排序結束！下面只給出每一步的執行結果：

JS代碼

// 快排
function quickSort(arr, i, j) {
  if(i < j) {
    let left = i;
    let right = j;
    let pivot = arr[left];
    while(i < j) {
      while(arr[j] >= pivot && i < j) {  // 從后往前找比基準小的數
        j--;
      }
      if(i < j) {
        arr[i++] = arr[j];
      }
      while(arr[i] <= pivot && i < j) {  // 從前往后找比基準大的數
        i++;
      }
      if(i < j) {
        arr[j--] = arr[i];
      }
    }
    arr[i] = pivot;
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
    return arr;
  }
}

// example
let arr = [2, 10, 4, 1, 0, 9, 5 ,2];
console.log(quickSort(arr, 0 , arr.length-1));

有的書上是以中間的數作為基準數的，要實現這個方便非常方便，直接將中間的數和第一個數進行交換就可以了。

function quickSort(arr, i, j) {
  if(i < j) {
    let left = i;
    let right = j;
    let mid = Math.floor((left+right)/2);
    let temp = arr[left];
    arr[left] = arr[mid];
    arr[mid] = temp;
    let pivot = arr[left];
    while(i < j) {
      while(arr[j] >= pivot && i < j) {  // 從后往前找比基準小的數
        j--;
      }
      if(i < j) {
        arr[i++] = arr[j];
      }
      while(arr[i] <= pivot && i < j) {  // 從前往后找比基準大的數
        i++;
      }
      if(i < j) {
        arr[j--] = arr[i];
      }
    }
    arr[i] = pivot;
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
    return arr;
  }
}

GPU云服務器云服務器 js快速排序快速排序法js js實現table排序快速排序

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

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

js實現冒泡排序,快速排序,選擇排序

摘要：用冒泡排序快速排序選擇排序冒泡排序冒泡排序是比較經典的排序方法，是一種用時間換空間的排序方法。找到并交換的時候，指針位置不變。選擇排序沒趟都會產生最小值，它不是相鄰元素的比較而是在該元素設置一個索引。選擇排序循環找到從開始到最后的最小的數用js冒泡排序,快速排序,選擇排序 1.冒泡排序冒泡排序是比較經典的排序方法，是一種用時間換空間的排序方法。我總結了一下它的特點：（1）它的時間復...

bbbbbb 2019-08-22 16:56 評論0 收藏0
關于JS的快速排序實現方法

摘要：所有關鍵字比該記錄關鍵字小的記錄放置在前一部分，所有比它大的記錄放置在后一部分，并把改記錄排在這兩部分的中間稱為該記錄歸位，這個過程稱作一次快速排序。代碼如下大佬的代碼還是比較厲害的，簡單易懂，佩服以上就是相關的快速排序的實現方法由于自己不是計算機專業，數據結構沒有太多研究，曾經面試時有被問過關于快速排序以及冒泡排序的寫法，冒泡排序比較簡單，當時能回答出來，但是快速排序當時就比較懵逼...

LeexMuller 2019-08-21 17:40 評論0 收藏0
js算法-快速排序(Quicksort)

摘要：快速排序英語，又稱劃分交換排序，簡稱快排，一種排序算法，最早由東尼霍爾提出。快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序n個項目要O(nLogn)次比較。在最壞狀況下則需要O(n^2)次比較，但這種狀況并不常見。事實上，快速排序O(nLogn)通常明顯比其他算...

Taste 2019-08-23 14:35 評論0 收藏0
排序算法速度測試（插入排序、二分法插入、選擇排序、快速排序、堆排序）js實現

摘要：公共函數庫用于取出隨機排列的數字原數組給原數組賦值排序算法插入排序時間復雜度二分法插入排序選擇排序快速排序一堆排序測試用例插入排序時間測試二分法插入排序時間測試選擇排序時間測試快速排序時間測試一堆公共函數庫（用于取出隨機排列的數字） module.exports={ randomIntegerArray:function(count){ var origina...

mochixuan 2019-08-20 16:04 評論0 收藏0
快速排序js實現

摘要：然后再分別對基數左邊和右邊的數組進行相同的操作，直到數組中只有一個元素時，返回該數組。快速排序算法今天大概講下使用js實現快速排序算法：快速排序算法的思想類似于二分法，每次都是在數組中選擇一個基數（可以是任意一個位置的數，不過一般選擇中間的數字或者最左邊的數字），每一輪結束后，比該基數小的數都位于該基數的左邊，比該基數大的數都位于該基數的右邊。然后再分別對基數左邊和右邊的數組進行...

zhoutk 2019-08-22 16:22 評論0 收藏0
js 排序算法之快速排序

摘要：快速排序是一種劃分交換排序。快速排序基于冒泡遞歸分治。他在大數據情況下是最快的排序算法之一，平均事件復雜度很低而且前面的系數很小，在大量隨機輸入的情況下最壞情況出現的概率是極小的。快速排序是一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法。分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。...

Eidesen 2019-08-23 11:38 評論0 收藏0