1.0 歸并排序
1.1 起源
歸并排序1945年由約翰·馮·諾伊曼首次提出良价。
該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用凳寺，且各層分治遞歸可以同時(shí)進(jìn)行。
1.2 分治法的基本思想
將原問題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。
遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解瓤荔。
1.3 歸并排序的基本思想
排序一個(gè)數(shù)組，我們先把數(shù)組從中間分成前后兩部分钥组，然后對(duì)前后兩部分分別排序输硝，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了程梦。
1.4 代碼實(shí)現(xiàn)
def merge(left,right):
'''合并和排序'''
i,j = 0,0
res = []
len_left,len_right = len(left),len(right)
while i < len_left and j < len_right:
'''逐個(gè)比較兩個(gè)列表的元素点把，小的添加進(jìn)新表大的留下繼續(xù)比較'''
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
'''最后加上未比較的元素'''
res.extend(left[i:])
res.extend(right[j:])
return res
def mergeSort(lists):
'''歸并排序入口，拆分列表'''
#遞歸退出條件判斷
length = len(lists)
if length <= 1:
return lists
#遞歸拆分
mid = length // 2
left = mergeSort(lists[:mid])
right = mergeSort(lists[mid:])
return merge(left,right)
if __name__ == "__main__":
arr = [5,4,3,6,9,2,1,7,8]
print("Before sort: ", arr)
print("After sort: ", mergeSort(arr))
1.5 排序結(jié)果
2.0 快速排序
2.1 起源
快速排序(quick sort)的采用了分治的策略屿附。由圖靈獎(jiǎng)得主C. A. R. Hoare(托尼·霍爾)在1962年提出郎逃。
2.2 快排的基本思想
時(shí)間復(fù)雜度： O(nlogn)
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小挺份，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序褒翰，整個(gè)排序過程可以遞歸進(jìn)行。
2.3 快排的基本原理
- a.在數(shù)列之中，選擇一個(gè)元素作為”基準(zhǔn)”（pivot）优训，或者叫比較值
- b.數(shù)列中所有元素都和這個(gè)基準(zhǔn)值進(jìn)行比較朵你，如果比基準(zhǔn)值小就移到基準(zhǔn)值的左邊，如果比基準(zhǔn)值大就移到基準(zhǔn)值的右邊
- c.以基準(zhǔn)值左右兩邊的子列作為新數(shù)列揣非，不斷重復(fù)第一步和第二步抡医，直到所有子集只剩下一個(gè)元素為止
2.4 代碼實(shí)現(xiàn)
def quickSort(lists):
'''快速排序?qū)崿F(xiàn)'''
if len(lists) < 2:
return lists
# 第一步：隨機(jī)選取基準(zhǔn)，這里選列表中間的數(shù)便于理解,并從源列表中移除基準(zhǔn)值
mid = lists[len(lists) // 2]
lists.remove(mid)
# 第二步：定義基準(zhǔn)值左右兩個(gè)列表
left,right = [],[]
# 第三步：循環(huán)比較
for num in lists:
# 大于基準(zhǔn)值的放到右邊
if num >= mid:
right.append(num)
else:
# 小于基準(zhǔn)值的放到左邊
left.append(num)
# 第四步：利用遞歸迭代得到結(jié)果
return quickSort(left) + [mid] + quickSort(right)
if __name__ == "__main__":
arr = [5,4,3,6,9,2,1,0,7,8]
print("Before sort: ", arr)
print("After sort: ", quickSort(arr))
2.5 排序結(jié)果
3.0 冒泡排序
3.1 冒泡的基本思想
時(shí)間復(fù)雜度： O(n^2)
“凍結(jié)”列表的長度早敬，然后進(jìn)行遍歷忌傻，把最大數(shù)推到最后，然后將“凍結(jié)”的列表長度減1搞监，重復(fù)此操作完成排序
3.2 冒泡的基本原理
從第一項(xiàng)開始水孩，將第一項(xiàng) a 和第二項(xiàng) b 比較，如果 a < b腺逛，則不動(dòng)荷愕，否則交換兩者的順序衡怀。然后將第二項(xiàng) b 和第三項(xiàng) c 比較棍矛，和前面是一樣的。重復(fù)此過程直到最后一項(xiàng)抛杨。
3.3 代碼實(shí)現(xiàn)
def bubbleSort(lists):
length = len(lists)
while length > 0:
for i in range(length-1):
if lists[i] > lists[i+1]:
lists[i],lists[i+1] = lists[i+1],lists[i]
length -= 1
return lists
if __name__ == "__main__":
arr = [5,4,3,6,9,2,1,0,7,8]
print("Before sort: ", arr)
print("After sort: ", bubbleSort(arr))
3.4 排序結(jié)果
