至于快排的原理,在我之前的博客里有写,这里再简单描述一下。快排首先会选择一个种子元素key,一般取序列的第一个元素为key,然后从后往前把比key小的找出来,放在key前面,再从前往后找出比key大的,放在key的后面,直到所有子序列的长度不大于1,这样最终排序就完成了。
是最实用的排序算法,没有之一,各大语言标准库的排序函数也基本都是基于快排实现的。快排的时间复杂度为nlogn。
def fastsort(arr,left,right): if left >= right: return arr key = arr[left] low = left high = right while left < right: while left < right and arr[right] > key: right -= 1 arr[left] = arr[right] while left < right and arr[left] <= key: left += 1 arr[right] = arr [left] arr[right] = key fastsort(arr,low,left-1) fastsort(arr,right+1,high) def main(): lst = [19, -23, 15, 7, -44, 98, 72] length = len(lst)-1 fastsort(lst, 0, length) print(lst) if __name__ == "__main__": main()