玩蛇网提供最新Python编程技术信息以及Python资源下载!

Python各种排序方法汇总

python 培训

这是我做为学生时代初学python时做的各种排序方法汇总的资料,拿出来和大家分享。时过境迁,手平的不同,应用的不同,有些方法可能不适用了,大家就随便看看吧。

Python各种排序方法汇总需要用到的python模块有:python timepython loggingpython random

import random
import time
import logging

def isSorted(ml):
    for i in range(len(ml) - 1):
        if ml[i] > ml[i + 1]:
            return False
    return True
    
def swap(ml, m, n):
    t = ml[m]
    ml[m] = ml[n]
    ml[n] = t
    
def bubbleSort(ml):
    for m in range(len(ml) - 1):
        for n in range(len(ml) - m - 1):
            if ml[n] > ml[n + 1]:
                swap(ml, n, n + 1)
                
def selectSort(ml):
    for m in range(len(ml) - 1):
        minIndex = m
        for n in range(m + 1, len(ml)):
            if ml[n] < ml[minIndex]:
                minIndex = n
        if minIndex != m:
            swap(ml, minIndex, m)


def quickSort(ml, left = None, right = None):
    def partition(ml, left, right):
        counter = left
        for m in range(left, right):
            if ml[m] < ml[right]:
                swap(ml, counter, m)
                counter += 1
        swap(ml, counter, right)
        return counter
        
    if left == None or right == None:
        quickSort(ml, 0, len(ml) - 1)
    elif left < right:
        p = partition(ml, left, right)
        quickSort(ml, left, p - 1)
        quickSort(ml, p + 1, right)

#www.iplaypython.com
def insertSort(ml):
    for n in range(1, len(ml)):
        temp = ml[n]
        index = n
        while index > 0 and ml[index - 1] > temp:
            ml[index] = ml[index - 1]
            index -= 1
        ml[index] = temp

def ciuraShellSort(ml):
    '''It says this is fast, 
    but it seems it's not as fast as it's supposed to be'''
    op, n = 0, len(ml)
    incs = [2331004, 1036002, 460445, 204643, 90952, 40423, 17965, 7985, 
            3549, 1577, 701, 301, 132, 57, 23, 9, 4, 1]
    for t in range(18):
        h = incs[t]
        if h > n * 4 / 9:
            continue
        for i in range(h, n):
            temp = ml[i]
            j = i - h
            while j >= 0 and ml[j] > temp:
                ml[j + h] = ml[j]
                op += 1
                j -= h
            ml[j + h] = temp
            op += 1

def shellSort(seq):
    '''This shell sort use the nature of python'''
    inc = len(seq) // 2
    while inc:
        for i, el in enumerate(seq):
            while i >= inc and seq[i - inc] > el:
                seq[i] = seq[i - inc]
                i -= inc
            seq[i] = el
        inc = round(inc / 2.2)

def shell(data):
    '''This is tranlsated from java version from wiki, 
    not using python feature, it's a little bit slower than previous one'''
    inc = len(data) // 2
    while inc:
        for i in range(inc, len(data)):
            tmp = data[i]
            j = i
            while j >= inc and data[j - inc] > tmp:
                data[j] = data[j - inc]
                j -= inc
            data[j] = tmp
        inc = round(inc / 2.2)
        
def mergesort(n):
        """Recursively merge sort a list. Returns the sorted list."""
        def merge(front, back):
                """Merge two sorted lists together. Returns the merged list."""
                result = []
                while front and back:
                    # pick the smaller one from the front and stick it on
                    # note that list.pop(0) is a linear operation, so this gives quadratic running time...
                    result.append(front.pop(0) if front[0]<=back[0] else back.pop(0))
                # add the remaining end
                result.extend(front or back)
                return result
 
        mid = len(n) // 2
        front = n[:mid]
        back = n[mid:]
        
        if len(front) > 1:
            front = mergesort(front)
        if len(back) > 1:
            back = mergesort(back)

def HeapSort(A):
    def heapify(A):
        start = (len(A) - 2) // 2
        while start >= 0:
            siftDown(A, start, len(A) - 1)
            start -= 1

2000


    def siftDown(A, start, end):
        root = start
        while root * 2 + 1 <= end:
            child = root * 2 + 1
            if child + 1 <= end and A[child] < A[child + 1]:
                child += 1
            if child <= end and A[root] < A[child]:
                A[root], A[child] = A[child], A[root]
                root = child
            else:
                return

    heapify(A)
    end = len(A) - 1
    while end > 0:
        A[end], A[0] = A[0], A[end]
        siftDown(A, 0, end - 1)
        end -= 1

if __name__ == '__main__':
    mt = [random.randint(1, 100) for i in range(9999)]
    #print(' '.join(map(str, mt)))
    print(isSorted(mt))

    def out(visit):
        if visit != None:
            print(visit.__name__ + ':')
            l = mt[:]
            t1 = time.time()
            visit(l)
            t2 = time.time()
            #print(' '.join(map(str, l)))
            print(isSorted(l))
            print((t2 - t1) * 1000.0)
            
    out(insertSort)
    out(bubbleSort)
    out(selectSort)
    out(quickSort)
    out(ciuraShellSort)
    out(shellSort)
    out(shell)
    out(mergesort)
    out(HeapSort)

玩蛇网原创,转载请注明文章出处和来源网址:http://www.iplaypython.com/code/base/b2473.html



微信公众号搜索"玩蛇网Python之家"加关注,每日最新的Python资讯、图文视频教程可以让你一手全掌握。强烈推荐关注!

微信扫描下图可直接关注

玩蛇网Python新手QQ群,欢迎加入: ① 240764603 玩蛇网Python新手群
文章发布日期:2016-03-31 08:50 玩蛇网 www.iplaypython.com

评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)
相关文章推荐
别人正在看
特别推荐
去顶部去底部