算法 -- 快速排序

  • 快速排序一般要比其他排序算法快得多;

原理

  • 首先,随机选择一个分切元素(中间点)(一般是 数组/子数组的第一个元素 sample[low]);
  • 交换分切元素两边的元素,使得分切元素左边的元素都比它小,右边元素都比它大(这样就相当于排序了一个元素 -- 分切元素);
  • 把分切元素左右两边当成两个子数组,递归执行以上过程,递归结束,数组排序完成

代码

快速排序的代码分为两部分:切分函数 和 递归(调用切分函数的)函数

切分函数

目标

就是要使切分元素,左边的元素都小于切分元素,右边的元素都大于切分元素

切分函数
实现过程
  • 切分元素:切分元素选择数组(或子数组)的第一个元素
  • 交换:交换需要用到两个指针
    • 左指针初始时为数组的第二个元素(第一个元素是切分元素),向右移动 ,直到找到一个值大于切分元素时停下。
    • 右指针初始为数组的最后一个元素,不断向左移动,直到遇到一个比切分元素小或等于()的,停下
    • 等于切分元素按小于处理
  • 此时会有两种情况:
    • 两个指针还未相遇:交换左右指针所指元素,并继续前进
    • 两个指针已经相遇(左指针的索引 i >= 右指针的索引 j):属于已经有序的正常情况,退出指针移动操作
  • 为了避免所有元素都小于(或大于)切分元素的情况,应限制指针的索引 -- i, j 避免无限移动,导致越界
  • 最后,将 切分元素与索引 j 的元素交换(因为两指针相遇后,j 已经在中间点的左边,该元素比切分元素小)
partition 切分函数
#!/usr/bin/python3

class QuickSort:
    def exch(self, sample, i, j):
        t = sample[i]
        sample[i] = sample[j]
        sample[j] = t

    def partition(self, sample, low, high):
        # 切分元素: v
        # 左指针索引:i
        # 右指针索引:j

        v = sample[low]
        i = low + 1
        j = high

        while True:
            while sample[i] <= v:
                i += 1
                if i > high: break

            while sample[j] > v:
                j -= 1
                if j < (low + 1): break

            if i >= j:
                break
            else:
                self.exch(sample, i, j)
        self.exch(sample, low, j)
        return j
递归(调用切分函数的)函数
两个子数组

递归调用函数的作用是不断的地将根据切分元素的位置,将大数组分成两个小数组,这个切分元素的位置最后是和右指针的索引 j 交换,所以我们可以通过切分函数获得

值得注意的是:并不是新建一个子数组并传给切分函数,而是在本来的大数组上逻辑(通过索引 low , j, high)地划分子数组

代码
    def sort(self, sample, low, high):
        # j 为切分元素的位置

        if low >= high:
            return

        j = self.partition(sample, low, high)
        self.sort(sample, low, j - 1)
        self.sort(sample, j + 1, high)

测试

if __name__ == '__main__':
    import random

    def show(target, prompt=''):
        print(prompt, end='')
        for  elem in target:
            print(elem, end=' ')
        print()

    sample = input().split()
    show(sample, 'Origin: ')
    sort = QuickSort()
    random.shuffle(sample) # 为了保证切分元素(我们选数组的第一个元素作为切分元素)是随机的,我们先将数组打乱,
    sort.sort(sample, 0, len(sample) - 1)
    show(sample, 'Result: ')

/mnt/f/python $ ./quickSort.py < data.txt
Origin: D G A B E C F
Result: A B C D E F G
/mnt/f/python $
/mnt/f/python $ ./quickSort.py < bigData.txt
Origin: H M F N A P N G M G Q Y Q V P T Z Z F Z Z U Q W C D Z E X H M Z K D C B K P L E X F O I O A N F X M X U T V I M T W W A P L O L H W Y W J W H C M P K U I D P B O G R K E V G L F W N U C P T J R M Y H
Result: A A A B B C C C C D D D E E E F F F F F G G G G H H H H H I I I J J K K K K L L L L M M M M M M M N N N N O O O O P P P P P P P Q Q Q R R T T T T U U U U V V V W W W W W W W X X X X Y Y Y Z Z Z Z Z Z
/mnt/f/python $

Python 随机生成字母

In [1]: import string, random

In [2]: for i in range(5):
   ...:     print(random.choice(string.ascii_uppercase), end=' ')
   ...: else:
   ...:     print()
   ...:
L R X G W

In [3]: string.ascii_letters
Out[3]: 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

In [4]: string.ascii_uppercase
Out[4]: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

In [5]: string.ascii_lowercase
Out[5]: 'abcdefghijklmnopqrstuvwxyz'

In [6]:

Github 完整代码 -- QuickSort.py

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 220,809评论 6 513
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 94,189评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 167,290评论 0 359
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,399评论 1 294
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,425评论 6 397
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,116评论 1 308
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,710评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,629评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,155评论 1 319
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,261评论 3 339
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,399评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,068评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,758评论 3 332
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,252评论 0 23
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,381评论 1 271
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,747评论 3 375
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,402评论 2 358

推荐阅读更多精彩内容

  • 数据结构与算法——快速排序 快速排序,顾名思义,它速度很快,针对一般应用中各种不同的输入都要比其他排序算法快很多,...
    sunhaiyu阅读 3,283评论 0 3
  • 快速排序算的上目前使用最广泛的算法了,之所以它这么受欢迎,是因为它是原地排序,而且将长度为 N 的数组排序所需的时...
    ghwaphon阅读 1,611评论 2 18
  • 青峰科技19小时前快速排序算法是分治算法技术的一个实例,也称为分区交换排序。快速排序采用递归调用对元素进行排序,是...
    不二王1006阅读 670评论 0 50
  • 快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 ...
    爱吃西瓜的番茄酱阅读 615评论 0 2
  • 最近在读< >时,了解到了很多常用的排序算法,故写一篇读书笔记记录下这些排序算法的思路和实现. 冒泡排序 冒泡排序...
    SylvanasSun阅读 690评论 0 0