前言
原理就不在這里說了,好多大神肯定比我這個初學者講的好很多,推薦去B站看視頻講解,跟著手敲代碼
為什么選這三個排序呢?
- 首先快排是必須掌握的
- 看看快排在最壞的情況下(O(n2)),且不使用輔助空間,與冒泡(O(n2))的比較
- 由于快排是不穩定的排序演算法,且平均時間復雜度為O(nlogn),那找一個時間復雜度為O(nlogn)且穩定排序演算法,那么就非歸并排序莫屬了.
一、快速排序,歸并排序,冒泡排序比較
| 演算法 | 時間復雜度 | 空間復雜度 | 穩定性 | ||
| 平均 | 最好 | 最壞 | |||
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 穩定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(1)或O(n) | 不穩定 |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩定 |
二、原始碼
- 引入庫,并生成1000個亂數,然后深拷貝若干份.
import random
from copy import deepcopy
arr0 = [random.randint(1, 100) for _ in range(1000)]
# arr0 = [_ for _ in range(1000, 0, -1)]
# print(arr0)
for i in range(1, 11):
exec(f'arr{i} = deepcopy(arr0)')
1.冒泡
def bubble_sort(arr):
for i in range(len(arr) - 1):
for j in range(len(arr) - 1 - i):
if arr[j] >= arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr2.歸并
def merge_sort(arr):
length = len(arr)
if length <= 1:
return arr
mid = length // 2
# 以下標mid為分界點,將arr的[:mid]給left,[mid:]給right
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
lp = 0
rp = 0
res = []
while lp < len(left) and rp < len(right):
if left[lp] <= right[rp]:
res.append(left[lp])
lp += 1
else:
res.append(right[rp])
rp += 1
# 這里要用extend. left,right切片后的值為一個list
res.extend(left[lp:])
res.extend(right[rp:])
return res3.快排
# 一句話快排
qs = lambda arr: arr if len(arr) <= 1 else qs([it for it in arr[1:] if it <= arr[0]]) + [arr[0]] + \
qs([it for it in arr[1:] if it > arr[0]])
# 空間復雜度O(1)的快排
def quick_sort_O1(arr, left, right):
if left >= right:
return
base = arr[left]
lp = left
rp = right
while lp < rp:
while lp < rp and arr[rp] >= base:
rp -= 1
arr[lp] = arr[rp]
while lp < rp and arr[lp] < base:
lp += 1
arr[rp] = arr[lp]
arr[lp] = base
quick_sort_O1(arr, left, lp - 1)
quick_sort_O1(arr, lp + 1, right)
return arr
# 空間復雜度O(n)的快排
def quick_sort_On(arr: list):
if len(arr) <= 1:
return arr
left = []
right = []
base = arr.pop(0)
for it in arr:
if it <= base:
left.append(it)
else:
right.append(it)
return quick_sort_On(left) + [base] + quick_sort_On(right)
# 空間復雜度O(n)的快排,引入隨機處理,嘗試規避快排的最壞風險
def quick_sort_On_random(arr: list):
if len(arr) <= 1:
return arr
left = []
right = []
base = arr.pop()
while arr:
tmp = arr.pop()
if tmp <= base:
left.append(tmp)
else:
right.append(tmp)
return quick_sort_On(left) + [base] + quick_sort_On(right)
三、創建長度為1000的list,在jupyter notebook上運行,觀察結果
1.隨機無序陣列結果
- 空間換時間的做法明顯讓快排效率提高了一個數量級~
2.反序陣列結果
將arr0重新賦值如下:
arr0 = [_ for _ in range(1000, 0, -1)] 
3.正序陣列結果
將arr0重新賦值如下:
arr0 = [_ for _ in range(1000)] 
4.內置函式--遙遙領先
**內置函式那么快,學啥快排(捂臉)...
隨機無序陣列
反序陣列
正序結果
總結
先不總結了,大致情況就如上吧.希望大家看完后給些意見和建議.
不知道有什么地方沒考慮進去,本來只是為了規避快排最壞情況的風險而實作的quick_sort_On_random,意外發現每次都是最快的???
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/234894.html
標籤：python