Python 數據結構之十大經典排序算法一文通關
一文搞掂十大經典排序算法
今天整理一下十大經典排序算法。
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 排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！