https://www.cnblogs.com/onepixel/p/7674659.html這個文章很nicehttps://www.bilibili.com/video/av685670?from=search&seid=1637373535603658338這個動圖優秀https://www.... ...
https://www.cnblogs.com/onepixel/p/7674659.html這個文章很nice
https://www.bilibili.com/video/av685670?from=search&seid=1637373535603658338這個動圖優秀
https://www.icourse163.org/course/ZJU-93001 MOOC浙大 數據結構 陳越、何欽銘
冒泡排序、選擇排序、插入排序這三個是最慢也是最經典的三個排序演算法
快速排序對於大的亂數串列一般相信是最快的已知排序
冒泡排序 bubble sort
最簡單的排序演算法,也是效率最差的，因為它必須在最終位置知道前交換，浪費許多“交換操作”
如果列表已經排序，則是最好情況，遍歷期間無需交換，如果發現已經排序，可以提前終止，這種修改下的冒泡通常稱為短冒泡排序
時間複雜度: 平均O(n^2) 最差O(n^2) 最好O(n)
空間複雜度:O(1)
穩定
#測試輸入數組
alist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
#冒泡排序
for i in range(len(alist)-1):
for j in range(len(alist)-1-i):
if alist[j] > alist[j+1]:
alist[j],alist[j+1] = alist[j+1],alist[j]
#排序結果輸出
print('sorted:',alist)
選擇排序 selection sort
選擇排序改進了冒泡排序，每次遍歷列表只做一次交換
時間複雜度：平均O(n^2) 最差O(n^2) 最好O(n^2)
空間複雜度:O(1)
不穩定
#測試輸入數組
alist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
#選擇排序
for i in range(len(alist)-1):
least = i
for j in range(i+1,len(alist)):
if alist[j] < alist[least]:
least = j
if least != i:
alist[least],alist[i] = alist[i],alist[least]
#排序結果輸出
print('sorted:',alist)
插入排序 insertion sort
它始終在列表的較低位置維護一個排序的子列表,然後將每個新項 “插入” 回先前的子列表，使得排序的子列表成為較大的一個項
時間複雜度: 平均O(n^2) 最差O(n^2) 最好O(n)
空間複雜度:O(1)
穩定
#測試輸入數組
alist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
#插入排序
for i in range(1,len(alist)):
j = i;
while j>0 and alist[j-1]>alist[j]:
alist[j-1],alist[j] = alist[j],alist[j-1]
j -= 1
#排序結果輸出
print('sorted:',alist)
希爾排序 shell sort
是1959年Shell發明，第一個突破O(n^2)的排序，是對簡單插入排序的改進，與插入排序不同的是它優先比較距離較遠的元素，又叫“遞減增量排序”
是針對插入排序以下2特點改進：在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率；一般來說是低效的，因為插入排序每次只能將數據移動一位
希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步
gap概念，gap遞減，最後一步就是插入排序，但是此時幾乎已經排好序了
gap是希爾排序核心
出名的gap設置Marcin Ciura's gap sequence ，gaps = [701, 301, 132, 57, 23, 10, 4, 1]，不過下麵例子用數組長度不斷整除2得到的序列作為gaps
時間複雜度：平均O(n(logn)^2) 最差O(n^2) 最好O(n)
空間複雜度:O(1)
不穩定
#測試輸入數組
alist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
#希爾排序
gap = len(alist)//2
while gap>0:
#對每個gap做插入排序
for i in range(gap,len(alist)):
j = i
while j>=gap and alist[j-gap]>alist[j]:
alist[j-gap],alist[j] = alist[j],alist[j-gap]
j -= gap
gap = gap//2
#排序結果輸出
print('sorted:',alist)
歸併排序 merge sort
分而治之的策略來提高性能，是分治法的典型應用
歸併排序是一種遞歸演算法，不斷將列表拆分為一半
二路歸併 多路歸併
缺點是在合併過程需要額外存儲空間
時間複雜度: 平均O(nlogn) 最差O(nlogn) 最好O(nlogn)
空間複雜度:O(n)
穩定
#測試輸入數組
alist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
#歸併排序
def merge_sort(ilist):
def merge(left, right):
result = []
while left and right:
result.append((left if left[0] <= right[0] else right).pop(0))
return result + left + right
if len(ilist) <= 1:
return ilist
mid = len(ilist) // 2
return merge(merge_sort(ilist[:mid]), merge_sort(ilist[mid:]))
#排序結果輸出
print('sorted:',merge_sort(alist))
快速排序 quick sort
與歸併排序相同，採用分治法，而不使用額外存儲
是對冒泡排序的改進
通常明顯比其他演算法更快，因為它的內部迴圈可以在大部分的架構上很有效的達成
簡單的版本和歸併排序一樣不好，需要額外存儲空間，但是可以改為in-place版本，也就不要額外空間了
時間複雜度: 平均O(nlogn) 最差O(n^2) 最好O(nlogn)
空間複雜度:O(nlogn)
不穩定
#測試輸入數組
alist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
#快速排序
def quick_sort(ilist):
length = len(ilist)
if length <= 1:
return ilist
else:
# Use the last element as the first pivot
pivot = ilist.pop()
# Put elements greater than pivot in greater list
# Put elements lesser than pivot in lesser list
greater, lesser = [], []
for element in ilist:
if element > pivot:
greater.append(element)
else:
lesser.append(element)
return quick_sort(lesser) + [pivot] + quick_sort(greater)
#排序結果輸出
print('sorted:',quick_sort(alist))
堆排序 heap sort
是對選擇排序的一種改進
利用堆這種數據結構所設計的演算法 近似完全二叉樹
堆通常通過一維數組實 大根堆 小根堆
時間複雜度：平均O(nlogn) 最差O(nlogn) 最好O(nlogn)
空間複雜度:O(1)
不穩定
#測試輸入數組
alist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
#堆排序
def heapify(unsorted, index, heap_size):
largest = index
left_index = 2 * index + 1
right_index = 2 * index + 2
if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
largest = left_index
if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
largest = right_index
if largest != index:
unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):
n = len(unsorted)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted
#排序結果輸出
print('sorted:',heap_sort(alist))
