常见排序算法-快排

快速排序

算法步骤：

首先，从数列中挑出一个元素，作为基准值

然后重新排序数列，将比基准值小的元素摆放在基准前面，比基准值大的摆在基准的后面（相同的数可以到任一边）。

再递归地把小于基准值元素的子数列和大于基准值元素的子数列按照同样的方法排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。

代码：

 1 '快排中的挖坑法'
 2 def quick_sort033(array,start,end):
 3     if start >= end:
 4         return
 5     mid = array[start]
 6     left=start
 7     right=end
 8     while left<right:
 9         while left<right and array[right]>=mid:
10             right-=1
11         array[left]=array[right]
12         while left < right and array[left]<=mid:
13             left+=1
14         array[right]=array[left]
15     array[left]=mid
16     quick_sort033(array,start,left-1)
17     quick_sort033(array,left+1,end)
18 
19 "*交换指针法********************************************************"
20 
21 def quick_sort3(arr,startIndex,endIndex):# 递归结束条件：startIndex大等于endIndex的时候
22     if startIndex >= endIndex:
23         return
24     pivot = arr[startIndex]
25     left = startIndex
26     right = endIndex
27     while left != right:
28         while left < right and arr[right] > pivot:
29             right-=1
30         while left < right and arr[left] <= pivot:
31             left += 1
32         if left < right:
33             p = arr[left]
34             arr[left] = arr[right]
35             arr[right] = p
36     p = arr[left]
37     arr[left] = arr[startIndex]
38     arr[startIndex] = p
39 
40     quick_sort3(arr, startIndex, left -1)
41     quick_sort3(arr, left +1, endIndex)
42 
43 if __name__ == '__main__':
44         # array1 = [2, 1, 6, 3, 5]
45         array1 = [5, 8, 9, 17, 6, 21, 3, 1, 4]
46         quick_sort3(array1, 0, len(array1) - 1)
47         print(array1)
48 
49         # if  __name__=="__main__":
50 #     lists=[5, 8, 9, 7, 6, 2, 3, 1, 4]
51 #     print ( '排序前序列为:')
52 #     for  i  in  (lists):
53 #         print ( i,end=' ')
54 #     print  ('
排序后结果为:' )
55 #     for  i  in  (quick_sort2(lists,0,len(lists)-1)):
56 #         print (i,end=' ')