# 冒泡排序 defbobble_sort(data): for i inrange(len(data) - 1): data_mark = 0 mark = 0 for m inrange(1, len(data)-i): if data[data_mark] > data[m]: data[data_mark], data[m] = data[m], data[data_mark] mark = 1 data_mark = m if mark == 0: break return data
# 快速排序 deffind_mid(data, low, high): mark = data[low] while low < high: while mark <= data[high] and low < high: high -= 1 data[low] = data[high] while mark >= data[low] and low < high: low += 1 data[high] = data[low] data[low] = mark return low defQ_sort(data, low, high): if low < high: mid = find_mid(data, low, high) Q_sort(data, low, mid-1) Q_sort(data, mid+1, high)
defQuick_Sort(data): Q_sort(data, 0, len(data)-1) return data
选择排序
1 2 3 4 5 6 7 8 9 10
# 选择排序 defChoose_Sort(data): for i inrange(0, len(data)-1): mark = i for m inrange(i+1, len(data)): if data[mark] > data[m]: mark = m if mark != i: data[mark], data[i] = data[i], data[mark] return data
插入排序:
1 2 3 4 5 6 7 8 9 10 11 12 13
# 插入排序 defInsert_Sort(data): for i inrange(len(data)-1): if data[i] > data[i+1]: mark = data[i+1] data[i+1] = data[i] for m inrange(i-1, -1,-1): if data[m] > mark: data[m+1] = data[m] else: data[m+1] = mark break return data
二分插入排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# 二分插入排序 defBInsert_Sort(data): for i inrange(len(data)-1): if data[i] > data[i+1]: low = 0 high = i mark = data[i+1] while(low <= high): mid = int(high-low) if(data[mid] > mark): high = mid-1 else: low = mid+1 for m inrange(i, low-1, -1): data[m+1] = data[m] data[low] = mark return data
希尔排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
# 希尔排序 defShell_Insert(data, k): for i inrange(k, len(data)): if data[i-k] > data[i]: mark = data[i] for m inrange(i-k, 0-k-1, -k): if m >= 0and data[m] > mark: data[m+k] = data[m] else: break data[m+k] = mark
defShell_Sort(data): k = int(len(data) / 2) for i inrange(k, -4, -4): Shell_Insert(data, i) Shell_Insert(data, 1) return data
# 堆排序 defHeapAdjust(data, s, m): mark = data[s] j = 2*s whileTrue: if j > m: break if j < m and data[j] < data[j+1]: j += 1 if mark > data[j]: break data[s] = data[j] s=j j *= 2 data[s] = mark defCreatHeap(data): n = len(data)-1 m = int(n/2) for i inrange(m, 0, -1): HeapAdjust(data, i, n) defHeapSort(data): CreatHeap(data) for i inrange(len(data)-1, 0, -1): data[i], data[1] = data[1], data[i] HeapAdjust(data,1, i-1) return data
# 归并排序 defmerge(data1, data2): data3 = [] i = j = 0 while i < len(data1) and j < len(data2) : if data1[i] < data2[j]: data3.append(data1[i]) i += 1 else: data3.append(data2[j]) j += 1 if j == len(data2): for m in data1[i:]: data3.append(m) # data3.extend(data1[i:]) else: for m in data2[j:]: data3.append(m) return data3
defMsort(data): iflen(data) <= 1: return data mid = (len(data))//2 left = Msort(data[:mid]) right = Msort(data[mid:]) return merge(left,right)