一文搞掂十大經典排序演算法

今天整理一下十大經典排序演算法，

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、桶排序

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

演算法演示

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-9ybEGKPU-1633970885002)(C:\Users\LANWEI~1\AppData\Local\Temp\1633970398356.png)]

演算法步驟

設定一個定量的陣列當作空桶；
遍歷輸入資料，并且把資料一個一個放到對應的桶里去；
對每個不是空的桶進行排序；
從不是空的桶里把排好序的資料拼接起來，

演算法實作

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/312129.html

標籤：其他

上一篇：你們公司用什么查看日志？

下一篇：??【資料結構和演算法】動圖演示，超詳細，就怕你不會！二分查找詳解【建議收藏】??