#coding=utf-8
import random
ls = [random.randint(1,20) for i in range(30)]
def quick_sort(li):
if len(li) <=10:
li.sort()
return li
lenth = len(li)
if li[0]>li[lenth / 2]:
li[lenth / 2], li[0] = li[0], li[lenth / 2]
if li[0] > li[lenth-1]:
li[lenth-1], li[0] = li[0], li[lenth-1]
if li[lenth/2]>li[lenth-1]:
li[lenth-1], li[lenth/2] = li[lenth/2], li[lenth-1]
li[lenth/2], li[lenth-1] = li[lenth-1], li[lenth/2]
i,j = 0 ,lenth-2
while 1:
while li[i]<=li[lenth-1] and i<lenth-2:
i = i+1
while li[j] > li[lenth-1] and j >= i:
j = j-1
if i>=j:
break
else:
li[i], li[j] = li[j], li[i]
li[i+1], li[lenth-1] = li[lenth-1], li[i+1]
li = quick_sort(li[:i]) + quick_sort(li[i:])
return li
if __name__ == '__main__':
print quick_sort(ls)
我不是很喜欢可以用递归的强行用while循环来写,要换成循环就干脆换成迭代的。
英文必应搜索quick sort python给的样例:
#Quick Sort
def quicksort(arr,i,j):
if i<j:
pos=partition(arr,i,j)
quicksort(arr,i,pos-1)
quicksort(arr,pos+1,j)
def partition(arr,i,j):
pivot=arr[j]
small=i-1
for k in range(i,j):
if arr[k]<=pivot:
small+=1
swap(arr,k,small)
swap(arr,j,small+1)
print "Pivot= "+str(arr[small+1])
print arr
return small+1
def swap(arr,i,j):
temp=arr[i]
arr[i]=arr[j]
arr[j]=temp
arr=[9,4,8,3,1,2,5]
print "Initial Array :"+str(arr)
quicksort(arr,0,len(arr)-1)
二分排序,给你php版的,你用python照着改:
二分排序:
function quickSort($left,$right,$arr){
$l=$left;
$r=$right;
$pivot=$arr[($left+$right)/2];
while($l<$r){
while ($arr[$l]<$pivot) $l++;
while ($arr[$r]>$pivot) $r++;
if($l>=$r) break;
$temp=$arr[$l];
$arr[$l]=$arr[$r];
$arr[$r]=$temp;
if($arr[$l]==$pivot) --$r;
if($arr[$r]==$pivot) ++$l;
}
if($l==$r){
$l++;
$r--;
}
if($left<$r) quickSort($left,$r,$arr);
if($right>$i) quickSort($l, $right, $arr);
return $arr;
}
$arr=array(0,5,-1,20,-20,45,32,-100,-200);
$test=quickSort(0,count($arr)-1,$arr);
print_r($test);