文档章节

快速排序的python实现

丘名鹤
 丘名鹤
发布于 2015/01/05 23:18
字数 357
阅读 130
收藏 0

教官说:“第一个同学出列,其他人以他为中心,比他矮的站在他左边,比他高的站在他右边”

这就是快速排序第一轮排序的思路。

该同学左右又可以分为两个初始的队伍,再次执行教官说的话,这就是递归的思想。

时间复杂度:平均-----O(nlog2n)

最坏------O(n²)

空间复杂度:O(log2n)

 

下面是代码:

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# 快速排序的实现

L = [90,89,78,67,56,45,34,23,12,0]

# 这里实现第一轮排序,不妨称第一个元素为锚,
# i,j分别指向待排序序列的第一和最后一个元素,
# j与锚比较,若大于锚则左移,直到小于锚的元素停下,与i指向元素交换,i后移
# 接着,i与锚比较,若小于则右移,直到大于锚的元素停下,与j指向的元素交换,j前移
# i,j交替移动,i==j时,锚temp到达最终位置
def first_sort(numbers,i,j):
    temp = numbers[i]
    while i!=j:
        while i<j and numbers[j]>temp:
            j = j - 1
        if i<j:
            numbers[i] = numbers[j]
            i = i + 1
        while i<j and numbers[i]<temp:
            i = i + 1
        if i<j:
            numbers[j] = numbers[i]
            j = j - 1
        numbers[i] = temp
        return i
        
def quick_sort(numbers,i,j):
    if i<j:
        middle = first_sort(numbers,i,j)
        quick_sort(numbers,i,middle-1)
        quick_sort(numbers,middle+1,j)

if __name__=='__main__':
    quick_sort(L,0,len(L)-1)
    print L



© 著作权归作者所有

共有 人打赏支持
丘名鹤
粉丝 0
博文 1
码字总数 357
作品 0
朝阳
程序员
私信 提问
Python之排序算法:快速排序与冒泡排序

Python之排序算法:快速排序与冒泡排序 转载请注明源地址:http://www.cnblogs.com/funnyzpc/p/7828610.html   入坑(简称IT)这一行也有些年头了,但自老师讲课提过排序算法后几乎再也没写过...

€5è¬þxãÍ
2017/11/19
0
0
排序算法(7) -- 归并排序

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/87947485 一、前言 归并排序是建立...

dby_freedom
02/26
0
0
算法基础:五大排序算法Python实战教程

本文为 AI 研习社编译的技术博客,原标题 : A tour of the top 5 sorting algorithms with Python code 作者 | George Seif 翻译 | 邓普斯•杰弗 校对 | shunshun 整理 | 菠萝妹 原文链接:...

雷锋字幕组
01/07
0
0
【代码】Pythonの代码片段

实用方法 Pythonの清理文件及文件夹 Pythonの获取Gravatar头像地址 Pythonの获取beautifulphoto随机某图片 2) 排序算法 2.1) 比较排序 Pythonの插入排序 Pythonの合并排序 Pythonの冒泡排序 ...

加壹
2013/05/19
0
1
排序算法总结(python版)

经典排序算法总结与实现 经典排序算法在面试中占有很大的比重,也是基础,为了未雨绸缪,在寒假里整理并用Python实现了七大经典排序算法,包括冒泡排序,插入排序,选择排序,希尔排序,归并...

dby_freedom
2018/08/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【机器学习PAI实战】—— 玩转人工智能之商品价格预测

摘要: 我们经常思考机器学习,深度学习,以至于人工智能给我们带来什么?在数据相对充足,足够真实的情况下,好的学习模型可以发现事件本身的内在规则,内在联系。我们去除冗余的信息,可以...

zhaowei121
11分钟前
0
0
Spring拓展接口之FactoryBean,我们来看看其源码实现

是什么 FactoryBean的源码比较简单,大家可以细读下其注释,我做了简单的如下翻译 /** * 实现此接口的bean不能用作普通bean。此bean暴露的对象是通过getObject()创建的对象,而不是它自身...

java菜分享
15分钟前
1
0
Pod在多可用区worker节点上的高可用部署

一、 需求分析 当前kubernetes集群中的worker节点可以支持添加多可用区中的ECS,这种部署方式的目的是可以让一个应用的多个pod(至少两个)能够分布在不同的可用区,起码不能分布在同一个可用...

阿里云官方博客
21分钟前
0
0
深入理解 Hive 分区分桶 (Inceptor)

分区是hive存放数据的一种方式。将列值作为目录来存放数据,就是一个分区。这样查询时使用分区列进行过滤,只需根据列值直接扫描对应目录下的数据,不扫描其他不关心的分区,快速定位,提高查...

hblt-j
29分钟前
0
0
数据结构

什么是数据结构 1、数据 数据是描述客观世界的数字、字符以及一切能够输入到计算机中,并且能够被计算机程序处理的符号集合。简言之,数据就是计算机加工处理的原料,是信息的载体。 2、数据...

stars永恒
39分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部