用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</pre> 

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