快速排序实现的方法有两种，挖坑法和前后指针法
挖坑法
选一个基准数，通常是第一个，将其他数与这个基准数比较，定义游标left，right
首先从右边开始，即right开始向左移动，如果right指向的数小于基准数，就相互调换（否则继续向左移动），调换后，right游标停止，让left游标移动，是向右移动。如果left指向的数比基准数大，就与基准数调换，刚才基准数就是right指向的数。循环上述操作即可
代码如下
''' 挖坑法 ''' def Quiet_sort(alist, start, end): if start >= end: return mid_value = alist[start] left = start right = end while left < right: while alist[right] >= mid_value and left < right: right -= 1 alist[left], alist[right] = alist[right], alist[left] while alist[left] < mid_value and left < right: left += 1 alist[left], alist[right] = alist[right], alist[left] Quiet_sort(alist,start,left-1) Quiet_sort(alist,left+1,end) def main(): # li = [9, 8, 7, 6, 5, 4, 3, 2, 1] li = [56,78,4,3,42,90] # li = [54,78,36,36,79,68,0,2,9,1] Quiet_sort(li, 0, len(li)-1) print(li) if __name__ == "__main__": main()前后指针法
同样需要选择一个基准数
原理就是前后夹击，大的数放右边，小的数放左边，寻找一个位置给基准数，是的基准数坐边是小的，右边是大的
# coding:utf-8 ''' 以下代码对逆序排列的序列无用 ''' def Quiet_sort(alist, start, end): if start >= end: return #定义一个基准值 mid_value = alist[start] #定义左游标 left = start #定义右游标 right = end while left < right: #当右边边的值大于基准值时,right游标左移 while alist[right] >= mid_value and left < right: right -= 1 alist[left] = alist[right] #当左边的值小于基准值时,left游标右移 while alist[left] < mid_value and left < right: left += 1 alist[right] = alist[left] alist[left] = mid_value Quiet_sort(alist,start,left-1) Quiet_sort(alist,left+1,end) def main(): # li = [9, 8, 7, 6, 5, 4, 3, 2, 1] # li = [1, 2, 3, 4, 5, 6, 7, 8, 9] li = [54,78,36,36,79,68,0,2,9] Quiet_sort(li, 0, len(li)-1) print(li) if __name__ == "__main__": main()
