文档章节

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

seandor
 seandor
发布于 2012/12/05 22:19
字数 636
阅读 44
收藏 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()

© 著作权归作者所有

共有 人打赏支持
上一篇: Asteroids
seandor
粉丝 0
博文 25
码字总数 22346
作品 0
巢湖
私信 提问
Python算法设计总结篇

算法设计篇主要是阅读[Python Algorithms: Mastering Basic Algorithms in the Python Language](http://link.springer.com/book/10.1007%2F978-1-4302-3238-4)[**点击链接可进入Springer下载......

宅男潇涧
2014/07/06
904
2
排序算法总结(python版)

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

dby_freedom
08/28
0
0
阿里一面 京东一面+二面 | 掘金技术征文

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

京东一面
04/18
0
0
【代码】Pythonの代码片段

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

加壹
2013/05/19
0
1
十大经典排序算法的python实现

十种常见排序算法可以分为两大类:   非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。包括:冒泡排序、选择排...

翠竹09
09/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

HashTable和Vector为什么逐渐被废弃

HashTable,不允许键值为null,还一个就是put方法使用sychronized方法进行线程同步,单线程无需同步,多线程可用concurren包的类型。 如编程思想里面说的作为工具类,封闭性做的不好没有一个...

noob_chr
昨天
0
0
Win10 下安装Win7双系统

很多人买了预装64位Win8/8.1的电脑后想重装(或者再安装一个)Win7系统,但是折腾半天发现以前的方法根本不奏效。这是因为预装Win8/8.1的电脑统一采用了UEFI+GPT引导模式,传统的BIOS(Legacy...

yaly
昨天
1
0

中国龙-扬科
昨天
1
0
假若明天来临——《AI.未来》读后感3900字

假若明天来临——《AI.未来》读后感3900字: 你有没有想过,如果有一天你被确诊为癌症患者,你会做些什么?你有没有想过,在你百年之后,你希望你的墓碑上刻写着什么内容? 在我翻开李开复老...

原创小博客
昨天
1
0
tomcat线程模型

Connector结构 BIO模式 NIO模式

grace_233
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部