冒泡排序(優(yōu)化)
冒泡排序的概念:冒泡排序是一種交換排序渴肉，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換爽冕，直至沒(méi)有反序的記錄為止仇祭。因?yàn)榘凑赵撍惴ǎ看伪容^會(huì)將當(dāng)前未排序的記錄序列中最小的關(guān)鍵字移至未排序的記錄序列最前（或者將當(dāng)前未排序的記錄序列中最大的關(guān)鍵字移至未排序的記錄序列最后）颈畸，就像冒泡一樣乌奇，故以此為名。
-
冒泡排序算法的算法描述如下：
- 比較相鄰的元素眯娱。如果第一個(gè)比第二個(gè)大礁苗，就交換他們兩個(gè)。
- 對(duì)每一對(duì)相鄰元素作同樣的工作徙缴，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)试伙。這步做完后，最后的元素會(huì)是最大的數(shù)于样。
- 針對(duì)所有的元素重復(fù)以上的步驟疏叨，除了最后一個(gè)。
- 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟穿剖，直到?jīng)]有任何一對(duì)數(shù)字需要比較蚤蔓。
-
冒泡排序的復(fù)雜度：
- 時(shí)間復(fù)雜度
- 最優(yōu)時(shí)間復(fù)雜度
- 平均時(shí)間復(fù)雜度
- 空間復(fù)雜度：總共
- 時(shí)間復(fù)雜度
*前面的是位置參數(shù) - 傳參時(shí)只需要參數(shù)值對(duì)號(hào)入座即可
*后面的時(shí)命名關(guān)鍵字參數(shù) - 傳參是必須書(shū)寫(xiě)為"參數(shù)名=參數(shù)值"格式
好的函數(shù)應(yīng)該是沒(méi)有副作用的(調(diào)用函數(shù)不會(huì)讓函數(shù)的調(diào)用者收到任何影響)
def bubble_sort(origin_items, comp = lambda x, y: x > y):
"""冒泡排序 - 平方復(fù)雜度 - O(N**2)"""
items = origin_items[:] # 此處優(yōu)化算法不對(duì)原始數(shù)據(jù)造成影響
for i in range(1, len(items),):
swapped = False
for j in range(0, len(items)-i):
if comp(items[j], items[j+1]): # 此處解耦比較運(yùn)算符, 擴(kuò)大函數(shù)適用范圍
items[j], items[j+1] = items[j+1], items[j]
swapped = True
# 此處優(yōu)化為雙向排序, 經(jīng)過(guò)此優(yōu)化后的冒泡排序算法又稱為攪拌排序、雞尾酒排序等
for j in range(len(items) - i, 0, -1):
if comp(items[j-1], items[j]):
items[j], items[j-1] = items[j-1], items[j]
swapped = True
if not swapped: # 如果某一輪比較全程沒(méi)有發(fā)生交換則終止循環(huán)
break
return items
歸并排序
- 歸并排序的概念:歸并排序是創(chuàng)建在歸并操作上的一種有效的排序算法携御，效率為O(n log n)昌粤。1945年由約翰·馮·諾伊曼首次提出既绕。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行涮坐。
歸并排序的算法描述如下：
- 迭代法：
- 申請(qǐng)空間凄贩，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
- 設(shè)定兩個(gè)指針袱讹，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
- 比較兩個(gè)指針?biāo)赶虻脑仄Ｔx擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
- 重復(fù)步驟3直到某一指針到達(dá)序列尾
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
- 遞歸法：
原理如下（假設(shè)序列共有n個(gè)元素）：- 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作捷雕，形成 {\displaystyle floor(n/2)} floor(n/2)個(gè)序列椒丧，排序后每個(gè)序列包含兩個(gè)元素
- 將上述序列再次歸并，形成 {\displaystyle floor(n/4)} floor(n/4)個(gè)序列救巷，每個(gè)序列包含四個(gè)元素
- 重復(fù)步驟2壶熏，直到所有元素排序完畢
- 歸并排序的復(fù)雜度:
- 時(shí)間復(fù)雜度
- 最優(yōu)時(shí)間復(fù)雜度
- 平均時(shí)間復(fù)雜度
- 空間復(fù)雜度
- 時(shí)間復(fù)雜度
def merge(items1, items2, comp):
"""有序列表合并"""
items = []
index1, index2 = 0, 0
while index1 < len(items1) and index2 < len(items2):
if comp(items[index1], items2[index2]):
items.append(items1[index1]
index1 += 1
else:
items.append(items2[index2])
index2 += 1
items += items1[index1:]
items += items2[index2:]
return items
# 函數(shù)的遞歸調(diào)用 - 一個(gè)函數(shù)如果直接或者簡(jiǎn)介的調(diào)用了自身就成為遞歸調(diào)用
# 寫(xiě)遞歸調(diào)用的函數(shù)又兩個(gè)關(guān)鍵點(diǎn):
# 1. 收斂條件 - 什么時(shí)候可以停止遞歸
# 2. 遞歸公式 - 下一輪的調(diào)用跟當(dāng)前輪次的關(guān)系
def merge_sort(items, comp=lambda x, y: x <= y):
"""歸并排序"""
if len(items) < 2:
return items[:]
mid = len(items) // 2
left = merge_sort(items[:mid])
right = merge_sort(items[mid:])
return merge(left, right, comp)
插入排序
插入排序的概念::是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列浦译，對(duì)于未排序數(shù)據(jù)棒假，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入精盅。插入排序在實(shí)現(xiàn)上帽哑，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過(guò)程中叹俏，需要反復(fù)把已排序元素逐步向后挪位妻枕，為最新元素提供插入空間。
-
插入排序的算法描述如下：
- 從第一個(gè)元素開(kāi)始粘驰，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個(gè)元素屡谐，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復(fù)步驟3晴氨，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟2~5
-
插入排序復(fù)雜度:
- 時(shí)間復(fù)雜度
- 最優(yōu)時(shí)間復(fù)雜度
- 平均時(shí)間復(fù)雜度
- 空間復(fù)雜度總共
- 時(shí)間復(fù)雜度
def insert_sort(items):
for i in range(1, len(items)):
for j in range(i):
if items[j] > items[i]:
items.insert(j, items.pop(i))
break
# 或者
def insert_sort(items):
for i in range(1, len(items)):
temp = items[i]
for j in range(i, 0, -1):
if temp < items[j-1]:
items[j] = items[j-1]
items[j-1] = temp
else:
break
快速排序
import random
# 三數(shù)取中
def get_mid(arr, left, right):
mid = left + ((left-right)>>1)
if arr[left] < arr[right]:
if arr[mid] > arr[right]:
return right
elif arr[mid] < arr[left]:
return left
else:
return mid
else:
if arr[mid] > arr[left]:
return left
elif arr[mid] < arr[right]:
return right
else:
return mid
# 挖坑法
def partition1(arr, left, right):
mid = get_mid(arr, left, right)
arr[mid], arr[right] = arr[right], arr[mid]
key = arr[right]
while left < right:
while left < right and arr[left] <= key:
left += 1
arr[right] = arr[left]
while left < right and arr[right] >= key:
right -= 1
arr[left] = arr[right]
arr[right] = key
return right
# 左右指針?lè)?def partition2(arr, left, right):
mid = get_mid(arr, left, right)
arr[mid], arr[right] = arr[right], arr[mid]
key = right
while left < right:
while left < right and arr[left] <= arr[key]:
left += 1
while left < right and arr[right] >= arr[key]:
right -= 1
arr[left],arr[right] = arr[right], arr[left]
arr[left], arr[key] = arr[key], arr[left]
return left
# 前后指針?lè)?def partition3(arr, left, right):
mid = get_mid(arr, left, right)
arr[right], arr[mid] = arr[mid], arr[right]
cur = left
pre = cur - 1
while cur < right:
if arr[cur] < arr[right]:
pre += 1
if pre != cur:
arr[pre], arr[cur] = arr[cur], arr[pre]
cur += 1
pre += 1
arr[pre], arr[right] = arr[right], arr[pre]
return pre
def quick_sort(arr, left, right):
if left >= right:
return
mid = partition1(arr, left, right)
quick_sort(arr, left, mid-1)
quick_sort(arr, mid+1, right)
def random_arr(length, min, max):
arr = []
for i in range(length):
arr.append(random.randint(min, max))
return arr
def main():
arr = random_arr(100, 0, 10000)
print(arr)
quick_sort(arr, 0, len(arr)-1)
print(arr)
if __name__ == '__main__':
main()
