Python各种排序方法汇总，python排序汇总,这是我做为学生时代初学p

Python各种排序方法汇总，python排序汇总,这是我做为学生时代初学p

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

Python各种排序方法汇总需要用到的python模块有：python time、python logging、python random

import randomimport timeimport loggingdef 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.iplaypy.comdef 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] = tempdef 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 += 1def 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 -= 12000    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 -= 1if __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)

编橙之家文章，