python實現常見八種內排序算法

2019-11-08 01:32:08

字體：大中小

來源：轉載

供稿：網友

#!/usr/bin/python# -*- coding: UTF-8 -*-# python 實現八大內排序算法, 利用list對象的方法改變了部分過程input_list = [3, 5, 9, 8, 7, 7, 6, 2, 4, 5]# 直接插入排序def insert_sort(alist): for x in xrange(len(alist)): for y in xrange(x): if alist[x] < alist[y]: # 原本對于有序區大于它的元素需要逐個后移，我使用insert和del方法簡化操作 alist.insert(y, alist[x]) del alist[x+1] return alist# 希爾排序 d = n/2 , d2 = d1/2 , 調用前面的直接插入排序算法def shell_sort(alist): # 獲取相同間隔內的元素組成列表 def get_group(blist, index_list): return [blist[index] for index in index_list] # 將直接插入的結果映射回原列表 def map_result(blist, result_iter, index_list): for a in index_list: blist[a] = result_iter.next() return blist n = len(alist) gap = n/2 while gap > 0: for x in xrange(gap): result_list = insert_sort(get_group(alist, range(x, n, gap))) alist = map_result(alist, result_list.__iter__(), range(x, n, gap)) gap /= 2 return alist# 冒泡排序def bubble_sort(alist): n = len(alist) for x in xrange(n): for y in range(x + 1, n)[::-1]: if alist[y] < alist[y-1]: alist[y], alist[y-1] = alist[y-1], alist[y] return alist# 快速排序def quick_sort(alist, i, j): start, end = i, j if start < end: base = alist[start] while start != end: while end > start and alist[end] >= base: end -= 1 alist[start] = alist[end] while end > start and alist[start] <= base: start += 1 alist[end] = alist[start] alist[start] = base quick_sort(alist, i, start - 1) quick_sort(alist, start + 1, j) return alist# 選擇排序def select_sort(alist): count = 0 n = len(alist) while count < n: index = alist[count:].index(min(alist[count:])) + count alist[count], alist[index] = alist[index], alist[count] count += 1 return alist# 堆排序, 小根堆# 調整堆的算法def sift(alist, low, high): i, j = low, 2 * low root = alist[i] while j <= high: if j < high and alist[j] > alist[j+1]: j += 1 if root > alist[j]: alist[i], i, j = alist[j], j, 2 * j else: break alist[i] = root# 堆排序的算法def heap_sort(alist): n = len(alist) result = [] # 在0的位置插入一個元素，讓下標從1開始 alist.insert(0, -1) for x in range(1, n / 2 + 1)[::-1]: sift(alist, x, n) for y in range(2, n + 1)[::-1]: result.append(alist[1]) alist[1], alist[y] = alist[y], alist[1] sift(alist, 1, y - 1) result.append(alist[1]) return result# 歸并排序這個算法參考自http://python.jobbole.com/82270/def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return resultdef merge_sort(alist): if len(alist) < 2: return alist num = len(alist) / 2 left = merge_sort(alist[:num]) right = merge_sort(alist[num:]) return merge(left, right)# 基數排序，不想寫了# merge_sort(input_list[:])# heap_sort(input_list[:])# select_sort(input_list[:])# quick_sort(input_list[:], 0, len(input_list[:])-1)# bubble_sort(input_list[:])# PRint shell_sort(input_list[:])# insert_sort(input_list[:])

網上大部分都有，但有一些地方我按照python特點做了些變化。

其中有一個讓我很疑惑的地方，希爾排序的定義是：把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序。

我看過很多的博客，甚至包括我本科的數據結構教材，一概都是在算法中先分組，然后兩兩交換，但按照希爾排序的定義， 難道不是應該先分組，然后使用直接插入排序？，網上和教材中使用的代碼普遍是“希爾冒泡法”，我不知道是我理解問題，還是大家的以訛傳訛。

我貼出教材中的代碼，有興趣的朋友可以對照我上面的代碼，看看有什么不同，

void ShellSort(int R[], int n){ int i,j,gap; int tmp; gap = n / 2; while(gap > 0) { for(i = gap;i < n;i++) { tmp = R[i]; j = j - gap; while(j >= 0 && tmp < R[j]) { R[j + gap] = R[j]; j = j - gap; } R[j + gap] = tmp; } gap = gap / 2; }}

上一篇：運行Python程序的2種方式

下一篇：python讀取圖像時遇到的奇怪問題