function quickSort(arr) {
if (arr.length <= 1) return ;
//取數(shù)組最接近中間的數(shù)位基準(zhǔn)，奇數(shù)與偶數(shù)取值不同，但不印象，當(dāng)然，你可以選取第一個，或者最后一個數(shù)為基準(zhǔn)，這里不作過多描述
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
//左右區(qū)間，用于存放排序后的數(shù)
var left = [];
var right = [];
console.log('基準(zhǔn)為：' + pivot + ' 時');
for (var i = 0; i < arr.length; i++) {
console.log('分區(qū)操作的第 ' + (i + 1) + ' 次循環(huán)：');
//小于基準(zhǔn)，放于左區(qū)間，大于基準(zhǔn)，放于右區(qū)間
if (arr[i] < pivot) {
left.push(arr[i]);
console.log('左邊：' + (arr[i]))
} else {
right.push(arr[i]);
console.log('右邊：' + (arr[i]))
}
}
//這里使用concat操作符，將左區(qū)間，基準(zhǔn)，右區(qū)間拼接為一個新數(shù)組
//然后遞歸1，2步驟，直至所有無序區(qū)間都 只剩下一個元素 ，遞歸結(jié)束
return quickSort(left).concat([pivot], quickSort(right));
}
var arr = [14, 3, 15, 7, 2, 76, 11];
console.log(quickSort(arr));
/*
* 基準(zhǔn)為7時，第一次分區(qū)得到左右兩個子集[ 3, 2,] 7 [14, 15, 76, 11];
* 以基準(zhǔn)為2，對左邊的子集[3,2]進行劃分區(qū)排序,得到[2] 3。左子集排序全部結(jié)束
* 以基準(zhǔn)為76，對右邊的子集進行劃分區(qū)排序,得到[14, 15, 11] 76
* 此時對上面的[14, 15, 11]以基準(zhǔn)為15再進行劃分區(qū)排序， [14, 11] 15
* 此時對上面的[14, 11]以基準(zhǔn)為11再進行劃分區(qū)排序， 11 [14]
* 所有無序區(qū)間都只剩下一個元素，遞歸結(jié)束
*
*/

function quickSort(arr) {
// 交換
function swap(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// 分區(qū)
function partition(arr, left, right) {
/**
* 開始時不知最終pivot的存放位置，可以先將pivot交換到后面去
* 這里直接定義最右邊的元素為基準(zhǔn)
*/
var pivot = arr[right];
/**
* 存放小于pivot的元素時，是緊挨著上一元素的，否則空隙里存放的可能是大于pivot的元素，
* 故聲明一個storeIndex變量，并初始化為left來依次緊挨著存放小于pivot的元素。
*/
var storeIndex = left;
for (var i = left; i < right; i++) {
if (arr[i] < pivot) {
/**
* 遍歷數(shù)組，找到小于的pivot的元素，（大于pivot的元素會跳過）
* 將循環(huán)i次時得到的元素，通過swap交換放到storeIndex處，
* 并對storeIndex遞增1，表示下一個可能要交換的位置
*/
swap(arr, storeIndex, i);
storeIndex++;
}
}
// 最后： 將pivot交換到storeIndex處，基準(zhǔn)元素放置到最終正確位置上
swap(arr, right, storeIndex);
return storeIndex;
}
function sort(arr, left, right) {
if (left > right) return;
var storeIndex = partition(arr, left, right);
sort(arr, left, storeIndex - 1);
sort(arr, storeIndex + 1, right);
}
sort(arr, 0, arr.length - 1);
return arr;
}
console.log(quickSort([8, 4, 90, 8, 34, 67, 1, 26, 17]));