Python數據結構之有哪些經典的排序算法

這篇文章主要講解了“Python數據結構之有哪些經典的排序算法”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Python數據結構之有哪些經典的排序算法”吧！

目錄

• 1、冒泡排序

• 算法演示

• 算法步驟

• 算法實現

• 2、選擇排序

• 算法演示

• 算法步驟

• 算法實現

• 3、簡單插入排序

• 算法演示

• 算法步驟

• 算法實現

• 4、希爾排序

• 算法演示

• 算法步驟

• 算法實現

• 5、歸并排序

• 算法演示

• 算法步驟

• 算法實現

• 6、快速排序

• 算法演示

• 算法步驟

• 算法實現

• 7、堆排序

• 算法演示

• 算法步驟

• 算法實現

• 8、計數排序

• 算法演示

• 算法步驟

• 算法實現

• 9、桶排序

• 算法演示

• 算法步驟

• 算法實現

• 10、基數排序

• 算法演示

• 算法步驟

• 算法實現

1、冒泡排序

——越小的元素會經由交換慢慢“浮”到數列的頂端

算法演示

算法步驟

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

• 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；

• 針對所有的元素重復以上的步驟，除了最后一個；

• 重復步驟1~3，直到排序完成。

算法實現

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

2、選擇排序

—— 最小的出來排第一，第二小的出來排第二…

算法演示

算法步驟

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

• 再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。

• 重復第二步，直到所有元素均排序完畢。

算法實現

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

3、簡單插入排序

——通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。

算法演示

算法步驟

• 從第一個元素開始，該元素可以認為已經被排序；

• 取出下一個元素，在已經排序的元素序列中從后向前掃描；

• 如果該元素（已排序）大于新元素，將該元素移到下一位置；

• 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；

• 將新元素插入到該位置后；重復步驟2~5。

算法實現

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

4、希爾排序

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

算法演示

算法步驟

• 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

• 按增量序列個數 k，對序列進行 k 趟排序；

• 每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

算法實現

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

5、歸并排序

——建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

算法演示

算法步驟

• 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；

• 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

• 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

• 重復步驟 3 直到某一指針達到序列尾；

• 將另一序列剩下的所有元素直接復制到合并序列尾。

算法實現

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

6、快速排序

——快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。 快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

算法演示

算法步驟

• 從數列中挑出一個元素，稱為 “基準”（pivot）;

• 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；

• 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序；

算法實現

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]

7、堆排序

——利用堆這種數據結構所設計的一種排序算法

算法演示

算法步驟

• 創建一個堆 H[0……n-1]；

• 把堆首（最大值）和堆尾互換；

• 把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；

• 重復步驟 2，直到堆的尺寸為 1。

算法實現

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

8、計數排序

——作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

算法演示

算法步驟

• 找出待排序的數組中最大和最小的元素

• 統計數組中每個值為i的元素出現的次數，存入數組C的第i項

• 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）

• 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

算法實現

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

9、桶排序

——桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。

算法演示

算法步驟

• 設置一個定量的數組當作空桶；

• 遍歷輸入數據，并且把數據一個一個放到對應的桶里去；

• 對每個不是空的桶進行排序；

• 從不是空的桶里把排好序的數據拼接起來。

算法實現

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 輸入數據的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 輸入數據的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 設置桶的默認數量為5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函數將數據分配到各個桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 對每個桶進行排序，這里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
 
    return arr;
}

10、基數排序

基數排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。

算法演示

算法步驟

• 取得數組中的最大數，并取得位數；

• arr為原始數組，從最低位開始取每個位組成radix數組；

• 對radix進行計數排序（利用計數排序適用于小范圍數的特點）；

算法實現

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

感謝各位的閱讀，以上就是“Python數據結構之有哪些經典的排序算法”的內容了，經過本文的學習后，相信大家對Python數據結構之有哪些經典的排序算法這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！