美文网首页
Python实现快速排序

Python实现快速排序

作者: 番茄树叶 | 来源:发表于2017-03-25 19:27 被阅读173次

简介
快速排序被评为20世纪十大算法之一,最早由图灵奖获得者Tony Hoare设计出来,很牛。。玩编程的老铁们应该掌握它。

基本思想

(摘抄自《大话数据结构》)
快速排序的基本思想是
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以带到整个序列有序的目的。

Python实现
以下给出Python实现版本,结合打印信息应该就能看明白了。

# coding=utf-8


def swap(lst, left, right):
    lst[left], lst[right] = lst[right], lst[left]


def parititon(lst, left, right):
    key = lst[left]
    while left < right:
        if left < right and key <= lst[right]:
            right = right - 1
        swap(lst, left, right)

        if left < right and lst[left] <= key:
            left = left + 1
        swap(lst, left, right)
    print 'left: {} right: {}'.format(left, right)
    print lst
    return left


def Qsort(lst, left, right):
    piviot = 0
    if left < right:
        piviot = parititon(lst, left, right)
        Qsort(lst, left, piviot - 1)
        Qsort(lst, piviot + 1, right)


def Quicksort(lst):
    Qsort(lst, 0, len(lst) - 1)

l = [1, 20, 3, 50, 40, 70, 23, 100, 23]
Quicksort(l)

Console输出:

left: 0 right: 0
[1, 20, 3, 50, 40, 70, 23, 100, 23]
left: 2 right: 2
[1, 3, 20, 50, 40, 70, 23, 100, 23]
left: 6 right: 6
[1, 3, 20, 23, 40, 23, 50, 100, 70]
left: 3 right: 3
[1, 3, 20, 23, 40, 23, 50, 100, 70]
left: 5 right: 5
[1, 3, 20, 23, 23, 40, 50, 100, 70]
left: 8 right: 8
[1, 3, 20, 23, 23, 40, 50, 70, 100]

相关文章

  • 快速排序的Python实现

    目录 快速排序的介绍 快速排序的Python实现 快速排序的介绍 快速排序(quick sort)的采用了分治的策...

  • 排序

    排序 快速排序 归并排序 计数排序 Python实现 理解 详解 稳定:如果a原本在b前面,而a=b,排序之后a仍...

  • 七大排序算法的 Python

    本文用Python实现了插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序。 1、插...

  • 八大排序算法的 Python 实现(转)

    本文用Python实现了插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序。 1、插...

  • Python实现程序员必备之排序算法汇总

    本文用Python实现了快速排序、插入排序、希尔排序、归并排序、堆排序、选择排序、冒泡排序共7种排序算法。 一、快...

  • python 排序算法

    文章概述 介绍各大常用经典的排序算法和效率,以及python实现常用算法(冒泡排序,选择排序,快速排序,插入排序)...

  • Python 实现七大排序算法

    本文用 Python 实现了插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序。 先整体看一下...

  • 快速排序算法的实现( Golang 和 Python )

    Python 中一行代码搞定快排 Python 快速排序 Golang 快速排序

  • 快速排序的Python 简单实现

    快速排序的Python 简单实现[https://www.cnblogs.com/clemente/p/11168...

  • python实现快速排序(QuickSort)

    python实现【快速排序】(QuickSort) 算法原理及介绍 快速排序的基本思想:通过选择一个关键字,一趟排...

网友评论

      本文标题:Python实现快速排序

      本文链接:https://www.haomeiwen.com/subject/idicottx.html