python之快速排序

算法描述

快速排序是将元素按照其中一个记录分成大于该记录和小于该记录的部分，然后再对两个部分进行排序。快速排序也是分治法的经典应用。

快速排序是最常使用也是最经典得排序算法，排序平均时间复杂度是O(nlogn)，最坏情况是O(n^2)。

代码1：(quicksort.py)

def splitlist(lst): pi, lst = lst[0], lst[1:] gt = [v for v in lst if v > pi ] lt = [v for v in lst if v >> lst = [4, 2, 3, 1, 6, 7] >>> splitlist(lst) ([2, 3, 1], [4], [6, 7]) """ lst = [4, 2, 3, 1, 6, 7] lt, pi, gt = splitlist(lst) if lt == [2, 3, 1] and pi == [4] and gt == [6, 7]: print("test splitlist OK!") else: print("test splitlist Failed!")def test_quicksort(): # lst = [ 9, 4, 3, 10, 7, 13, 2] lst = [9, 4, 3, 10, 7, 13, 2] lst_copy = lst[:] sorted_list = quicksort(lst) if sorted_list == sorted(lst_copy): print("test quicksort OK!") else: print("test quicksort failed")if __name__ == "__main__": test_splitlist() test_quicksort()

在上面得代码中，我们使用了递归调用和额外空间，这样虽然会导致更多得额外空间被使用，但是代码更加易读，符合python的编码哲学。

后面两个test开头的函数属于测试用例。