问题描述
快速排序作为排序算法中平均花费时间最少的排序算法，在各自比赛中，经常被用来处理排序问题。
解决方案
今天来带大家理解快速排序的原理及python代码实现。快排思路：选取一个数base(方便理解选取数组第一个数)，比这个数小的移到这个数左边，比这个数大的移到这个数右边。
算法思路：
1.选取一个数作为base，并选取左右指针left和right。
2.left指针每次向右移动1，找到比base大的数.right指针每次向左移动1，找到比base小的数。然后将left指针与right指针对应的数交互位置。（这样比base小的数就移到数组左边，大的就去了右边）
图 2 步骤2
3.当left指针等于right指针，如果这个数小于base就与base交换，如果大于base就与left-1对应的数交换。
def quick_sort(array): if len(array)<2: return array else: # 选取base base=0 base_val=array[0] # 比base_val小的数组成一个数组 less_base = [i for i in array[base + 1:] if i <=base_val] # 比base_val大的数组成一个数组 more_base = [i for i in array[base + 1:] if i > base_val] # 对base_val左右两个数组执行同样操作，然后再与base+val拼接 return quick_sort(less_base)+[base_val]+quick_sort(more_base) |
测试结果：
def replace_val(array,beg,end): base=beg base_val=array[base] left=base+1 right=end while True: ''' 为了防止传入的数组只有2个元素，left=base+1直接与right重合,然后就移动下标的位置，所以先判断 ''' # 当left和right重合 if right <= left: if array[right] < base_val: array[base], array[right] = array[right], array[base] else: array[base], array[right + 1] = array[right + 1], array[base] break # left与right未重合 if array[left]>array[right]: array[left], array[right] = array[right], array[left] # 当left<right并且array[left]比base_val小就继续移动 while left<right and array[left]<=base_val: left+=1 # 当right>left并且array[right]比base_val大就继续移动 while right>=left and array[right]>base_val: right-=1 return right |
之后就是将执行了一次replace_val函数的数组拆成2部分再来一次。然后再拆，对每一部分，再执行replace_val函数。
def quilck_sort(array,beg,end): #beg<end,表示beg到end最少有2个数，才需要进行排序 if beg<end: ind=replace_val(array,beg,end) quilck_sort(array,beg,ind-1) quilck_sort(array,ind+1,end) |
测试结果：
