经典排序——快速排序

企鹅博客
企鹅博客
企鹅博客
25193
文章
0
评论
2020年10月4日03:00:59 评论 8 views 880字阅读2分56秒

快速排序:快速排序是经典的排序算法之一,它是冒泡排序的升级版。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

首先观察每一趟排序的效果:
原始序列:[84, 17, 26, 30, 62, 83, 5, 79, 45, 85]

[45, 17, 26, 30, 62, 83, 5, 79, 84, 85]
[5, 17, 26, 30, 45, 83, 62, 79, 84, 85]
[5, 17, 26, 30, 45, 83, 62, 79, 84, 85]
[5, 17, 26, 30, 45, 83, 62, 79, 84, 85]
[5, 17, 26, 30, 45, 83, 62, 79, 84, 85]
[5, 17, 26, 30, 45, 83, 62, 79, 84, 85]
[5, 17, 26, 30, 45, 79, 62, 83, 84, 85]
[5, 17, 26, 30, 45, 62, 79, 83, 84, 85]
[5, 17, 26, 30, 45, 62, 79, 83, 84, 85]
[5, 17, 26, 30, 45, 62, 79, 83, 84, 85]

最终结果:[5, 17, 26, 30, 45, 62, 79, 83, 84, 85]

Python代码实现:

from random import randint

l = [randint(0, 100) for x in range(10)]
print l

def q_sort(l, left, right):
    if left > right:
        return
    i = left
    j = right
    flag = l[left]
    while i < j:
        while i < j and flag <= l[j]:
            j = j - 1
        l[i] = l[j]
        while i < j and flag >= l[i]:
            i = i + 1
        l[j] = l[i]
    l[i] = flag
    print l
    q_sort(l, left, i - 1)
    q_sort(l, i + 1, right)
    return l

继续阅读
Android短信应用——短信信息实时获取 Linux编程

Android短信应用——短信信息实时获取

我们知道,只需通过代码就可以读到收件箱中的短信,发件箱中的短信;但是却没办法在短信发来的瞬间获取;如果我们在短信发来的一瞬间能得到相应的信息内容,那么我们就可以依次来展开很多应用了——也就是通过短信去...
LRU缓存设计 Linux编程

LRU缓存设计

缓存的数据结构采用哈希表,key到value的映射。 网上有些资料采用记录数据的使用时刻 实现LRU策略,此处采用双向链表 实现LRU策略。LRU Least Recently Used,MRUMos...
R 语言 简单介绍 Linux编程

R 语言 简单介绍

一.统计分析软件说明  统计分析软件有:SPSS, SAS、R语言,Matlab,S-PLUS,S-Miner。 SPSS: 最简单的,都是菜单操作,不过不利于二次程序开发。 SAS: 需要...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: