python写希尔、堆、快速、归并排序

1 希尔排序：

[python] view plaincopy

1. def shell_sort(seq):  
2.     gap = len(seq)/2 # 以gap为间隙，将数组分成gap组，0 到gap-1分属不同的组  
3.     #pdb.set_trace()  
4.     while gap > 0: # gap最小为1  
5.         for i in range(0, gap): # 0 到 gap-1组，分别用直接插入排序处理每组，取得每组的第一个元素i  
6.             for j in range(i+gap, len(seq), gap): # 确定这一组的若干元素，从第二个元素开始取待插入元素  
7.                 for k in range(i, j, gap): # 待插入元素与前面元素做对比，从第一个元素比起  
8.                     if seq[j] < seq[k]:  
9.                         tmp = seq[j]  
10.                         seq.pop(j)  
11.                         seq.insert(k, tmp)  
12.         gap /=2  

2 堆排序：

[python] view plaincopy

1. def heap_adjust(seq, end, mid):  # 建立大顶堆，end是尾元素下标，mid为中间位置元素  
2.     #pdb.set_trace()  
3.     for i in range(mid, -1, -1):# 堆，或者二叉树顺序存储结构的特性有：第i个元素的左右子节点为i*2+1和i*2+2，从中间位置元素开始往前，分别进行置换  
4.         if i*2+1 > end: # 没有子节点  
5.             continue  
6.         if i*2+1 == end: # 有左子结点  
7.             if seq[i] < seq[i*2+1]:  
8.                 seq[i], seq[i*2+1] = seq[i*2+1], seq[i]  
9.         else:<span style="white-space:pre"> </span># 有左右子节点，找到最小的赋予i位置  
10.             if seq[i*2+1] < seq[i*2+2]:  
11.                 seq[i*2+1],seq[i*2+2] = seq[i*2+2],seq[i*2+1]  
12.             if seq[i] < seq[i*2+1]:  
13.                 seq[i],seq[i*2+1] = seq[i*2+1], seq[i]  
14.   
15. def heap_sort(seq):<span style="white-space:pre">   </span># n个元素的大顶堆建立后，堆的首尾元素互换，n-1个元素重新建立大顶堆  
16.     for i in range(len(seq)-1, 0, -1):  
17.         mid = i/2  
18.         heap_adjust(seq, i, mid)  
19.         seq[0],seq[i] = seq[i], seq[0]  

3 快速排序：

[python] view plaincopy

1. def median(seq, start, center, end): #put median number at start，将中值放在start位置，避免快排最坏情况出现  
2.     if seq[start] > seq[end]:  
3.         seq[start], seq[end] = seq[end], seq[start]  
4.     if seq[start] > seq[center]:  
5.         seq[start], seq[center] = seq[center], seq[start]  
6.     if seq[center] > seq[end]:  
7.         seq[start], seq[end] = seq[end], seq[start]  
8.     else:  
9.         seq[start], seq[center] = seq[center], seq[start]  
10.   
11. def quik_sort(seq, start, end):  
12.     if start >= end:             #终止条件  
13.         return  
14.   
15.     mid = (start + end)/2<span style="white-space:pre"> </span>  
16.     median(seq, start, mid, end)<span style="white-space:pre">  </span># 设定中值  
17.     key = seq[start]  
18.     lp = start # 左侧游标  
19.     rp = end   # 右侧游标  
20.   
21.     while True: # 进行一轮移动，移动结果为将start位置的中值移动到某位，其左侧都小于中值，右侧都大于中值  
22.         while key < seq[rp] and rp > lp: # 从右侧游标开始比较并移动rp  
23.             rp = rp - 1  
24.         if rp > lp:  
25.             seq[lp] = seq[rp] # 将右侧游标数据放到左侧游标位置  
26.             lp = lp + 1 # 左侧游标前移，指向下一个待比较数据  
27.         while key > seq[lp] and lp < rp: # 从左侧游标开始比较并移动lp  
28.             lp = lp +1   
29.         if lp < rp:  
30.             seq[rp] = seq[lp] <span style="font-family: Arial, Helvetica, sans-serif;"># 将左侧游标数据放到右侧游标位置</span>  
31.             rp = rp -1 # 右侧游标前移，<span style="font-family: Arial, Helvetica, sans-serif;">指向下一个待比较数据</span>  
32.         if lp >= rp: # 如果lp和rp会和，则终止循环  
33.             break  
34.   
35.     seq[lp] = key # 此时的lp指向中值应该放置的位置  
36.     quik_sort(seq, start, rp-1)             # 分成两段进行分治  
37.     quik_sort(seq, rp+1, end)  

4. 归并排序

[python] view plaincopy

1. def merge_array(seq, start, mid, end):  
2.     #pdb.set_trace()  
3.     part_1 = seq[start:mid+1]  
4.     part_2 = seq[mid+1:end+1]  
5.     i = 0  
6.     j = 0  
7.     k = start  
8.     while (i < len(part_1)) and (j < len(part_2)):   
9.         if part_1[i] < part_2[j]:  
10.             seq[k] = part_1[i]  
11.             i += 1  
12.             k += 1  
13.         else:  
14.             seq[k] = part_2[j]  
15.             j += 1  
16.             k += 1  
17.   
18.     for index in range(i, len(part_1)):  
19.         seq[k] = part_1[index]  
20.         k += 1  
21.   
22.     for index in range(j, len(part_2)):  
23.         seq[k] = part_2[index]  
24.         k += 1  
25.   
26. def merge_sort(seq, start, end):  
27.     if end == start:  
28.         return  
29.     mid = (start + end)/2  
30.     merge_sort(seq, start, mid)  
31.     merge_sort(seq, mid+1, end)  
32.     merge_array(seq, start, mid, end)