JS實(shí)現(xiàn)快速排序

Jrain 發(fā)布于2019-08-22 18:31 / 1022人閱讀

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

看了一篇通俗易懂的快排文章快排，下面一步一步實(shí)現(xiàn)整個(gè)過程。

快排的基本思想

上面鏈接的文章對(duì)快排的思路提出了一個(gè)很形象的概念：挖坑填數(shù) + 分治法，分三個(gè)步驟實(shí)現(xiàn)：

從數(shù)組中取出一個(gè)數(shù)作為基準(zhǔn)(pivot)。

在原數(shù)組中進(jìn)行移動(dòng)，將大于基準(zhǔn)的數(shù)放到基準(zhǔn)右邊，小于基準(zhǔn)的數(shù)放到基準(zhǔn)左邊，在基準(zhǔn)左右形成兩個(gè)子數(shù)組。

在左右子數(shù)組中反復(fù)執(zhí)行步驟1、2，直到所有子數(shù)組只剩下一個(gè)數(shù)。

詳細(xì)步驟

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

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

i= 3， j = 8 時(shí)，43 > 36，將 arr[3] 挖出，放入 arr[8] 的“坑中”。接著去找數(shù)填 arr[3] 的坑，調(diào)換順序從后往前找比基準(zhǔn)小的數(shù)：

i= 3， j = 5 時(shí)，20 > 36，反向查找：

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

接著在左右兩個(gè)子數(shù)組中重復(fù)上面的排序過程，直到每個(gè)子數(shù)組的長度為1，排序結(jié)束！下面只給出每一步的執(zhí)行結(jié)果：

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) {  // 從后往前找比基準(zhǔn)小的數(shù)
        j--;
      }
      if(i < j) {
        arr[i++] = arr[j];
      }
      while(arr[i] <= pivot && i < j) {  // 從前往后找比基準(zhǔn)大的數(shù)
        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));

有的書上是以中間的數(shù)作為基準(zhǔn)數(shù)的，要實(shí)現(xiàn)這個(gè)方便非常方便，直接將中間的數(shù)和第一個(gè)數(shù)進(jìn)行交換就可以了。

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) {  // 從后往前找比基準(zhǔn)小的數(shù)
        j--;
      }
      if(i < j) {
        arr[i++] = arr[j];
      }
      while(arr[i] <= pivot && i < j) {  // 從前往后找比基準(zhǔn)大的數(shù)
        i++;
      }
      if(i < j) {
        arr[j--] = arr[i];
      }
    }
    arr[i] = pivot;
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
    return arr;
  }
}