python 排序算法

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

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

一、冒泡排序

冒泡排序（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ù)列的頂端。

例如：?

def?selectionSort(arr):
????for?i?in?range(len(arr)?-?1):
????????#?記錄最小數(shù)的索引
????????minIndex?=?i
????????for?j?in?range(i?+?1,?len(arr)):
????????????if?arr[j]?
二、插入排序
插入排序的代碼實(shí)現(xiàn)雖然沒(méi)有冒泡排序和選擇排序那么簡(jiǎn)單粗暴，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^(guò)撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
例如：
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
三、希爾排序
?希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(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)行依次直接插入排序。
例如：
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）的一個(gè)非常典型的應(yīng)用。
作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：
自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 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
五、快速排序
?快速排序是由東尼·霍爾所發(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ǔ)上的遞歸分治法。
例如：
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）是指利用堆這種數(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)的值，在堆排序算法中用于降序排列；
例如：
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
七、計(jì)數(shù)排序
?計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(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
以上就是小編今天的分享了，希望可以幫助到大家。