快速排序：
快速排序采用“分而治之、各个击破”的观念，此为原地（In-place）分割版本。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为“基准”（pivot），
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
PHP 实现：
function quickSort(array $array):array
{
$count = count($array);
if($count < 2){
return $array;
}
$leftArray = $rightArray = [];
$indexValue = $array[0];
for ($i=1; $i < $count; $i++) {
if($array[$i] < $indexValue){
$leftArray[] = $array[$i];
} else {
$rightArray[] = $array[$i];
}
}
$leftArray = quickSort($leftArray);
$rightArray = quickSort($rightArray);
return array_merge($leftArray, [$indexValue], $rightArray);
}
var_export(quickSort([42323, 34, 45, 24, 45]));
Python 实现：
def quick_sort(array, l=0, r=False):
length = len(array)
left = l or 0
right = r or length - 1
if left < right:
pivot = partition(array, left, right)
quick_sort(array, left, pivot-1)
quick_sort(array, pivot + 1, right)
return array
def partition(array, left, right):
right_value = array[right]
i = left
index = left
while i < right:
if array[i] < right_value:
swap(array, i, index)
index = index + 1
i = i + 1
swap(array, right, index)
return index
def swap(array, i, j):
array[i], array[j] = array[j], array[i]
a = quick_sort([2, 12, 32, 15, 34, 1, 0, 352, 32])
print(a)
JavaScript 实现：
unction quickSort(array, l, r){
var len = array.length;
var left = l || 0;
var right = r || len - 1;
if(left < right){
pivotIndex = partition(array, left, right);
quickSort(array, left, pivotIndex - 1);
quickSort(array, pivotIndex + 1, right);
}
return array;
}
function partition(array, left, right){
const value = array[right]
var pivotIndex = left;
for(var i = left; i < right; i++){
if(array[i] < value){
swap(array, i, pivotIndex);
pivotIndex++;
}
}
swap(array, right, pivotIndex);
return pivotIndex;
}
function swap(array, i, j){
const temp = array[i]
array[i] = array[j]
array[j] = temp
}
<<------------------------------------------------------->>
function quickSort2(array){
var len = array.length
if(len < 2){
return array;
}
var left = [], right = [];
var value = array[0]
for(var i = 1; i < len; i++){
if(array[i] < value){
left.push(array[i])
} else {
right.push(array[i])
}
}
left = quickSort2(left);
right = quickSort2(right);
return left.concat([value], right)
}
console.log(quickSort([21, 23, 3, 2, 34, 3, 45, 1, 0]))
console.log(quickSort2([21, 23, 3, 2, 34, 3, 45, 1, 0]))
