使用 Python 實現(xiàn)幾種常見的排序算法

排序是非常常見的算法，今天就來分享幾種常見排序算法的 Python 實現(xiàn)

冒泡排序

冒泡排序是最為基礎的排序算法，其核心思想就是相鄰元素兩兩比較，把較大的元素放到后面，在一輪比較完成之后，最大的元素就位于最后一個位置了，就好像是氣泡，慢慢的浮出了水面一樣。

def?bubble_sort(data,?reverse=False):
????"""
????:param?data:?list?type?data
????:param?reverse:
????:return:?list?type?data
????"""
????if?not?reverse:
????????for?i?in?range(len(data)?-?1):
????????????for?j?in?range(len(data)?-?1?-i):
????????????????if?data[j]?>?data[j+1]:
????????????????????data[j],?data[j+1]?=?data[j+1],?data[j]
????????return?data
????else:
????????for?i?in?range(len(data)?-?1):
????????????for?j?in?range(len(data)?-?1?-i):
????????????????if?data[j]?1]:
????????????????????data[j],?data[j?+?1]?=?data[j?+?1],?data[j]
????????return?data

其實冒泡排序算法還是比較好理解的，只需要進行兩次循環(huán)，最外層的循環(huán)代表排序元素的個數(shù)，內(nèi)部循環(huán)則進行兩兩比較，時間復雜度為 O(n^2)。

選擇排序

選擇排序，是逐個確定元素位置的思想。同樣是 n 遍循環(huán)，第一輪時，每一個元素都與第一個元素比較，如果比第一個元素大，則與之交換，這樣一輪過后，第一個元素就是最小的了，第二輪開始每個元素與第二個位置的元素比較，如果大，則與第二位置的元素交換，以此類推，達到排序的目的

def?selection_sort(data,?reverse=False):
????"""
????:param?data:?list?type?data
????:param?reverse:
????:return:?list?type?data
????"""
????if?not?reverse:
????????for?i?in?range(len(data)-1):
????????????min_index?=?i
????????????for?j?in?range(i+1,?len(data)):
????????????????if?data[j]?????????????????????min_index?=?j
????????????data[i],?data[min_index]?=?data[min_index],?data[i]
????????return?data
????else:
????????for?i?in?range(len(data)?-?1):
????????????min_index?=?i
????????????for?j?in?range(i+1,?len(data)):
????????????????if?data[j]?>?data[min_index]:
????????????????????min_index?=?j
????????????data[i],?data[min_index]?=?data[min_index],?data[i]
????????return?data

選擇排序和冒泡排序還是很相似的，但是選擇排序會比冒泡排序少一次交換的過程，但是同樣是兩層循環(huán)，所有時間復雜度也是 O(n^2)

插入排序

插入排序的思想是把一個數(shù)據(jù)插入到一個有序序列中，從而得到一個新的序列加一的有序序列，可以通過下圖來進一步加深理解

def?insert_sort(data,?reverse=False):
????if?not?reverse:
????????for?i?in?range(1,?len(data)):
????????????key?=?data[i]
????????????j?=?i?-?1
????????????while?j?>=?0:
????????????????if?data[j]?>?key:
????????????????????data[j+1]?=?data[j]
????????????????????data[j]?=?key
????????????????j?-=?1
????????return?data
????else:
????????for?i?in?range(1,?len(data)):
????????????key?=?data[i]
????????????j?=?i?-?1
????????????while?j?>=?0:
????????????????if?data[j]?????????????????????data[j+1]?=?data[j]
????????????????????data[j]?=?key
????????????????j?-=?1
????????return?data

由于每次遍歷有序序列時，都會有序列中所有的數(shù)據(jù)做對比，故而時間復雜度為O(n^2)

快速排序

快排的思想為首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序，之后再遞歸排序兩邊的數(shù)據(jù)。

def?quick_sort(data):
????if?not?data:
????????return?data
????first?=?data[0]
????left?=?quick_sort([l?for?l?in?data[1:]?if?l?????right?=?quick_sort([r?for?r?in?data[1:]?if?r?>=?first])
????return?left?+?[first]?+?right

好了，今天的分享就到這里了。