快速排序

快速排序采用了分治的思想,首先选择一个元素作为主元(pivot,通常选择第一个元素),然后将剩下的元素都和该主元进行比较,小的放到主元左侧,大的放到主元右侧,这样一轮之后,主元在中间,左右两侧分别都小于或大于主元,但不一定有序,左右两侧就可以作为子问题迭代求解。

快排是基于比较的排序算法,平均时间复杂度为\(O(n\log n)\),但属于一种不稳定的算法,最坏情况会达到\(O(n^2)\)的时间复杂度。

通常快排对于n比较大的情况会比较好,对于规模比较小的问题直接用插入排序就可以了。

为了避免最坏情况,也可以主元选取的方式上做一些文章。

一般数据结构课程中的快速排序实现方式如下:

python语言的一行快排实现:

一行

def quick_sort(arr):
    if len(arr) < 2: return arr
    else: reutrn quick_sort([item for item in arr[1:] if item <= arr[0]) + \
          arr[0:1] + \
          quick_sort([item for item in arr[1:] if item > arr[0])

一行

quick_sort= lambda x: x if len(x) < 2 else quick_sort([item for item in arr[1:] if item <= arr[0]) + x[0:1] + quick_sort([item for item in arr[1:] if item > arr[0])

或者这样,参考自这篇文章

qsort = lambda arr: len(arr) > 1 and qsort(list(filter(lambda x: x <= arr[0], arr[1:]))) + arr[0:1] + qsort(list(filter(lambda x: x > arr[0], arr[1:]))) or arr

上述代码中涉及的python语法要点包括:lambda 匿名函数,一行if-else语句, 列表推导式,带有过滤的列表推导式,列表切片,函数递归定义,and和or的返回值问题等。当然这样的代码看个有趣就行。

发表评论

电子邮件地址不会被公开。 必填项已用*标注