排序演算法 python

<link rel="stylesheet" href="https://js.how234.com/third-party/SyntaxHighlighter/shCoreDefault.css" type="text/css" /><script type="text/javascript" src="https://js.how234.com/third-party/SyntaxHighlighter/shCore.js"></script><script type="text/javascript"> SyntaxHighlighter.all(); </script>

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] < arr[minIndex]:                minIndex = j        # i 不是最小數時，將 i 和最小數進行交換        if i != minIndex:            arr[i], arr[minIndex] = arr[minIndex], arr[i]    return arr

二、插入排序

插入排序的程式碼實現雖然沒有氣泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序演算法，它的工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。

例如：

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

四、歸併排序

 歸併排序（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 < right:        partitionIndex = partition(arr, left, right)        quickSort(arr, left, partitionIndex-1)        quickSort(arr, partitionIndex+1, right)    return arrdef 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-1def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]

六、堆排序

 堆排序（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 < 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

七、計數排序

 計數排序的核心在於將輸入的資料值轉化為鍵儲存在額外開闢的陣列空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的資料必須是有確定範圍的整數。

例如：

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