采用了分治的思想
(1)在數(shù)據(jù)集之中,選擇一個(gè)元素作為"基準(zhǔn)"(pivot)。
(2)所有小于"基準(zhǔn)"的元素邻眷,都移到"基準(zhǔn)"的左邊眠屎;所有大于"基準(zhǔn)"的元素,都移到"基準(zhǔn)"的右邊肆饶。(相同的數(shù)可以到任一邊)改衩。在這個(gè)分區(qū)退出之后,該基準(zhǔn)就處于數(shù)列的中間位置驯镊。這個(gè)稱(chēng)為分區(qū)(partition)操作葫督;
(3)對(duì)"基準(zhǔn)"左邊和右邊的兩個(gè)子集,遞歸地排序 板惑。直到所有子集只剩下一個(gè)元素為止橄镜。
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1)[0];
let left = [];
let right = [];
for (let 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));
}
let array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(array));