快速排序的核心思想是(如下图)
1.先确定一个基准数,让后按照比较规则,如本例是升序排列,则将比基数大的放到右边,比基数小的放到左边。
2.接下来各边重复步骤1,直到全部排序完毕。
快排的Python方法
def quick_sort(li, start, end): if start >= end: return low = start high = end pivot = li[start] # 先找一个基准 while low < high: # 先从右边找比基准元素小的数 while low < high and li[high] >= pivot: high -= 1 li[low] = li[high] # high一直在向左移,直到移到某个比基准小的元素,然后low从当前位置开始 # 再从左边找比基准元素大的数 while low < high and li[low] < pivot: low += 1 li[high] = li[low] li[low] = pivot # 基准元素的位置就确定了,此时它左边的数都比它小,右边的数都比它大 quick_sort(li, start, low - 1) quick_sort(li, low + 1, end) li = [3, 2, 1, 10, 1, 6, 9, 4] quick_sort(li, 0, len(li) - 1) print(li) 另一种递归的方法
def quick_sort(alist): if len(alist) <= 1: return alist return quick_sort([i for i in alist[1:] if i < alist[0]]) + alist[0:1] + quick_sort([i for i in alist[1:] if i >= alist[0]]) ls = [22, 21, 34, 65, 12, 89, 3, 9, 66] print(quick_sort(ls)) 快拍的核心就是把待排序的数字分成了基准,左半部分,右半部分。初始基准选择位置为0的元素。 所以结果就是返回左半部分的排序结果(左半部分的元素必须比初始基准元素小) [i for i in alist[1:] if i < alist[0]] + 初始基准元素,即位置为0的元素 alist[0] + 右半部分的快排结果(右半部分的元素必须比初始基准元素大) [i for i in alist[1:] if i >= alist[0]]