這篇文章主要為大家展示了“python3常用排序算法有哪些”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“python3常用排序算法有哪些”這篇文章吧。
我簡單的繪制了一下排序算法的分類，藍色字體的排序算法是我們用python3實現(xiàn)的，也是比較常用的排序算法。
冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。
它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。
走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢"浮"到數(shù)列的頂端。
作為最簡單的排序算法之一，冒泡排序給我的感覺就像Abandon在單詞書里出現(xiàn)的感覺一樣，每次都在第一頁第一位，所以最熟悉。
冒泡排序還有一種優(yōu)化算法，就是立一個 flag，當在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經(jīng)有序。
但這種改進對于提升性能來說并沒有什么太大作用。
Python3冒泡排序實例代碼最快：當輸入的數(shù)據(jù)已經(jīng)是正序時（都已經(jīng)是正序了，我還要你冒泡排序有何用?。?/p>
最慢：當輸入的數(shù)據(jù)是反序時（寫一個 for 循環(huán)反序輸出數(shù)據(jù)不就行了，干嘛要用你冒泡排序呢，我是閑的嗎）
重慶分公司
重慶分公司
# 冒泡排序
def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = bubbleSort(list)
print("List sort is:", result)效果
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。
在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現(xiàn)出來。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。
快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。
Python3快速排序-交換類排序實例源碼特點：選基準、分治、遞歸
# 快速排序
def quickSort(arr, left=None, right=None):
left = 0 if not isinstance(left,(int, float)) else left
right = len(arr)-1 if not isinstance(right,(int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = quickSort(list)
print("List sort is:", result)Python3快排簡寫def quickSort2(array): return array if len(array) <= 1 else quickSort2([lt for lt in array[1:] if lt < array[0]]) + array[0:1] + quickSort2([ge for ge in array[1:] if ge >= array[0]])
效果
Python3選擇排序-選擇類排序實例源碼選擇排序是一種簡單直觀的排序算法。
無論什么數(shù)據(jù)進去都是 O(n2) 的時間復雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。
# 選擇排序
def selectionSort(arr):
for i in range(len(arr) - 1):
# 記錄最小數(shù)的索引
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i 不是最小數(shù)時，將 i 和最小數(shù)進行交換
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = selectionSort(list)
print("List sort is:", result)效果
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法。
堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
1、大頂堆（大根堆）：每個節(jié)點的值都大于或等于其子節(jié)點的值，在堆排序算法中用于升序排列；
2、小頂堆（小根堆）：每個節(jié)點的值都小于或等于其子節(jié)點的值，在堆排序算法中用于降序排列；
堆排序的平均時間復雜度為 Ο(nlogn)。
Python3堆排序-選擇類排序實例源碼# 堆排序
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = heapSort(list)
print("List sort is:", result)效果
插入排序是一種最簡單直觀的排序算法。
插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。
它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。
插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。
Python3插入排序-插入類排序實例源碼# 作者：沙振宇
# 插入排序
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = insertionSort(list)
print("List sort is:", result)效果
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。
但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
1、插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率；
2、但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；
希爾排序的基本思想是：
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄"基本有序"時，再對全體記錄進行依次直接插入排序。
Python3希爾排序-插入類排序實例源碼# 作者：沙振宇
# 希爾排序
def shellSort(arr):
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = shellSort(list)
print("List sort is:", result)效果
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。
該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
作為一種典型的分而治之思想的算法應用，歸并排序的實現(xiàn)由兩種方法：
1、自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
2、自下而上的迭代；
和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因為始終都是 O(nlogn) 的時間復雜度。代價是需要額外的內存空間
Python3歸并排序-歸并類排序實例源碼# 作者：沙振宇
# 歸并排序
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = mergeSort(list)
print("List sort is:", result)效果
計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉化為鍵存儲在額外開辟的數(shù)組空間中。
作為一種線性時間復雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
當輸入的元素是 n 個 0 到 k 之間的整數(shù)時，它的運行時間是 Θ(n + k)。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的大值與最小值的差加上1），這使得計數(shù)排序對于數(shù)據(jù)范圍很大的數(shù)組，需要大量時間和內存。例如：計數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計數(shù)排序可以用在基數(shù)排序中的算法來排序數(shù)據(jù)范圍很大的數(shù)組。
通俗地理解，例如有 10 個年齡不同的人，統(tǒng)計出有 8 個人的年齡比 A 小，那 A 的年齡就排在第 9 位,用這個方法可以得到其他每個人的位置,也就排好了序。當然，年齡有重復時需要特殊處理（保證穩(wěn)定性），這就是為什么最后要反向填充目標數(shù)組，以及將每個數(shù)字的統(tǒng)計減去 1 的原因。
Python3計數(shù)排序-分布類排序實例源碼# 作者：沙振宇
# 計數(shù)排序
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = countingSort(list,max(list))
print("List sort is:", result)效果
基數(shù)排序是一種非比較型整數(shù)排序算法。
其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
python3基數(shù)排序-分布類排序實例源碼# 作者：沙振宇
# 基數(shù)排序
def radix_sort(arr):
"""基數(shù)排序"""
i = 0 # 記錄當前正在排拿一位，最低位為1
max_num = max(arr) # 大值
j = len(str(max_num)) # 記錄大值的位數(shù)
while i < j:
bucket_list =[[] for _ in range(10)] #初始化桶數(shù)組
for x in arr:
bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶數(shù)組
arr.clear()
for x in bucket_list: # 放回原序列
for y in x:
arr.append(y)
i += 1
return arr
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = radix_sort(list)
print("List sort is:", result)效果
桶排序是計數(shù)排序的升級版。
它利用了函數(shù)的映射關系，高效與否的關鍵就在于這個映射函數(shù)的確定。為了使桶排序更加高效，我們需要做到這兩點：
1、在額外空間充足的情況下，盡量增大桶的數(shù)量
2、使用的映射函數(shù)能夠將輸入的 N 個數(shù)據(jù)均勻的分配到 K 個桶中
同時，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關重要。
最快：當輸入的數(shù)據(jù)可以均勻的分配到每一個桶中。
最慢：當輸入的數(shù)據(jù)被分配到了同一個桶中。
Python3桶排序-分布類排序實例源碼# 作者：沙振宇
# 桶排序
def bucketSort(arr):
# 選擇一個大的數(shù)
max_num = max(arr)
# 創(chuàng)建一個元素全是0的列表, 當做桶
bucket = [0] * (max_num + 1)
# 把所有元素放入桶中, 即把對應元素個數(shù)加一
for i in arr:
bucket[i] += 1
# 存儲排序好的元素
sort_nums = []
# 取出桶中的元素
for j in range(len(bucket)):
if bucket[j] != 0:
for y in range(bucket[j]):
sort_nums.append(j)
return sort_nums
if __name__ == '__main__':
list = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
print("List source is:", list)
result = bucketSort(list)
print("List sort is:", result)效果
以上是“python3常用排序算法有哪些”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！
