Python常用排序算法

 #快排 
 1 def q_sort(l):
 2     left = 0
 3     right = len(l)-1
 4     return q(l,left,right)
 5 
 6 def quick_sort(l,left,right):
 7     if left >= right:
 8         return l
 9     low = left
10     high = right
11     while right>left:
12         while right>left and l[right] >= l[left]:
13             right -=1
14         l[right],l[left] = l[left],l[right]
15         while right>left and l[right] >= l[left]:
16             left += 1
17         l[right],l[left] = l[left],l[right]
18     q(l,low,left-1)
19     q(l,left+1,high)
20     return l

 #堆排序
 1 def heap_sort(l):
 2     n = len(l)                #  n-1 最后一个节点标号
 3     first = (n/2-1)    #最后一个非叶子节点
 4     for start in range(first,-1,-1):     
 5         max_heap(l,start,n-1)
 6 
 7     for end in range(n-1,0,-1):
 8         l[end],l[0] = l[0],l[end]
 9         max_heap(l,0,end-1)         #去除最后一个节点 标号往前重构
10     return l
11 
12 
13 def max_heap(l,start,end):
14     root = start
15     while True:
16         child = root*2 + 1
17         if child > end:break
18         if child+1 <= end and l[child] < l[child+1]:
19             child += 1
20         if l[root] < l[child] :
21             l[root],l[child] = l[child],l[root]
22             root = child
23         else:
24             break

 #堆排序取前100大
 1 def heap_sort(l):
 2     n = len(l)
 3     first = n/2-1        # 最后一个非叶子节点
 4     for start in range(first,-1,-1):
 5         min_heap(l,start,n-1)
 6 
 7     for end in range(n-1,0,-1):
 8         l[end] ,l[0] = l[0] , l[end]
 9         min_heap(l,0,end-1)
10     return l
11 
12 
13 def min_heap(l,start,end):
14     root = start
15     while 1:
16         child = root*2+1
17         if child > end :break
18         if child+1 <= end and l[child] > l[child+1]:
19             child+=1
20         if l[root] > l[child]:
21             l[root],l[child] = l[child],l[root]
22             root = child
23         else:
24             break
25 
26 def qu(x):　　　　　　　　　　#x为传入数列,z为输出前100的列表
27     z = heap_sort(x[:100])
28     print 'z:',z
29     for i in x[100:]:
30         if i > z[99]:
31             z[99]=i
32             heap_sort(z)
33     return z

 #归并排序
 1 def merge_sort(l):
 2     if len(l) <= 1:
 3         return l
 4     num = len(l)/2
 5     left = merge_sort(l[:num])
 6     right = merge_sort(l[num:])
 7     return merge(left,right)
 8 
 9 def merge(left,right):
10     i=j=0
11     r=[]
12     while i<len(left) and j<len(right):
13         if left[i] <= right[j]:
14             r.append(left[i])
15             i+=1
16         else:
17             r.append(right[j])
18             j+=1
19     r += left[i:]
20     r += right[j:]
21     return r

1 #冒泡
2 def maopao(seq):
3     for i in range(0,len(seq)-1):
4         for j in range(0,len(seq)-1-i):
5             if seq[j] > seq[j+1]:
6                 seq[j],seq[j+1]=seq[j+1],seq[j]
7     return seq    

 1 #插入
 2 def DirectInsert(seq):
 3     for i in range(1,len(seq)):
 4         temp, j = seq[i], i
 5         while j>0 and temp < seq[j-1]:
 6             seq[j] = seq[j-1]
 7             j = j-1
 8         seq[j] = temp
 9     return seq
10 
11 #插入(从中间开始)
12 def DI(seq):
13     for i in range(1,len(seq)):
14         temp, j,k = seq[i], i, i/2
15         if temp < seq[k]:
16             while k>0 and temp < seq[k-1]:
17                 seq[k] = seq[k-1]
18                 k = k-1
19             seq[k] = temp
20         else:
21             while j>0 and temp < seq[j-1]:
22                 seq[j] = seq[j-1]
23                 j = j-1
24             seq[j] = temp
25     return seq

1 #直接选择排序
2 def select_sort(l):
3     for i in range(0,len(l)):
4         min = i
5         for j in range(i+1,len(l)):
6             if l[min] > l[j]:
7                 min = j
8         l[min],l[i] = l[i],l[min]
9     return l

参考:http://www.cnblogs.com/jztan/p/5878630.html