文档章节

python实现的几个经典的排序算法

seandor
 seandor
发布于 2012/12/05 22:19
字数 636
阅读 44
收藏 0
点赞 0
评论 0
# some complex sorting algorithm
def shell_sort(sort_list):
    ''' (list) -> None
    Sort the sort_list.
    '''
    increment = len(sort_list)
    iter_len = len(sort_list)
    while increment > 1:
        increment = increment // 3 + 1
        for i in range(increment, iter_len):
            if sort_list[i] < sort_list[i - increment]:
                sentry = sort_list[i]
                j = i - increment
                while j > -1 and sort_list[j] > sentry:
                    sort_list[j + increment] = sort_list[j]
                    j -= increment
                sort_list[j + increment] = sentry
                
def heap_adjust(sort_list, s, m):
    ''' (list, int, int) -> none
    s is the last nonterminal node. m is the last node. This is going to build
    a max heap.
    '''
    temp = sort_list[s]
    # j is the index of s's left child
    j = 2 * s + 1
    while (j <= m):
        # find the biggest one between her children
        if j < m and sort_list[j] < sort_list[j + 1]:
            j += 1
        if temp >= sort_list[j]:
            break
        sort_list[s] = sort_list[j]
        s = j
        j = 2 * j + 1
    sort_list[s] = temp

def heap_sort(sort_list):
    iter_len = len(sort_list)
    # make sort_list a max heap
    for i in range(iter_len // 2 - 1, -1, -1):
        heap_adjust(sort_list, i, iter_len - 1)

    for i in range(iter_len - 1, 0, -1):
        sort_list[0], sort_list[i] = sort_list[i], sort_list[0]
        heap_adjust(sort_list, 0, i - 1)
        
def partition(sort_list, low, high):
    ''' (list, int, int) -> int
    Sort the sort_list into two parts and return the pivot index of sort_list
    '''
    # find the midian of three
##    m = low + (high - low) // 2
##    if sort_list[low] > sort_list[high]:
##        sort_list[low], sort_list[high] = sort_list[high], sort_list[low]
##    if sort_list[m] > sort_list[high]:
##        sort_list[m], sort_list[high] = sort_list[high], sort_list[m]
##    if sort_list[m] > sort_list[low]:
##        sort_list[low], sort_list[m] = sort_list[m], sort_list[low]
        
    pivot = sort_list[low]
    while low < high:
        while low < high and sort_list[high] >= pivot:
            high -= 1
        sort_list[low] = sort_list[high]
        while low < high and sort_list[low] <= pivot:
            low += 1
        sort_list[high] = sort_list[low]
    sort_list[low] = pivot
    return low

def q_sort(sort_list, low, high):
    ''' (list, int, int) -> None
    '''
    if low < high:
        pivot = partition(sort_list, low, high)

        q_sort(sort_list, low, pivot - 1)
        q_sort(sort_list, low + 1, high)

def quick_sort(sort_list):
    q_sort(sort_list, 0, len(sort_list) - 1)

# this short code snippets excerpted from python cookbook 2nd edithion, but it doesn't work well, I am gonna make it work.
##def quick_sort_2(sort_list):
##    if len(sort_list) <= 1:
##        return sort_list
##    return quick_sort_2([lt for lt in sort_list[1:] if lt < sort_list[0]]) + sort_list[0:1] + \
##           quick_sort_2([ge for ge in sort_list[1:] if ge >= sort_list[0]])

# constants for merging sort
MAXSIZE = 1000

def m_sort(sr, tr1, s, t):
    ''' (list, list, int, int) -> None
    The main part of the merge sort
    '''
    tr2 = []
    for i in range(MAXSIZE):
        tr2.append(0)
        
    if s == t:
        tr1[s] = sr[s]
    else:
        m = (s + t) // 2
        m_sort(sr, tr2, s, m)
        m_sort(sr, tr2, m + 1, t)
        merge(tr2, tr1, s, m, t)

def merge(sr, tr, i, m, n):
    ''' (list, list, int, int) -> None
    '''
    j = m + 1
    k = i
    while i <= m and j <= n:
        if sr[i] < sr[j]:
            tr[k] = sr[i]
            i += 1
        else:
            tr[k] = sr[j]
            j += 1            
        k += 1

    if i <= m:
        for l in range(0, m - i + 1):
            tr[k + l] = sr[i + l]

    if j <= n:
        for l in range(0, n - j + 1):
            tr[k + l] = sr[j + l]
 
def merge_sort(sort_list):
    m_sort(sort_list, sort_list, 0, len(sort_list) - 1)

# easy test
##lis = [50, 10, 90, 30, 70, 40, 80, 60, 20]
##merge_sort(lis)
##print(lis)

# read 'random_num.txt' from disk 
import tkinter.filedialog
sort_filename = tkinter.filedialog.askopenfilename()
sort_file = open(sort_filename, 'r')
contents = sort_file.read()
sort_file.close()

sort_list = contents.split(' ')
for i in range(len(sort_list) - 1):
    sort_list[i] = int(sort_list[i])

sort_list.pop()
# using the sorting algorithm
shell_sort(sort_list)

# write sorted file to disk.
to_filename = tkinter.filedialog.asksaveasfilename()
sorted_file = open(to_filename, 'w')
for num in sort_list:
    sorted_file.write(str(num) + ' ')
sorted_file.close()

© 著作权归作者所有

共有 人打赏支持
seandor
粉丝 0
博文 25
码字总数 22346
作品 0
巢湖
【代码】Pythonの代码片段

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

加壹
2013/05/19
0
1
阿里一面 京东一面+二面 | 掘金技术征文

阿里一面 简单说说在学校做过最有成就感的事情(和技术相关的) 你的项目用到了数据库,谈谈对事务的理解 假设你要做一个银行app,有可能碰到多个人同时向一个账户打钱的情况,有可能碰到什么...

京东一面
04/18
0
0
笨办法学 Python · 续 练习 16:冒泡、快速和归并排序

练习 16:冒泡、快速和归并排序 原文:Exercise 16: Bubble, Quick, and Merge Sort 译者:飞龙 协议:CC BY-NC-SA 4.0 自豪地采用谷歌翻译 你现在将尝试为你的数据结构实现排序算法。对于这...

apachecn_飞龙
2017/08/07
0
0
Python 如何传递运算表达式

点击关注异步图书,置顶公众号 媒体与你分享IT好书 技术干货 职场知识 首先要说明的一下,所描述的是 Python 中的 运算表达式 的部分,不是 Python 表达式的部分。 关于什么是 Python 中的运...

异步社区
05/02
0
0
heapq取列表最大或最小值元素

在一个集合中获取最大或者最小的n个元素,这时候就可以使用heapq模块中有nlargest和nsmallest函数可以达到需求 heapq介绍: heapq模块实现了python中的堆排序,并提供了有关方法。让用Python实...

梧桐0928
06/26
0
0
读书节最该买的书,我都帮你们挑出来了

点击关注 异步图书,置顶公众号 每天与你分享 IT好书 技术干货 职场知识 过完漫长的冬天,送走了倒春寒,转眼4月也即将过半,我们有那么多的节日要过,对爱读书的真爱粉儿而言,读书节这个大...

异步社区
04/19
0
0
Python能让你上天?(附代码)

Python当然能让你上天! 没试过?别担心,我来教你。和Python里的其他东西一样,它非常简单。你只需要敲入下面这行反重力代码 这是啥? 这是个彩蛋。import antigravity将打开一个指向经典X...

技术小能手
04/24
0
0
Python才是人工智能AI的首选编程语言,你值得拥有……

在所有编程语言里,Python并不算萌新,从1991年发布第一个版本,至今已经快30年了。 最近几年,随着人工智能概念的火爆,Python迅速升温,成为众多AI从业者的首选语言。 根据数据平台 Kaggle...

M耀文
05/19
0
0
Python - 装饰器使用过程中的误区

曾灵敏 — APRIL 27, 2015 装饰器基本概念 大家都知道装饰器是一个很著名的设计模式,经常被用于AOP(面向切面编程)的场景,较为经典的有插入日志,性能测试,事务处理,, 等。 Python语言本...

OneAPM1
2015/05/08
0
1
Hacker News与Reddit的算法比较

Hacker News是Y Combinator旗下的一个新闻频道,属于digg类产品, SEOmoz曾经在2008年7月隆重推出Reddit、Stumbleupon、Del.icio.us和Hacker News算法全揭秘。由此,这些知名Web2.0网站的算法...

老枪
2011/05/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

深入理解springMVC

什么是spring MVC Spring MVC属于SpringFrameWork的后续产品,已经融合在Spring Web Flow里面。Spring 框架提供了构建 Web 应用程序的全功能 MVC 模块。使用 Spring 可插入的 MVC 架构,从而...

Java填坑之路
5分钟前
0
0
《射雕英雄传》书摘

1. 我虽是个飘泊江湖的贫家女子,可不是低三下四、不知自爱之人。你如真心爱我,须当敬我重我。我此生决无别念,就是钢刀架颈,也决意跟定了你。将来……将来如有洞房花烛之日,自然……自能...

k91191
16分钟前
0
0
解决:modal中datePicker 选中时,会触发modal的hidden.bs.modal事件

最近项目中发现了一个bug,具体表现为选中模态框上datepicker组件上的日期时,会触发模态框的关闭事件,导致数据编辑无法正常进行。网上搜索了下,解决方法如下: $('.datepicker').on('hid...

Funcy1122
19分钟前
0
0
matplotlib 绘图 常用设置

中文乱码 from pylab import mplmpl.rcParams['font.sans-serif'] = ['FangSong'] # 指定默认字体mpl.rcParams['axes.unicode_minus'] = False # 解决保存图像是负号'-'显示为方块的...

阿豪boy
35分钟前
0
0
Redis分布式锁的正确实现方式

前言 分布式锁一般有三种实现方式: 1.数据库乐观锁 2.基于Redis的分布式锁; 3.基于Zookeeper的分布式锁。本篇博客将介绍第二种方式,基于Redis实现分布式锁。虽然网上已经有各种介绍Redis...

大海201506
今天
0
0
ClassNotFoundException: javax.el.ELManager

这个是因为tomcat7中的el-api2.2,有些版本太低,建议升级tomcat到8.0,利用el-api3.0就会解决这个问题。

无语年华
今天
0
0
Jvm堆内存的划分结构和优化,垃圾回收详解(详细解答篇)

在JVM中堆空间划分如下图所示 上图中,刻画了Java程序运行时的堆空间,可以简述成如下2条 1.JVM中堆空间可以分成三个大区,新生代、老年代、永久代 2.新生代可以划分为三个区,Eden区,两个幸...

嘻哈开发者
今天
1
0
CentOS 7.4 设置系统字符编码

1.语言变量LANG在 /etc/locale 文件中。 2.可以通过/ect/profile 来修改LC_TYPE 变量的值 添加如下代码 export LC_ALL="zh_CN.GBK" export LANG="zh_CN.GBK" 到profile文件中,变量的可以修改...

qimh
今天
1
0
Kafka相关使用

安装前提,需要有jdk环境,还有zookeeper环境 zookeeper下载地址:https://www.apache.org/dyn/closer.cgi/zookeeper/ zookeeper安装参考:https://www.jianshu.com/p/f7037105db46 kafka的下......

朝如青丝暮成雪
今天
1
0
CentOS7 解决无法使用tab自动补全 tab代码提示

一、前言 对于刚刚开始学习linux的新人来说,linux的一切都显着神秘,只能惊叹于大牛在Linux上行云流水的操作。今天介绍一下在linux中自动补全的功能。 对于新人来说,在不懂得技巧的情况下,...

ziluopao
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部