python 排序算法

python 排序算法有哪些？一起來看看小編今天的分享吧！

python的排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：冒泡排序、插入排序、希爾排序、歸并排序、快速排序、堆排序、計數排序等。

一、冒泡排序

冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

例如：?

def?selectionSort(arr):
????for?i?in?range(len(arr)?-?1):
????????#?記錄最小數的索引
????????minIndex?=?i
????????for?j?in?range(i?+?1,?len(arr)):
????????????if?arr[j]?
二、插入排序
插入排序的代碼實現雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。
例如：
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
三、希爾排序
?希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
1、插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率；
2、但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位；
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
例如：
def?shellSort(arr):
????import?math
????gap=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
四、歸并排序
?歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
作為一種典型的分而治之思想的算法應用，歸并排序的實現由兩種方法：
自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
自下而上的迭代；
例如：
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
五、快速排序
?快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。
例如：
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?
六、堆排序
?堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
1、大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；
2、小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；
例如：
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??arr[largest]:
????????largest?=?left
????if?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
七、計數排序
?計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。
例如：
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
以上就是小編今天的分享了，希望可以幫助到大家。