快速排序

基本思想

通过一趟排序将序列分割为两部分,其中一部分的数据比另外一部分的所有数据都要小,然后按照同样的规则对这两个序列进行同样的操作,知道最后被分割的序列有且只有一个。
在程序中,如何实现一部分的数据比另外一部分的数据都要小,这里需要定义一个基数来作为比较,比这个基数小的分为一部分,比这个基数大的分为另外一部分。

示例

** 对序列[6 1 2 7 9 3 4 5 10 8]进行第一趟分割 **

  1. 在序列中找一个数作为基数,为了方便,一边选择最左边或最右边的数,我们这里选择最左边的6作为基数。
  2. 我们假设有一个男同学站左边的1上面,女同学站在右边的8上面。
  3. 然后女同学先往左边走(因为选择最左边的6作为基数,为了在最后一步去基数交换,所以必须先让女生走),如果走到比基数6小的位置则停下;然后男生往右边走,走到比基数6大的位置停下;然后交换位置下面的数据。(以下图片都来自于《啊哈!算法》)


    Paste_Image.png
  4. 重复第三步一次


    Paste_Image.png
  5. 重复第三步第二次


    Paste_Image.png
  6. 第一趟后的结果 [3 1 2 5 4 6 9 7 10 8],然后把基数6前面和后面的分割为两个序列进行同样的操作。最后可完成升序排序。

python实现算法

#!/usr/bin/python
# encoding: utf-8

# 快速排序
def quickSort(alist, left, right):
    # 判断结束递归
    if left >= right:
        return 0
    # base为基数
    base, i, j = alist[left], left, right
    while i < j:
        # 因为基数是最左边的数,所以要先从右边往左找
        while (alist[j] >= base and i < j):
            j -= 1
        while (alist[i] <= base and i < j):
            i += 1
        # 找到一个比基数大,一个比基数小后,交换
        alist[i], alist[j] = alist[j], alist[i]
    # 最后与基数交换
    alist[left], alist[i] = alist[i], alist[left]
    # 递归处理分割后的序列
    quickSort(alist, left, i - 1)
    quickSort(alist, i + 1, right)

elem = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
quickSort(elem, 0, len(elem) - 1)
print(elem)  #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

时间复杂度

最坏的情况为N的平方
平均时间复杂度O(nlogn)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它...
    Aroli阅读 2,116评论 0 6
  • 版本记录 前言 将数据结构和算法比作计算机的基石毫不为过,追求程序的高效是每一个软件工程师的梦想。下面就是我对算法...
    刀客传奇阅读 5,215评论 4 72
  • 版权声明:本文源自简书tianma,转载请务必注明出处:http://www.jianshu.com/p/df8a...
    tianma阅读 4,413评论 0 3
  • 有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。 假设我们现在...
    William8阅读 346评论 0 0
  • 不要悲伤!很多时候,需要遗忘,需要大脑比心灵更冷静!需要将托靠真真切切放到实处!孤绝之境,往往造人!
    轻纱若水阅读 181评论 0 0