常用排序算法的Python实现

常用的时间复杂度为O(n^2)的排序算法有冒泡排序，插入排序和选择排序，时间复杂度为O(nlog2(n))的算法有快速排序，归并排序和堆排序，

这里的快速排序的初始比较值partition是随机给定的，在用python进行编写时能更清楚的理解整个排序算法的过程。

  1 import random
  2 def BubbleSort(num):
  3     n=len(num)
  4     for i in range(0,n):
  5         for j in range(i,n):
  6             if num[i]>=num[j]:
  7                 num[i],num[j]=num[j],num[i]
  8     return num
  9 def SelectSort(num):
 10     for i in range(0,len(num)):
 11         mindex=i
 12         for j in range(i,len(num)):
 13             if num[mindex]>num[j]:
 14                 mindex=j
 15         num[mindex],num[i]=num[i],num[mindex]
 16     return num
 17 def InsertSort(num):
 18     for i in range(1,len(num)):
 19         j=i-1
 20         tmp=num[i]
 21         while j>0 and tmp<num[j]:
 22             num[j+1]=num[j]
 23             j-=1
 24         num[j]=tmp
 25     return num
 26 def MergerSort(num):
 27     if len(num)<=1:
 28         return num
 29     left=MergerSort(num[:len(num)/2])
 30     right=MergerSort(num[len(num)/2:])
 31     result=[]
 32     while len(left)>0 and len(right)>0:
 33         if left[0]>right[0]:
 34             result.append(right.pop(0))
 35         else:
 36             result.append(left.pop(0))
 37     if len(left)>0:
 38         result.extend(MergerSort(left))
 39     else:
 40         result.extend(MergerSort(right))
 41     return result
 42 def QuickSort(num):
 43     if len(num)<=1:
 44         return num
 45     greater=[]
 46     less=[]
 47     p=num.pop(random.randint(0,len(num)-1))
 48     for item in num:
 49         if item < p:
 50             less.append(item)
 51         else:
 52             greater.append(item)
 53     return QuickSort(less)+[p]+QuickSort(greater)
 54 ############################################################
 55 def InsertIntoHeap(x,heap):
 56     if len(heap)==0:
 57         heap=[x]
 58         return heap
 59     heap.append(x)
 60     pos=len(heap)
 61     while True:
 62         if pos==1:
 63             return heap
 64         father=pos/2
 65         if heap[father-1]<heap[pos-1]:
 66             heap[father-1],heap[pos-1]=heap[pos-1],heap[father-1]
 67             pos=father
 68         else:
 69             return heap
 70 def CreateHeap(x):
 71     b=[]
 72     for i in x:
 73         InsertIntoHeap(i,b)
 74     return b 
 75 def HandHeap(a):
 76     if a==None or type(a)!=list:
 77         return 
 78     if a==[] or len(a)==1:
 79         return a 
 80     pos=0
 81     while True:
 82         if 2*(pos+1)>len(a):
 83             return a 
 84         if 2*(pos+1)==len(a):
 85             if a[pos]<a[2*pos+1]:
 86                 a[pos],a[2*pos+1]=a[2*pos+1],a[pos]
 87             return a 
 88         if 2*(pos+1)+1<=len(a):
 89             if a[pos]<a[2*pos+1]and a[2*pos+1]>=a[2*pos+2]:  
 90                 a[pos],a[2*pos+1]=a[2*pos+1],a[pos]  
 91                 pos=2*pos+1  
 92             elif a[pos]<a[2*pos+2]and a[2*pos+1]<a[2*pos+2]:  
 93                 a[pos],a[2*pos+2]=a[2*pos+2],a[pos]  
 94                 pos=2*pos+2  
 95             else:  
 96                 return a 
 97 def HeapSort(num):
 98     if num==None or type(num)!=list:
 99         return 
100     b=CreateHeap(num)
101     a=[]
102     while b:
103         a.append(b[0])
104         b[0]=b[len(b)-1]
105         b.pop()
106         b=HandHeap(b)
107     return a
108