快速排序算法思路
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
# Filename : lean001.py # author by : www.py40.com #python快速排序算法 #算法实现步骤原理 #先从数列中取出一个数作为基准数。 #将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 #再对左右区间重复第二步,直到各区间只有一个数。 def path_sort(alist,start_index,end_index): flag = alist[end_index] i = start_index - 1 for j in range(start_index,end_index): if alist[j] < flag: i += 1 alist[i],alist[j] = alist[j],alist[i] alist[i+1],alist[end_index] = alist[end_index],alist[i+1] return i+1 def quick_sort(alist,start_index,end_index): if start_index >= end_index: return middle = path_sort(alist,start_index,end_index) quick_sort(alist,start_index,middle-1) quick_sort(alist,middle+1,end_index) print(alist) a = [1,15,12,3,56,42,1,44,32,25,6,7,32] quick_sort(a,0,len(a)-1) print("result:"+str(a)) |
运行结果
1 2 3 4 5 6 7 8 9 10 11 12 |
C:\Users\Administrator>E:\python\learn\lean001.py [1, 1, 3, 6, 7, 25, 15, 12, 32, 42, 56, 44, 32] [1, 1, 3, 6, 7, 25, 15, 12, 32, 42, 56, 44, 32] [1, 1, 3, 6, 7, 25, 15, 12, 32, 42, 56, 44, 32] [1, 1, 3, 6, 7, 12, 15, 25, 32, 42, 56, 44, 32] [1, 1, 3, 6, 7, 12, 15, 25, 32, 42, 56, 44, 32] [1, 1, 3, 6, 7, 12, 15, 25, 32, 42, 56, 44, 32] [1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56] [1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56] [1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56] [1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56] result:[1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56] |
未经允许不得转载:Python在线学习 » Python-快速排序