用Python实现各种排序算法

1.冒泡排序

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

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

复制代码

2.插入排序

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

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

复制代码

3.快速排序

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

1. L = [90,89,78,67,56,45,34,23,12,0]
   
2. def first_sort(numbers,i,j):
   
3.     temp = numbers[i]
   
4.     while i!=j:
   
5.         while i<j and numbers[j]>temp:
   
6.             j = j - 1
   
7.         if i < j
   
8.             numbers[i] = numbers[j]
   
9.             i = i + 1
   
10.         while i < j and numbers[i]<temp:
    
11.             i = i + 1
    
12.         if i <j:
    
13.             numbers[j] = numbers[i]
    
14.             j = j - 1
    
15.         numbers[i] = temp
    
16.         return i
    
17. def quick_sort(numbers,i,j):
    
18.     if i<j:
    
19.         middle = first_sort(numbers,i,j)
    
20.         quick_sort(numbers,i,middle-1)
    
21.         quick_sort(numbers,middle+1,j)
    
22. if name=='main':
    
23.     quick_sort(L,0,len(L)-1)
    
24.     print

复制代码

4.选择排序

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

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

复制代码

5.希尔排序

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

1. test=[9,2,3,5,7]
   
2. def ShellSort(data,flag):
   
3.     '''
   
4.     data: list,to be sorted
   
5.     flag: 0->asc,1->desc
   
6.     return a new sorted list
   
7.     '''
   
8.     retData=[]
   
9.     #copy data to retData
   
10.     for item in data:
    
11.         retData.append(item)
    
12.     #sort retData
    
13.     count=len(retData)
    
14.     step=count/2;
    
15.     while step>0:
    
16.         i=0
    
17.         while i<count:
    
18.             j=i+step
    
19.             while j<count:
    
20.                 t=retData.pop(j)
    
21.                 k=j-step
    
22.                 #asc
    
23.                 if flag==0:
    
24.                     while k>=0:
    
25.                         if t>=retData[k]:
    
26.                             retData.insert(k+1, t)
    
27.                             break
    
28.                         k=k-step
    
29.                     if k < 0:
    
30.                         retData.insert(0, t)
    
31.                 #desc
    
32.                 elif flag==1:
    
33.                     while k>=0:
    
34.                         if t<=retData[k]:
    
35.                             retData.insert(k+1, t)
    
36.                             break
    
37.                         k=k-step
    
38.                     if k<0:
    
39.                         retData.insert(0, t)
    
40.                 j=j+step
    
41.             i=i+1
    
42.         step=step/2
    
43.     return retData
    
44. data=ShellSort(test,0)
    
45. print 'Asc:',data
    
46. data=ShellSort(test,1)
    
47. print 'Desc:',data

复制代码

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