选一个中间值，每次排序后中间值的左边都比中间值小，右侧都比中间值大。
直到数组长度小于2
算法1
定义数组left,right 循环一次把小于中间值的放在left，大于中间值的放在right
递归此操作，直到当前只有一个元素或空
function quickSort( arr ) {
if( arr.length <= 1 ) return arr
const left = [], right = [];
const pivot = arr[ 0 ]
for( let i = 1;i < arr.length; i++ ) {
if( arr[ i ] < pivot ) {
left.push( arr[ i ] )
} else {
right.push( arr[ i ] )
}
}
return quickSort( left ).concat( pivot, quickSort( right ) )
}
算法2
从两侧各找出一个不符合条件的元素互换位置，直到游标指向相同位置
选取第0个元素为中间值
定义两个游标i指向第一个元素，j指向最后一个元素
当i<j时 重复指行以下操作
1.第i个元素比中间值小i++
2.第j个元素比中间值大j--
3.把找到的第i个和第j个不满足条件的元素互换
4.i === j结束循环
5.当前i和j指向的元素和中间值比较，大于中间值则i--
function quickSort( arr ) {
if( arr.length <= 1 ) return arr
return quickSort( arr.slice( 0, index ) ).concat( arr[ index ], quickSort( arr.slice( index + 1, arr.length - 1 ) ) )
}
function partition( arr ) {
const pivot = arr[ 0 ]
let i = 1, j = arr.length - 1;
while( i < j ) {
while( i < j && ( arr[ i ] < pivot ) ) {
i ++
}
while( i < j && ( arr[ j ] > pivot ) ) {
j --
}
if( i < j ) {
swap( arr, i, j )
}
if( i === j ) {
if( arr[ i ] > pivot ) i--
swap( arr, 0, i )
return i
}
}
}
function swap( arr, i, j ) {
arr[ i ]= arr[ j ] + arr[ i ];
arr[ j ]= arr[ i ] - arr[ j ];
arr[ i ]= arr[ i ] - arr[ j ];
}
