Python排序算法
排序是指以特定格式排列數據。 排序算法指定按特定順序排列數據的方式。 最常見的排序是數字或字典順序。
排序的重要性在於，如果數據是以分類方式存儲，數據搜索可以優化到非常高的水平。 排序也用於以更易讀的格式表示數據。 下面來看看python中實現的5種排序方式。
- 冒泡排序
- 合併排序
- 插入排序
- 希爾排序
- 選擇排序
冒泡排序
它是一種基於比較的算法，其中每對相鄰元素進行比較，如果元素不合適，元素將進行交換。
def bubblesort(list):
# Swap the elements to arrange in order
for iter_num in range(len(list)-1,0,-1):
for idx in range(iter_num):
if list[idx]>list[idx+1]:
temp = list[idx]
list[idx] = list[idx+1]
list[idx+1] = temp
list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)執行上面示例代碼，得到以下結果 -
[2, 6, 11, 19, 27, 31, 45, 121]合併排序
合併排序首先將數組分成相等的一半，然後以排序的方式組合它們。參考以下代碼實現 -
def merge_sort(unsorted_list):
if len(unsorted_list) <= 1:
return unsorted_list
# Find the middle point and devide it
middle = len(unsorted_list) // 2
left_list = unsorted_list[:middle]
right_list = unsorted_list[middle:]
left_list = merge_sort(left_list)
right_list = merge_sort(right_list)
return list(merge(left_list, right_list))
# Merge the sorted halves
def merge(left_half,right_half):
res = []
while len(left_half) != 0 and len(right_half) != 0:
if left_half[0] < right_half[0]:
res.append(left_half[0])
left_half.remove(left_half[0])
else:
res.append(right_half[0])
right_half.remove(right_half[0])
if len(left_half) == 0:
res = res + right_half
else:
res = res + left_half
return res
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(unsorted_list))執行上面示例代碼，得到以下結果 -
[11, 12, 22, 25, 34, 64, 90]插入排序
插入排序包括爲排序列表中的給定元素找到正確的位置。 所以在開始時比較前兩個元素並通過比較來對它們進行排序。 然後選取第三個元素，並在前兩個排序元素中找到它的正確位置。 通過這種方式，逐漸將更多元素添加到已排序的列表中，並將它們置於適當的位置。
參考下面代碼的實現 -
def insertion_sort(InputList):
for i in range(1, len(InputList)):
j = i-1
nxt_element = InputList[i]
# Compare the current element with next one
while (InputList[j] > nxt_element) and (j >= 0):
InputList[j+1] = InputList[j]
j=j-1
InputList[j+1] = nxt_element
list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)執行上面示例代碼，得到以下結果 -
[2, 11, 19, 27, 30, 31, 45, 121]希爾排序
希爾排序涉及排序遠離其他的元素。對給定列表的大型子列表進行排序，並繼續縮小列表的大小，直到所有元素都被排序。 下面的程序通過將其等於列表大小的一半來找到間隙，然後開始對其中的所有元素進行排序。 然後不斷重置差距，直到整個列表被排序。
def shellSort(input_list):
gap = len(input_list) / 2
while gap > 0:
for i in range(gap, len(input_list)):
temp = input_list[i]
j = i
# Sort the sub list for this gap
while j >= gap and input_list[j - gap] > temp:
input_list[j] = input_list[j - gap]
j = j-gap
input_list[j] = temp
# Reduce the gap for the next element
gap = gap/2
list = [19,2,31,45,30,11,121,27]
shellSort(list)
print(list)執行上面示例代碼，得到以下結果 -
[2, 11, 19, 27, 30, 31, 45, 121]選擇排序
在選擇排序中，首先查找給定列表中的最小值並將其移至排序列表。 然後爲未排序列表中的每個剩餘元素重複該過程。 輸入排序列表的下一個元素將與現有元素進行比較並放置在正確的位置。 所以最後所有來自未排序列表的元素都被排序。參考以下代碼實現 -
def selection_sort(input_list):
for idx in range(len(input_list)):
min_idx = idx
for j in range( idx +1, len(input_list)):
if input_list[min_idx] > input_list[j]:
min_idx = j
# Swap the minimum value with the compared value
input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]
l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)執行上面示例代碼，得到以下結果 -
[2, 11, 19, 27, 30, 31, 45, 121]