python3常用排序算法有哪些-創(chuàng)新互聯(lián)

這篇文章主要為大家展示了“python3常用排序算法有哪些”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“python3常用排序算法有哪些”這篇文章吧。

龍?zhí)毒W(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)公司,龍?zhí)毒W(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為龍?zhí)?000多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)要多少錢(qián)，請(qǐng)找那個(gè)售后服務(wù)好的龍?zhí)蹲鼍W(wǎng)站的公司定做！

我簡(jiǎn)單的繪制了一下排序算法的分類(lèi)，藍(lán)色字體的排序算法是我們用python3實(shí)現(xiàn)的，也是比較常用的排序算法。

Python3常用排序算法1、Python3冒泡排序——交換類(lèi)排序

冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。

它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。

走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端。

作為最簡(jiǎn)單的排序算法之一，冒泡排序給我的感覺(jué)就像Abandon在單詞書(shū)里出現(xiàn)的感覺(jué)一樣，每次都在第一頁(yè)第一位，所以最熟悉。

冒泡排序還有一種優(yōu)化算法，就是立一個(gè) flag，當(dāng)在一趟序列遍歷中元素沒(méi)有發(fā)生交換，則證明該序列已經(jīng)有序。

但這種改進(jìn)對(duì)于提升性能來(lái)說(shuō)并沒(méi)有什么太大作用。

最快：當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí)（都已經(jīng)是正序了，我還要你冒泡排序有何用?。?/p>

最慢：當(dāng)輸入的數(shù)據(jù)是反序時(shí)（寫(xiě)一個(gè) for 循環(huán)反序輸出數(shù)據(jù)不就行了，干嘛要用你冒泡排序呢，我是閑的嗎）

Python3冒泡排序?qū)嵗a

# 冒泡排序
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)

效果

2、Python3快速排序-交換類(lèi)排序

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。

在平均狀況下，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來(lái)看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。

快速排序的名字起的是簡(jiǎn)單粗暴，因?yàn)橐宦?tīng)到這個(gè)名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。

特點(diǎn)：選基準(zhǔn)、分治、遞歸

Python3快速排序-交換類(lèi)排序?qū)嵗创a

# 快速排序
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快排簡(jiǎn)寫(xiě)

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]])

效果

3、Python3選擇排序-選擇類(lèi)排序

選擇排序是一種簡(jiǎn)單直觀的排序算法。

無(wú)論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時(shí)間復(fù)雜度。所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。

Python3選擇排序-選擇類(lèi)排序?qū)嵗创a

# 選擇排序
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ù)時(shí)，將 i 和最小數(shù)進(jìn)行交換
    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)

效果

4、Python3堆排序-選擇類(lèi)排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。

堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說(shuō)是一種利用堆的概念來(lái)排序的選擇排序。分為兩種方法：

1、大頂堆（大根堆）：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列；

2、小頂堆（小根堆）：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列；

堆排序的平均時(shí)間復(fù)雜度為 Ο(nlogn)。

Python3堆排序-選擇類(lèi)排序?qū)嵗创a

# 堆排序
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)

效果

5、Python3插入排序-插入類(lèi)排序

插入排序是一種最簡(jiǎn)單直觀的排序算法。

插入排序的代碼實(shí)現(xiàn)雖然沒(méi)有冒泡排序和選擇排序那么簡(jiǎn)單粗暴，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^(guò)撲克牌的人都應(yīng)該能夠秒懂。

它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。

Python3插入排序-插入類(lèi)排序?qū)嵗创a

# 作者：沙振宇
# 插入排序
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)

效果

6、Python3希爾排序-插入類(lèi)排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。

但希爾排序是非穩(wěn)定排序算法。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

1、插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率；

2、但插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位；

希爾排序的基本思想是：

先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

Python3希爾排序-插入類(lèi)排序?qū)嵗创a

# 作者：沙振宇
# 希爾排序
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)

效果

7、Python3歸并排序-歸并類(lèi)排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。

該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：

1、自上而下的遞歸（所有遞歸的方法都可以用迭代重寫(xiě)，所以就有了第 2 種方法）；

2、自下而上的迭代；

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是 O(nlogn) 的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間

Python3歸并排序-歸并類(lèi)排序?qū)嵗创a

# 作者：沙振宇
# 歸并排序
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)

效果

8、Python3計(jì)數(shù)排序-分布類(lèi)排序

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。

作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來(lái)計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的大值與最小值的差加上1），這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。例如：計(jì)數(shù)排序是用來(lái)排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計(jì)數(shù)排序可以用在基數(shù)排序中的算法來(lái)排序數(shù)據(jù)范圍很大的數(shù)組。

通俗地理解，例如有 10 個(gè)年齡不同的人，統(tǒng)計(jì)出有 8 個(gè)人的年齡比 A 小，那 A 的年齡就排在第 9 位,用這個(gè)方法可以得到其他每個(gè)人的位置,也就排好了序。當(dāng)然，年齡有重復(fù)時(shí)需要特殊處理（保證穩(wěn)定性），這就是為什么最后要反向填充目標(biāo)數(shù)組，以及將每個(gè)數(shù)字的統(tǒng)計(jì)減去 1 的原因。

Python3計(jì)數(shù)排序-分布類(lèi)排序?qū)嵗创a

# 作者：沙振宇
# 計(jì)數(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)

效果

9、Python3基數(shù)排序-分布類(lèi)排序

基數(shù)排序是一種非比較型整數(shù)排序算法。

其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

python3基數(shù)排序-分布類(lèi)排序?qū)嵗创a

# 作者：沙振宇
# 基數(shù)排序
def radix_sort(arr):
  """基數(shù)排序"""
  i = 0 # 記錄當(dāng)前正在排拿一位，最低位為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)

效果

Python3桶排序-分布類(lèi)排序

桶排序是計(jì)數(shù)排序的升級(jí)版。

它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。為了使桶排序更加高效，我們需要做到這兩點(diǎn)：

1、在額外空間充足的情況下，盡量增大桶的數(shù)量

2、使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中

同時(shí)，對(duì)于桶中元素的排序，選擇何種比較排序算法對(duì)于性能的影響至關(guān)重要。

最快：當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中。

最慢：當(dāng)輸入的數(shù)據(jù)被分配到了同一個(gè)桶中。

Python3桶排序-分布類(lèi)排序?qū)嵗创a

# 作者：沙振宇
# 桶排序
def bucketSort(arr):
  # 選擇一個(gè)大的數(shù)
  max_num = max(arr)
  # 創(chuàng)建一個(gè)元素全是0的列表, 當(dāng)做桶
  bucket = [0] * (max_num + 1)
  # 把所有元素放入桶中, 即把對(duì)應(yīng)元素個(gè)數(shù)加一
  for i in arr:
    bucket[i] += 1
  # 存儲(chǔ)排序好的元素
  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常用排序算法有哪些”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)站標(biāo)題：python3常用排序算法有哪些-創(chuàng)新互聯(lián)
文章地址：http://bm7419.com/article12/dsegdc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、App設(shè)計(jì)、品牌網(wǎng)站制作、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站排名、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)