排序算法總結(jié)與 Py 實現(xiàn)
這篇文章主要借鑒了地址，原文是 Java 實現(xiàn)的，質(zhì)量特別棒。
算法分類：
常見排序算法一般分為兩大類：
- 比較型排序：通過比較決定元素的相對次序，由于其時間復(fù)雜度不能突破O(nlogn)，因此也稱為非線性時間比較類排序。
-
非比較排序：：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。
排序算法.png
算法復(fù)雜度
相關(guān)概念
- 穩(wěn)定：即元素的相對順序是否會發(fā)生改變，如 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面，則算法是穩(wěn)定的。有些算法由于判斷條件是
>=或<=，這個條件包含了相等的狀態(tài)，這會導(dǎo)致該元素會落在最后的位置。 - 不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后 a 可能會出現(xiàn)在 b 的后面。有些算法由于判斷條件是
>=或<=，這個條件包含了相等的狀態(tài)，這會導(dǎo)致該元素會落在最后的位置。
穩(wěn)定舉例：比如你考試成績一直和班里的另一個同學(xué)相同，那么穩(wěn)定的排序算法就是每次總排名你都在他前頭，而不是這次他排你前頭，下次你排他前頭。
- 時間復(fù)雜度：對排序數(shù)據(jù)的總的操作次數(shù)。
- 空間復(fù)雜度：是指算法在計算機(jī)
內(nèi)執(zhí)行時所需存儲空間的度量，它也是數(shù)據(jù)規(guī)模n的函數(shù)。
1、冒泡排序
冒泡排序是一種遍歷的排序算法。它重復(fù)地走過要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。每次遍歷都會把一個值放到合適的位置。
1.1 算法描述
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)；
- 針對所有的元素重復(fù)以上的步驟，除了最后一個；
- 重復(fù)步驟1~3，直到排序完成。
1.2 圖示
冒泡.png
1.3 代碼
def mao(nums):
n = len(nums)
for i in range(n):
# n個數(shù)，遍歷 n 次
for j in range(n-i-1):
# 因為每次遍歷都會放一個數(shù)到合適的位置，所以 - i，
# 又因為是在比較 nums[j] 與 nums[j+1]，j+1的操作可以幫住我們上擴(kuò)大遍歷的范圍，所以 - 1
if nums[j] > nums[j+1]:
# 注意這里是 > 號，所以不會交換相同的值，所以冒泡是穩(wěn)定的算法
nums[j], nums[j+1] = nums[j+1], nums[j]
print(nums)
return nums
2、快速排序
快速排序的基本思想：通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。
2.1 算法描述
快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：
從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot）；
重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
2.2 圖示
代碼
def quick(nums, left, right):
if left < right:
i, j = left, right
i 是左指針，j 是右指針
base = nums[i]
#使用待排序列的第一個數(shù)做作為基數(shù)
print(base)
while i < j:
while i < j and nums[j] >= base:
# j 會 pass 過所有大于等于 base 的值。注意這里也會 pass 過相等的值，這使得快速不是穩(wěn)定的算法
j -= 1
# 使 j 指針停在小于基數(shù)的位數(shù)
nums[i] = nums[j]
# 把 nums[j]的值 移到 i 的位置(讓小的數(shù)把前頭的值占了。）
while i < j and nums[i] <= base:
i += 1
# 使 j 指針停在大于基數(shù)的位數(shù)
nums[j] = nums[i]
# 把 nums[i]的值 移到 j 的位置(讓大的數(shù)把后頭的值占了。）
nums[i] = base
# 在最后 i 會停在合適的位置，（左小右大），其實每次quick都只能保證一個數(shù)字排到合適的位置。
print(i)
# 使用遞歸把剩下的數(shù)列排序了
quick(nums, left, i-1)
quick(nums, i+1, right)
return nums
