quickSort
快排 php
$arr = [3,5,33,2,8,0,444,-17,5,5];
//简单版本
function quickSort($array){
$count = count($array);
if($count <= 1){
return $array;
}
$ruler = $array[0];
$a1 = [];
$a2 = [];
for($i=1;$i<$count;$i++){
$num = $array[$i];
if($num <= $ruler){
$a1[] = $num;
}else if($num > $ruler){
$a2[] = $num;
}
}
$a1 = quickSort($a1);
$a2 = quickSort($a2);
return array_merge($a1,[$ruler],$a2);
}
print_r(quickSort($arr));
//复杂版本
function quickSort2(&$array, $start=0, $end=0){
if($start >= $end){
return $array;
}
$ruler = $array[$start];
$left = $start;
$right = $end;
while($left < $right){
while($left < $right && $array[$right] > $ruler){
$right--;
}
$array[$left] = $array[$right];
while($left < $right && $array[$left] <= $ruler){
$left++;
}
$array[$right] = $array[$left];
}
$array[$left] = $ruler;
quickSort2($array,$start,$left-1);
quickSort2($array,$left+1,$end);
}
quickSort2($arr,0,count($arr)-1);
print_r($arr);
快排 python
def quick_sort(li, start, end):
# 分治 一分为二
# start=end ,证明要处理的数据只有一个
# start>end ,证明右边没有数据
if start >= end:
return
# 定义两个游标,分别指向0和末尾位置
left = start
right = end
# 把0位置的数据,认为是中间值
mid = li[left]
while left < right:
# 让右边游标往左移动,目的是找到小于mid的值,放到left游标位置
while left < right and li[right] >= mid:
right -= 1
li[left] = li[right]
# 让左边游标往右移动,目的是找到大于mid的值,放到right游标位置
while left < right and li[left] < mid:
left += 1
li[right] = li[left]
# while结束后,把mid放到中间位置,left=right
li[left] = mid
# 递归处理左边的数据
quick_sort(li, start, left-1)
# 递归处理右边的数据
quick_sort(li, left+1, end)
if __name__ == '__main__':
l = [6,5,4,3,2,1]
# l = 3 [2,1,5,6,5,4]
# [2, 1, 5, 6, 5, 4]
quick_sort(l,0,len(l)-1)
print(l)
# 稳定性:不稳定
# 最优时间复杂度:O(nlogn)
# 最坏时间复杂度:O(n^2)