目錄
- 十大經(jīng)典的排序算法
- 一、交換排序
- 1、冒泡排序（前后比較-交換）
- 2、快速排序（選取一個(gè)基準(zhǔn)值，小數(shù)在左大數(shù)在右）
- 二、插入排序
- 1、簡單插入排序（逐個(gè)插入到前面的有序數(shù)中）
- 2、希爾排序（從大范圍到小范圍進(jìn)行比較-交換）
- 三、選擇排序
- 1、簡單選擇排序（選擇最小的數(shù)據(jù)放在前面）
- 2、堆排序（利用最大堆和最小堆的特性）
- 四、歸并排序
- 五、其他排序
- 1、計(jì)數(shù)排序（字典計(jì)數(shù)-還原）
- 2、桶排序（鏈表）
- 3、基數(shù)排序
十大經(jīng)典的排序算法
數(shù)據(jù)結(jié)構(gòu)中的十大經(jīng)典算法：冒泡排序、快速排序、簡單插入排序、希爾排序、簡單選擇排序、堆排序、歸并排序、計(jì)數(shù)排序、桶排序、基數(shù)排序
十大經(jīng)典算法的復(fù)雜度和穩(wěn)定性（如果a原本在b前面，而a=b，排序之后a仍然在b的前面）:
一、交換排序
1、冒泡排序（前后比較-交換）
（1）算法思想
它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成
（2）python實(shí)現(xiàn)代碼
def bubble_sort(blist):
count = len(blist)
for i in range(0, count):
for j in range(i + 1, count):
if blist[i] > blist[j]:
blist[i], blist[j] = blist[j], blist[i]
return blist
2、快速排序（選取一個(gè)基準(zhǔn)值，小數(shù)在左大數(shù)在右）
（1）算法思想
找基準(zhǔn)數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
（2）python實(shí)現(xiàn)代碼
def quick_sort(qlist):
if qlist == []:
return []
else:
qfirst = qlist[0]
qless = quick_sort([l for l in qlist[1:] if l qfirst])
qmore = quick_sort([m for m in qlist[1:] if m >= qfirst])
return qless + [qfirst] + qmore
二、插入排序
1、簡單插入排序（逐個(gè)插入到前面的有序數(shù)中）
（1）算法思想
插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序；首先將第一個(gè)作為已經(jīng)排好序的，然后每次從后的取出插入到前面并排序
（2）python實(shí)現(xiàn)代碼
（2）python實(shí)現(xiàn)代碼
def insert_sort(ilist):
for i in range(len(ilist)):
for j in range(i):
if ilist[i] ilist[j]:
ilist.insert(j, ilist.pop(i))
break
return ilist
2、希爾排序（從大范圍到小范圍進(jìn)行比較-交換）
（1）算法思想
先取一個(gè)正整數(shù) d1，以 d1 間隔分組，先對每個(gè)分組內(nèi)的元素使用插入排序操作，重復(fù)上述分組和直接插入排序操作；直至 di = 1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?/p>
（2）python實(shí)現(xiàn)代碼
def shell_sort(slist):
gap = len(slist)
while gap > 1:
gap = gap // 2
for i in range(gap, len(slist)):
for j in range(i % gap, i, gap):
if slist[i] slist[j]:
slist[i], slist[j] = slist[j], slist[i]
return slist
三、選擇排序
1、簡單選擇排序（選擇最小的數(shù)據(jù)放在前面）
（1）算法思想
第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢
（2）python實(shí)現(xiàn)代碼
def select_sort(slist):
for i in range(len(slist) - 1):
x = i
for j in range(i, len(slist)):
if slist[j] slist[x]:
x = j
slist[i], slist[x] = slist[x], slist[i]
return slist
2、堆排序（利用最大堆和最小堆的特性）
（1）算法思想
它是選擇排序的一種。可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂
（2）python實(shí)現(xiàn)代碼
import math
def heap_sort(a):
al = len(a)
def heapify(a, i):
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left al and a[left] > a[largest]:
largest = left
if right al and a[right] > a[largest]:
largest = right
if largest != i:
a[i], a[largest] = a[largest], a[i]
heapify(a, largest)
# 建堆
for i in range(math.floor(len(a) / 2), -1, -1):
heapify(a, i)
# 不斷調(diào)整堆：根與最后一個(gè)元素
for i in range(len(a) - 1, 0, -1):
a[0], a[i] = a[i], a[0]
al -= 1
heapify(a, 0)
return a
四、歸并排序
（1）算法思想
采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并
（2）python實(shí)現(xiàn)代碼
def merge_sort(a):
if(len(a)2):
return a
middle = len(a)//2
left, right = a[0:middle], a[middle:]
return merge(merge_sort(left), merge_sort(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
五、其他排序
1、計(jì)數(shù)排序（字典計(jì)數(shù)-還原）
（1）算法思想
計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
（2）python實(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
2、桶排序（鏈表）
（1）算法思想
為了節(jié)省空間和時(shí)間，我們需要指定要排序的數(shù)據(jù)中最小以及最大的數(shù)字的值。將數(shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）
（2）python實(shí)現(xiàn)代碼
def bucketSort(nums):
bucket=[0]*(max(nums)-min(nums)+1)
for i in range(len(nums)):
bucket[nums[i]-min(nums)]+=1
tmp=[]
for i in range(len(bucket)):
if bucket[i]!=0:
tmp+=[min(nums)+i]*bucket[i]
return tmp
3、基數(shù)排序
（1）算法思想
基數(shù)排序?qū)?shù)據(jù)按位進(jìn)行分桶，然后將桶中的數(shù)據(jù)合并。每次分桶只關(guān)注其中一位數(shù)據(jù)，其他位的數(shù)據(jù)不管，最大的數(shù)據(jù)有多少位，就進(jìn)行多少次分桶和合并。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
（2）python實(shí)現(xiàn)代碼
def radix_sort(array):
bucket, digit = [[]], 0
while len(bucket[0]) != len(array):
bucket = [[], [], [], [], [], [], [], [], [], []]
for i in range(len(array)):
num = (array[i] // 10 ** digit) % 10
bucket[num].append(array[i])
array.clear()
for i in range(len(bucket)):
array += bucket[i]
digit += 1
return array
以上就是python數(shù)據(jù)結(jié)構(gòu)的排序算法的詳細(xì)內(nèi)容，更多關(guān)于python數(shù)據(jù)結(jié)構(gòu)的資料請關(guān)注腳本之家其它相關(guān)文章！,希望大家以后多多支持腳本之家！
您可能感興趣的文章:- 如何利用Python動態(tài)展示排序算法
- Python 列表排序詳解
- python編程冒泡排序法實(shí)現(xiàn)動圖排序示例解析
- python教程對函數(shù)中的參數(shù)進(jìn)行排序
- Python實(shí)現(xiàn)堆排序案例詳解
- python如何實(shí)現(xiàn)常用的五種排序算法詳解
- Python 數(shù)據(jù)結(jié)構(gòu)之十大經(jīng)典排序算法一文通關(guān)
