Python 數(shù)據(jù)結(jié)構(gòu)之十大經(jīng)典排序算法一文通關(guān)
發(fā)布日期：2021-12-25 01:43 | 文章來(lái)源：源碼中國(guó)
一文搞掂十大經(jīng)典排序算法
今天整理一下十大經(jīng)典排序算法。
1、冒泡排序
——越小的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端
算法演示
算法步驟
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
- 重復(fù)步驟1~3，直到排序完成。
算法實(shí)現(xiàn)
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、選擇排序
—— 最小的出來(lái)排第一，第二小的出來(lái)排第二…
算法演示
算法步驟
- 首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?。
- 再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。
- 重復(fù)第二步，直到所有元素均排序完畢。
算法實(shí)現(xiàn)
def selectionSort(arr): for i in range(len(arr) - 1): # 記錄最小數(shù)的索引 minIndex = i for j in range(i + 1, len(arr)): if arr[j] < arr[minIndex]: minIndex = j # i 不是最小數(shù)時(shí)，將 i 和最小數(shù)進(jìn)行交換 if i != minIndex: arr[i], arr[minIndex] = arr[minIndex], arr[i] return arr
3、簡(jiǎn)單插入排序
——通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
算法演示
算法步驟
- 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序；
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
- 如果該元素（已排序）大于新元素，將該元素移到下一位置；
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- 將新元素插入到該位置后；重復(fù)步驟2~5。
算法實(shí)現(xiàn)
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、希爾排序
——希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。
算法演示
算法步驟
- 選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；
- 每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
算法實(shí)現(xiàn)
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）的一個(gè)非常典型的應(yīng)用。
算法演示
算法步驟
- 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；
- 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
- 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；
- 重復(fù)步驟 3 直到某一指針達(dá)到序列尾；
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。
算法實(shí)現(xiàn)
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）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。 快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來(lái)看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
算法演示
算法步驟
- 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）;
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；
算法實(shí)現(xiàn)
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、堆排序
——利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法
算法演示
算法步驟
- 創(chuàng)建一個(gè)堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互換；
- 把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；
- 重復(fù)步驟 2，直到堆的尺寸為 1。
算法實(shí)現(xià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 < 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、計(jì)數(shù)排序
——作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
算法演示
算法步驟
- 找出待排序的數(shù)組中最大和最小的元素
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
- 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
算法實(shí)現(xiàn)
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、桶排序
——桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。
算法演示
算法步驟
- 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；
- 遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去；
- 對(duì)每個(gè)不是空的桶進(jìn)行排序；
- 從不是空的桶里把排好序的數(shù)據(jù)拼接起來(lái)。
算法實(shí)現(xiàn)
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]; // 輸入數(shù)據(jù)的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 輸入數(shù)據(jù)的最大值
}
}
// 桶的初始化
var DEFAULT_BUCKET_SIZE = 5;// 設(shè)置桶的默認(rèn)數(shù)量為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] = [];
}
// 利用映射函數(shù)將數(shù)據(jù)分配到各個(gè)桶中
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]); // 對(duì)每個(gè)桶進(jìn)行排序，這里使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
10、基數(shù)排序
基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。
算法演示
算法步驟
- 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
- arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；
- 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；
算法實(shí)現(xiàn)
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;
}
到此這篇關(guān)于Python 數(shù)據(jù)結(jié)構(gòu)之十大經(jīng)典排序算法一文通關(guān)的文章就介紹到這了,更多相關(guān)Python 排序算法內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。
相關(guān)文章
關(guān)注官方微信