1 import time 2 start_time = time.clock() 3 4 list_ = [9, 2, 7, 4, 5, 6, 3, 8, 1] 5 6 7 """ 8 # 堆排序(通过不断的构造最大堆来选出序列的最大值放到末尾) 9 # 最大堆调整：将堆的末端子节点调整，使得子节点永远小于父节点。 10 # 建立最大堆：将堆所有数据重新排序。 11 # 堆排序：移除位在第一个数据的根节点，并做最大堆调整的递归运算。 12 import random 13 14 15 def max_heapify(heap, heapsize, root): 16 # 最大堆调整 17 left = 2 * root + 1 18 right = left + 1 19 larger = root 20 if left < heapsize and heap[larger] < heap[left]: 21 larger = left 22 if right < heapsize and heap[larger] < heap[right]: 23 larger = right 24 if larger != root: 25 heap[larger], heap[root] = heap[root], heap[larger] 26 max_heapify(heap, heapsize, larger) 27 28 29 def build_max_heap(heap): 30 # 构造一个堆，将堆中所有数据重新排序 31 heapsize = len(heap) 32 for i in range((heapsize - 2) // 2, -1, -1): 33 max_heapify(heap, heapsize, i) 34 35 36 def heapsort(heap): 37 # 将根节点去除与最后一位做对调，对前面len-1个节点继续进行对调整过程。 38 build_max_heap(heap) 39 for i in range(len(heap) - 1, -1, -1): 40 heap[0], heap[i] = heap[i], heap[0] 41 max_heapify(heap, i, 0) 42 return heap 43 44 45 if __name__ == '__main__': 46 a = [30, 50, 57, 77, 62, 78, 94, 80, 84] 47 print(a) 48 heapsort(a) 49 print(a) 50 # b = [random.randint(1, 1000) for i in range(1000)] 51 # print(b) 52 # heapsort(b) 53 # print(b) 54 # -------------------------------------------------------------- 55 56 # 归并排序 57 # 首先用分割的方法将这个序列分割成一个个已经排好序的子序列，然后 58 # 再利用归并的方法将一个个的子序列合并成排序号的序列 59 def merge(left, right): 60 result = [] 61 while left and right: 62 result.append(left.pop(0)) if left[0] < right[0] else result.append(right.pop(0)) 63 while left: 64 result.append(left.pop(0)) 65 while right: 66 result.append(right.pop(0)) 67 return result 68 69 70 def mergesort(l): 71 if len(l) < 2: 72 return l 73 mid_index = len(l) // 2 74 left = mergesort(l[:mid_index]) 75 right = mergesort(l[mid_index:]) 76 return merge(left, right) 77 78 79 print(mergesort(list_)) 80 # -------------------------------------------------------------- 81 82 # 希尔排序 将序列分割成若干子序列（由相隔某个增量的元素组成的）分别进行直接插入排序接着依次缩小增量继续进行排序，待整个序列基本有序时，再对全体元素进行插入排序。 83 def shell_sort(l): 84 n = len(l) 85 gap = n // 2 86 while gap > 0: 87 for i in range(gap, n): 88 temp = l[i] # 每个步长进行插入排序 89 j = i 90 # 插入排序 91 while j >= gap and l[j - gap] > temp: 92 l[j] = l[j - gap] 93 j -= gap 94 l[j] = temp 95 gap = gap // 2 96 return l 97 98 99 print(shell_sort(list_)) 100 # -------------------------------------------------------------- 101 102 # 插入排序 103 # 从索引1开始，一次与其左边的数相比较，若比自己大则插入并删除自己。 104 def insertsort(l): 105 len_ = len(l) 106 for i in range(1, len_): 107 for j in range(i): 108 if l[j] > l[i]: 109 l.insert(j, l[i]) 110 l.pop(i+1) 111 break 112 return l 113 114 115 print(insertsort(list_)) 116 # -------------------------------------------------------------- 117 118 # 快速排序 119 # 选定一个基数如第一个元素 120 # 将比基数小的和比基数大的元素分别放在新列表里并按顺序排列相加 121 # 递归直到新列表元素只有一个 122 def quicksort(l): 123 len_ = len(l) 124 if len_ < 2: 125 return l 126 else: 127 pivot = l[0] 128 less = [i for i in l[1:] if i <= pivot] 129 greater = [j for j in l[1:] if j > pivot] 130 print(less, greater) 131 return quicksort(less) + [pivot] + quicksort(greater) 132 133 134 print(quicksort(list_)) 135 # -------------------------------------------------------------- 136 137 # 选择排序 138 # 将第一个数与右边数的最小值相比较，若本身较大则与最小值调换位置 139 # 依次遍历即可 140 def selectsort(l): 141 len_ = len(l) 142 for i in range(len_ - 1): 143 for j in range(i+1, len_): 144 min_ = min(l[j:]) 145 min_index = l.index(min_) 146 if l[i] > min_: 147 l[i], l[min_index] = l[min_index], l[i] 148 return l 149
# 上述选择排序代码存在问题，这次复习自己重写时发现对重复数字处理不对，同时循环也有问题。以下是更改后代码：
def selectsort(l): length = len(l) for i in range(length-1): m = min(l[i+1:]) # 当前数字右边的数字列表中的最小数 j = l[i+1:].index(m) + i + 1 # m的索引，防止重复数字的干扰 if l[i] > m: l[i], l[j] = l[j], l[i] return l
150 151 print(selectsort(list_)) 152 # -------------------------------------------------------------- 153 154 # 冒泡排序 155 # 从索引0开始依次本身和右边的元素，若右边小则调换位置，来取得最大值 156 # 然后依次循环把较大的轮换到右边 157 def bubblesort(l): 158 len_ = len(l) 159 for i in range(len_ - 1): 160 for j in range(len_ - i - 1): 161 if l[j] > l[j+1]: 162 l[j], l[j+1] = l[j+1], l[j] 163 return l 164 165 166 print(bubblesort(list_)) 167 """ 168 169 end_time = time.clock() 170 print(end_time - start_time)
目前对于堆排序还不太理解，以备后续重温复习。