這篇文章主要介紹了關(guān)于JavaScript實(shí)現(xiàn)快速排序的算法思想，有著一定的參考價值，現(xiàn)在分享給大家，有需要的朋友可以參考一下

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

快速排序"的思想很簡單，整個排序過程只需要三步：

　?。?）在數(shù)據(jù)集之中，選擇一個元素作為"基準(zhǔn)"（pivot）。

　　（2）所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊；所有大于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的右邊。

　?。?）對"基準(zhǔn)"左邊和右邊的兩個子集，不斷重復(fù)第一步和第二步，直到所有子集只剩下一個元素為止。

舉例來說，現(xiàn)在有一個數(shù)據(jù)集{85, 24, 63, 45, 17, 31, 96, 50}，怎么對其排序呢？

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

　　第二步，按照順序，將每個元素與"基準(zhǔn)"進(jìn)行比較，形成兩個子集，一個"小于45"，另一個"大于等于45"。

　　第三步，對兩個子集不斷重復(fù)第一步和第二步，直到所有子集只剩下一個元素為止。

按照之前的步驟，定義一個quickSort函數(shù)：

var quickSort = function(arr) { //參數(shù)是一個數(shù)組
　　if (arr.length <= 1) { return arr; } //檢查數(shù)組的元素個數(shù)，如果小于等于1，就返回。
　　var pivotIndex = Math.floor(arr.length / 2); //選擇"基準(zhǔn)"（pivot），并將其與原數(shù)組分離，再定義兩個空數(shù)組，用來存放一左一右的兩個子集。
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){ //開始遍歷數(shù)組，小于"基準(zhǔn)"的元素放入左邊的子集，大于基準(zhǔn)的元素放入右邊的子集。
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

實(shí)現(xiàn)上面動畫：

?

算法思路：

1. 從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot）;

2. 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出 之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；

3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；

實(shí)現(xiàn)代碼：

function quickSort(arr, left, right) { 
　　var len = arr.length,
　　partitionIndex,
　　left = typeof left != 'number' ? 0 : left,
　　right = typeof right != 'number' ? 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) { // 分區(qū)操作
　　var pivot = left,                // 設(shè)定基準(zhǔn)值（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;
}

?以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，更多相關(guān)內(nèi)容請關(guān)注PHP中文網(wǎng)！

相關(guān)推薦：

js數(shù)組隨機(jī)排序的方法

js將任意元素移動到指定位置

以上是JavaScript實(shí)現(xiàn)快速排序的算法思想的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！