使用Python实现直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序、归并排序、基数排序。

#! /usr/bin/env python# DataStructure Sort# InsertSortdef InsertSort(lst, end=None, beg=0, space=1):    if end is None:        end = len(lst)    for i in range(beg, end, space):        tmp = lst[i]        j = i-space        while j>=beg and tmp < lst[j]:            lst[j+space] = lst[j]            j -= space        lst[j+space] = tmp# ShellSortdef ShellSort(lst):    spaces = [5,3,1]    # 5->3->1    for space in spaces:        for i in range(space):            InsertSort(lst, len(lst), i, space)        # print lst# BubbleSortdef BubbleSort(lst):    for i in range(len(lst)-1, 0, -1):        flag = 0        for j in range(1, i+1):            if lst[j-1] > lst[j]:                tmp = lst[j-1]                lst[j-1] = lst[j]                lst[j] = tmp                flag = 1        if flag == 0:            return# QuickSortdef QuickSort(lst, l, r):    i=l    j=r    if l
     
      i and lst[j]>tmp:                j -= 1            if i
      
       << 1        # print lst    InsertSort(lst, length)# BaseSortdef BaseSort(lst):    maxnum = max(lst)    mod = 1    barrel = [[] for i in range(10)]    # [[]] * 10 not work    while mod <= maxnum:        mod *= 10        length = len(lst)        for i in range(length):            index = lst[0] % mod            index = index*10 // mod            barrel[index].append(lst.pop(0))        for i in range(10):            length = len(barrel[i])            for j in range(length):                lst.append(barrel[i].pop(0))            # print lstif __name__ == "__main__":    nums = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]    # InsertSort(nums)    # BubbleSort(nums)    # QSort(nums)    # SelectSort(nums)    # ShellSort(nums)    # MergeSort(nums)    BaseSort(nums)    print nums