各個分類的代表算法
| 排序方法 | 平均情況 | 最好情況 | 最壞情況 | 輔助空間 | 穩(wěn)定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) ~ O(n) | 不穩(wěn)定 |
1. 冒泡排序
# encoding:utf8
def BubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(n - 1, i, -1):
if arr[j - 1] > arr[j]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
return arr
# 冒泡排序優(yōu)化：用Flag避免數(shù)組已經(jīng)有序的情況
def BubbleSort2(arr):
n = len(arr)
Flag = True
for i in range(n):
if not Flag:
break
Flag = False
for j in range(n - 1, i, -1):
if arr[j - 1] > arr[j]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
Flag = True
return arr
# 最優(yōu)時間復(fù)雜度 O(n^2)内贮， 最差時間復(fù)雜度 O(n)
if __name__ == "__main__":
arr = [6, 3, 2, 5, 1, 6, 3]
print(BubbleSort(arr))
2.1 快速排序
# encoding:utf8
def partition(arr, low, high):
# 用數(shù)組中的第一個記錄作為樞紐記錄
privotKey = arr[low]
# 從數(shù)組的兩端交替向中間掃描
while low < high:
while low < high and arr[high] >= privotKey:
high -= 1
# 將比樞紐小的數(shù)交換到低端
arr[low], arr[high] = arr[high], arr[low]
while low < high and arr[low] <= privotKey:
low += 1
# 將比樞紐大的數(shù)交換到高端
arr[low], arr[high] = arr[high], arr[low]
# 返回樞紐所在位置
return low
def QuickSort(arr, low, high):
if low < high:
# 算出樞紐值，將數(shù)組一分為二
privot = partition(arr, low, high)
# 對低子表遞歸排序
QuickSort(arr, low, privot - 1)
# 對高子表遞歸排序
QuickSort(arr, privot + 1, high)
# 最優(yōu)時間復(fù)雜度 O(nlogn)汞斧， 最差時間復(fù)雜度 O(n^2)
# 最優(yōu)空間復(fù)雜度 O(logn)夜郁， 最差空間復(fù)雜度 O(n)
if __name__ == "__main__":
arr = [10, 7, 8, 9, 1, 5, 2, 4, 6, 24]
QuickSort(arr, 0, len(arr) - 1)
print(arr)
2.2 快速排序優(yōu)化1
# encoding:utf8
# 優(yōu)化選取樞紐，選取的樞紐值決定交換次數(shù)粘勒，我們盡量將樞紐值取到數(shù)組的中間位置
# 選擇三數(shù)取中竞端，即取三個關(guān)鍵字先進(jìn)行排序，將中間數(shù)作為樞紐庙睡。
def partition(arr, low, high):
mid = low + (high - low) // 2
# 交換左端與右端事富，保證左端較小
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
# 交換中間與右端數(shù)據(jù)，保證中間較小
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
# 交換中間與左端數(shù)據(jù)乘陪，保證左端較小
if arr[mid] > arr[low]:
arr[mid], arr[low] = arr[low], arr[mid]
# 此時low是三個數(shù)中的中間值
pivotKey = arr[low]
while low < high:
if low < high and arr[high] >= pivotKey:
high -= 1
arr[low], arr[high] = arr[high], arr[low]
if low < high and arr[low] <= pivotKey:
low += 1
arr[low], arr[high] = arr[high], arr[low]
return low
def QuickSort(arr, low, high):
if low < high:
pivot = partition(arr, low, high)
QuickSort(arr, low, pivot - 1)
QuickSort(arr, pivot + 1, high)
arr = [10, 7, 8, 9, 1, 5, 2, 4, 6, 24]
QuickSort(arr, 0, len(arr) - 1)
print(arr)
2.2 快速排序優(yōu)化2
# encoding:utf8
# 優(yōu)化不必要的交換
def partition(arr, low, high):
# 三數(shù)交換
mid = low + (high - low) // 2
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
if arr[mid] > arr[low]:
arr[mid], arr[low] = arr[low], arr[mid]
pivotKey = arr[low]
# 設(shè)置一個哨兵元素
pre = pivotKey
while low < high:
while low < high and arr[high] >= pivotKey:
high -= 1
# 采用替換而不是交換
arr[low] = arr[high]
while low < high and arr[low] <= pivotKey:
low += 1
arr[high] = arr[low]
arr[low] = pre
return low
def QuickSort(arr, low, high):
if low < high:
pivot = partition(arr, low, high)
QuickSort(arr, low, pivot - 1)
QuickSort(arr, pivot + 1, high)
arr = [10, 7, 8, 9, 1, 5, 2, 4, 6, 2]
QuickSort(arr, 0, len(arr) - 1)
print(arr)
2.3 快速排序優(yōu)化3
# encoding:utf8
# 優(yōu)化遞歸
def partition(arr, low, high):
# 三數(shù)取中
mid = low + (high - low) // 2
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
if arr[mid] > arr[low]:
arr[mid], arr[low] = arr[low], arr[mid]
pivotKey = arr[low]
# 設(shè)置哨兵元素
pre = pivotKey
while low < high:
while low < high and arr[high] >= pivotKey:
high -= 1
arr[low] = arr[high]
while low < high and arr[low] <= pivotKey:
low += 1
arr[high] = arr[low]
arr[low] = pre
return low
def QuickSort(arr, low, high):
while low < high:
pivot = partition(arr, low, high)
# 對低子表遞歸排序
QuickSort(arr, low, pivot - 1)
# 尾遞歸
low = pivot + 1
arr = [10, 7, 8, 9, 1, 5, 2, 4, 6, 13, 4]
QuickSort(arr, 0, len(arr) - 1)
print(arr)
3. 歸并排序
# encoding:utf8
def merge(s1, s2, s):
"""將兩個列表是s1统台，s2按順序融合為一個列表s,s為原列表"""
# j和i就相當(dāng)于兩個指向的位置，i指s1啡邑，j指s2
i = j = 0
while i + j < len(s):
# j == len(s2)時說明s2走完了贱勃，或者s1沒走完并且s1中該位置是最小的
if j == len(s2) or (i < len(s1) and s1[i] < s2[j]):
s[i + j] = s1[i]
i += 1
else:
s[i + j] = s2[j]
j += 1
def MergeSort(arr):
n = len(arr)
# 剩一個或沒有直接返回，不用排序
if n <= 1:
return arr
# 拆分
mid = n // 2
left = arr[:mid]
right = arr[mid:]
# 子序列遞歸調(diào)用排序
MergeSort(left)
MergeSort(right)
# 合并
merge(left, right, arr)
# 最優(yōu)時間復(fù)雜度 O(nlogn)
# 最優(yōu)空間復(fù)雜度 O(n + logn)
if __name__ == '__main__':
s = [1, 7, 3, 5, 4, 2, 5, 3]
MergeSort(s)
print(s)
4. 歸并排序
# encoding:utf8
def merge(s1, s2, s):
"""將兩個列表是s1谤逼，s2按順序融合為一個列表s,s為原列表"""
# j和i就相當(dāng)于兩個指向的位置贵扰，i指s1，j指s2
i = j = 0
while i + j < len(s):
# j == len(s2)時說明s2走完了流部，或者s1沒走完并且s1中該位置是最小的
if j == len(s2) or (i < len(s1) and s1[i] < s2[j]):
s[i + j] = s1[i]
i += 1
else:
s[i + j] = s2[j]
j += 1
def MergeSort(arr):
n = len(arr)
# 剩一個或沒有直接返回戚绕，不用排序
if n <= 1:
return arr
# 拆分
mid = n // 2
left = arr[:mid]
right = arr[mid:]
# 子序列遞歸調(diào)用排序
MergeSort(left)
MergeSort(right)
# 合并
merge(left, right, arr)
# 最優(yōu)時間復(fù)雜度 O(nlogn)
# 最優(yōu)空間復(fù)雜度 O(n + logn)
if __name__ == '__main__':
s = [1, 7, 3, 5, 4, 2, 5, 3]
MergeSort(s)
print(s)
5. 簡單選擇排序
# encoding:utf8
def SelectSort(arr):
# 記錄每一個元素的下標(biāo)
for i in range(len(arr)):
min = i
for j in range(i + 1, len(arr)):
if arr[min] > arr[j]:
min = j
if i != min:
arr[i], arr[min] = arr[min], arr[i]
return arr
# 最優(yōu)時間復(fù)雜度 O(1)， 最差時間復(fù)雜度 O(n^2)
if __name__ == '__main__':
s = [1, 7, 3, 5, 4, 2, 5, 5]
res = SelectSort(s)
print(res)
6. 堆排序
# encoding:utf8
from collections import deque
"""
堆排序思想：
首先將待排序的數(shù)組構(gòu)造出一個大根堆
取出這個大根堆的堆頂節(jié)點(最大值)贵涵，與堆的最下最右的元素進(jìn)行交換列肢，然后把剩下的元素再構(gòu)造出一個大根堆
重復(fù)第二步，直到這個大根堆的長度為1宾茂，此時完成排序瓷马。
"""
# 交換兩個元素
def swap(l, i, j):
l[i], l[j] = l[j], l[i]
return l
def swap_param(L, i, j):
L[i], L[j] = L[j], L[i]
return L
# 調(diào)整堆
def heap_adjust(arr, start, end):
temp = arr[start]
i = start
# 沿關(guān)鍵字較大的孩子結(jié)點（2i）向下篩選
j = 2 * i
# 遍歷當(dāng)前節(jié)點的孩子結(jié)點
while j <= end:
# 如果當(dāng)前節(jié)點不是最后一個節(jié)點而且左孩子小于右孩子，記錄較大值
if j < end and arr[j] < arr[j + 1]:
j += 1 # j 為關(guān)鍵字中較大的記錄的下標(biāo)
if temp >= arr[j]:
break
else:
arr[i] = arr[j]
i = j
j = 2 * i
arr[i] = temp # 交換兩個數(shù)字
def heap_sort(arr):
"""
由于堆排序是一種完全二叉樹跨晴，數(shù)組下標(biāo)是從0開始的欧聘，二叉樹的節(jié)點從1開始，
所以這里我們引入一個輔助空間端盆，用deque追加一個輔助位
"""
l = deque(arr)
l.appendleft(0)
# 引入了一個輔助空間怀骤，這里l_len的長度-1
l_len = len(l) - 1
# first_sort_count 是有孩子的節(jié)點
first_sort_count = l_len // 2
# 從后往前將序列調(diào)整為一個大根堆
print(l)
for i in range(first_sort_count, 0, -1):
heap_adjust(l, i, l_len)
print(l)
# 從后往前將堆頂元素和堆末尾元素進(jìn)行交換费封， 然后把剩下的元素調(diào)整為一個大根堆
for i in range(l_len, 0, -1):
# 將堆頂記錄和當(dāng)前未經(jīng)排序的子序列的最后一個記錄交換
l = swap_param(l, 1, i)
# 將[1 ~ i-1]重新調(diào)整為大頂堆
heap_adjust(l, 1, i - 1)
# print(l)
return [l[i] for i in range(1, len(l))]
# 時間復(fù)雜度 O(nlogn)
if __name__ == '__main__':
s = [1, 7, 3, 5, 4, 2, 5, 9, 4, 3, 5]
res = heap_sort(s)
print(res)
7. 直接插入排序
# encoding:utf8
def insert_sort(arr):
for i in range(1, len(arr)):
# 保存當(dāng)前元素的值，依次比較選擇
key = arr[i]
# 從當(dāng)前記錄開始往前進(jìn)行比較
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j] # 記錄后移
j -= 1
arr[j + 1] = key # 插入到正確的位置
return arr
# 時間復(fù)雜度 O(n^2)
if __name__ == '__main__':
arr = [1, 7, 3, 5, 4, 2, 5, 9, 4, 3, 5]
res = insert_sort(arr)
print(res)
