首頁 >web前端 >js教程 >JavaScript實作快速排序的演算法思想

JavaScript實作快速排序的演算法思想

不言
不言原創
2018-07-11 09:16:391281瀏覽

這篇文章主要介紹了關於JavaScript實現快速排序的演算法思想,有著一定的參考價值,現在分享給大家,有需要的朋友可以參考一下

目前,最常見的排序演算法大概有七、八種,其中"快速排序"(Quicksort)使用得最廣泛,速度也較快。它是圖靈獎得主 東尼·霍爾(C. A. R. Hoare)於1960時提出來的。

快速排序"的想法很簡單,整個排序過程只需要三步驟:

  (1)在資料集之中,選擇一個元素作為"基準"(pivot)。

  (2)所有小於"基準"的元素,都移到"基準"的左邊;所有大於"基準"的元素,都移到"基準"的右邊。

  (3)對"基準"左邊和右邊的兩個子集,不斷重複第一步和第二步,直到所有子集只剩下一個元素為止。

舉例來說,現在有一個資料集{85 , 24, 63, 45, 17, 31, 96, 50},怎麼對其排序呢?

  第一步,選擇中間的元素45作為"基準"。(基準值可以任意選擇,但是選擇中間的值比較容易理解。)

  第二步,按照順序,將每個元素與"基準"進行比較,形成兩個子集,一個"小於45",另一個"大於等於45"。

  第三步,對兩個子集不斷重複第一步和第二步,直到所有子集只剩下一個元素到目前為止。

依照先前的步驟,定義一個quickSort函數:

var quickSort = function(arr) { //参数是一个数组
  if (arr.length <= 1) { return arr; } //检查数组的元素个数,如果小于等于1,就返回。
  var pivotIndex = Math.floor(arr.length / 2); //选择"基准"(pivot),并将其与原数组分离,再定义两个空数组,用来存放一左一右的两个子集。
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++){ //开始遍历数组,小于"基准"的元素放入左边的子集,大于基准的元素放入右边的子集。
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

實作上面動畫:

演算法想法:

從數列中挑出一個元素,稱為「基準」(pivot);


重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分區退出之後,該基準就處於數列的中間位置。這個稱為分區(partition)操作;

遞歸地(recursive)將小於基準值元素的子數列和大於基準值元素的子數列排序;

######實作程式碼:###
function quickSort(arr, left, right) { 
  var len = arr.length,
  partitionIndex,
  left = typeof left != &#39;number&#39; ? 0 : left,
  right = typeof right != &#39;number&#39; ? len - 1 : right;
 
 
  if (left < right) {
  partitionIndex = partition(arr, left, right);
  quickSort(arr, left, partitionIndex-1);
  quickSort(arr, partitionIndex+1, right);
  }
  return arr;
}
function partition(arr, left ,right) { // 分区操作
  var pivot = left,                // 设定基准值(pivot)
    index = pivot + 1;
  for (var i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }
  swap(arr, pivot, index - 1);
   return index-1;
}
 
function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
    --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
    ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
 
function quickSort2(arr, low, high) {
  if (low < high) {
  let pivot = partition2(arr, low, high);
  quickSort2(arr, low, pivot - 1);
  quickSort2(arr, pivot + 1, high);
  }
  return arr;
}
### 以上就是本文的全部內容,希望對大家的學習有所幫助,更多相關內容請關注PHP中文網!#### ##相關推薦:#########js陣列隨機排序的方法################js將任意元素移到指定位置######## ##

以上是JavaScript實作快速排序的演算法思想的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn