用Python实现各种排序算法详解编程语言

1.冒泡排序

比较相邻的元素大小，将小的前移，大的后移，就像水中的气泡一样，最小的元素经过几次移动，会最终浮到水面上。

def bubble(list): 
    for i in range(len(list)): 
        for j in range(0,len(list)-1-i): 
            if list[j] > list[j+1]: 
                list[j],list[j+1]=list[j+1],list[j] 
if name == 'main': 
    list1 = [2,3,5,7,8,9,6,54,1,42] 
    bubble(list1) 
    print(list1)

2.插入排序

将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

def insertsort(list): 
    if list != None: 
        if len(list) == 1: 
            pass 
        else: 
            for i in range(1,len(list)):#start with second item. 
                temp = list[i] 
                for j in range(i): 
                    if list[j]>list[i]: 
                        for k in range(i,j,-1):# 
                            list[k]= list[k-1] 
                        list[j] = temp 
if name == 'main': 
    list1 = [3,2,7,5,8,9,6,54,1,42] 
    insertsort(list1) 
    print(list1)

3.快速排序

(1)这里实现第一轮排序，不妨称第一个元素为锚
(2)i，j分别指向待排序序列的第一和最后一个元素
(3)j与锚比较，若大于锚则左移，直到小于锚的元素停下，与i指向元素交换，i后移
(4)接着，i与锚比较，若小于则右移，直到大于锚的元素停下，与j指向的元素交换，j前移，
(5)i,j交替移动，i==j时，锚temp到达最终位置。

L = [90,89,78,67,56,45,34,23,12,0] 
def first_sort(numbers,i,j): 
    temp = numbers[i] 
    while i!=j: 
        while i<j and numbers[j]>temp: 
            j = j - 1 
        if i < j 
            numbers[i] = numbers[j] 
            i = i + 1 
        while i < j and numbers[i]<temp: 
            i = i + 1 
        if i <j: 
            numbers[j] = numbers[i] 
            j = j - 1 
        numbers[i] = temp 
        return i 
def quick_sort(numbers,i,j): 
    if i<j: 
        middle = first_sort(numbers,i,j) 
        quick_sort(numbers,i,middle-1) 
        quick_sort(numbers,middle+1,j) 
if name=='main': 
    quick_sort(L,0,len(L)-1) 
    print

4.选择排序

从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作。

def selectionsort(list): 
    if list != None: 
        for i in range(len(list)): 
            min = i 
            for j in range(i+1,len(list)): 
                if list[min] > list[j]: 
                    min = j 
            if min != i: 
                list[min],list[i] = list[i],list[min] 
if name == 'main': 
    list1 = [2,3,5,7,8,9,6,54,1,42] 
    selectionsort(list1) 
    print(list1)

5.希尔排序

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

test=[9,2,3,5,7] 
def ShellSort(data,flag): 
    ''' 
    data: list,to be sorted 
    flag: 0->asc,1->desc 
    return a new sorted list 
    ''' 
    retData=[] 
    #copy data to retData 
    for item in data: 
        retData.append(item) 
    #sort retData 
    count=len(retData) 
    step=count/2; 
    while step>0: 
        i=0 
        while i<count: 
            j=i+step 
            while j<count: 
                t=retData.pop(j) 
                k=j-step 
                #asc 
                if flag==0: 
                    while k>=0: 
                        if t>=retData[k]: 
                            retData.insert(k+1, t) 
                            break 
                        k=k-step 
                    if k < 0: 
                        retData.insert(0, t) 
                #desc 
                elif flag==1: 
                    while k>=0: 
                        if t<=retData[k]: 
                            retData.insert(k+1, t) 
                            break 
                        k=k-step 
                    if k<0: 
                        retData.insert(0, t) 
                j=j+step 
            i=i+1 
        step=step/2 
    return retData 
data=ShellSort(test,0) 
print 'Asc:',data 
data=ShellSort(test,1) 
print 'Desc:',data

来自：http://www.jianshu.com/p/3380ea152c44