目錄
- 十大經典的排序算法
- 一、交換排序
- 1、冒泡排序（前后比較-交換）
- 2、快速排序（選取一個基準值，小數在左大數在右）
- 二、插入排序
- 1、簡單插入排序（逐個插入到前面的有序數中）
- 2、希爾排序（從大范圍到小范圍進行比較-交換）
- 三、選擇排序
- 1、簡單選擇排序（選擇最小的數據放在前面）
- 2、堆排序（利用最大堆和最小堆的特性）
- 四、歸并排序
- 五、其他排序
- 1、計數排序（字典計數-還原）
- 2、桶排序（鏈表）
- 3、基數排序
十大經典的排序算法
數據結構中的十大經典算法：冒泡排序、快速排序、簡單插入排序、希爾排序、簡單選擇排序、堆排序、歸并排序、計數排序、桶排序、基數排序
十大經典算法的復雜度和穩定性（如果a原本在b前面，而a=b，排序之后a仍然在b的前面）:
一、交換排序
1、冒泡排序（前后比較-交換）
（1）算法思想
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成
（2）python實現代碼
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、快速排序（選取一個基準值，小數在左大數在右）
（1）算法思想
找基準數，通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列
（2）python實現代碼
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、簡單插入排序（逐個插入到前面的有序數中）
（1）算法思想
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序；首先將第一個作為已經排好序的，然后每次從后的取出插入到前面并排序
（2）python實現代碼
（2）python實現代碼
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、希爾排序（從大范圍到小范圍進行比較-交換）
（1）算法思想
先取一個正整數 d1，以 d1 間隔分組，先對每個分組內的元素使用插入排序操作，重復上述分組和直接插入排序操作；直至 di = 1，即所有記錄放進一個組中排序為止。
（2）python實現代碼
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、簡單選擇排序（選擇最小的數據放在前面）
（1）算法思想
第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢
（2）python實現代碼
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）算法思想
它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大于其父節點的值。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂
（2）python實現代碼
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)
# 不斷調整堆：根與最后一個元素
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）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并
（2）python實現代碼
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、計數排序（字典計數-還原）
（1）算法思想
計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。
（2）python實現代碼
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）算法思想
為了節省空間和時間，我們需要指定要排序的數據中最小以及最大的數字的值。將數組分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序）
（2）python實現代碼
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、基數排序
（1）算法思想
基數排序將數據按位進行分桶，然后將桶中的數據合并。每次分桶只關注其中一位數據，其他位的數據不管，最大的數據有多少位，就進行多少次分桶和合并。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。
（2）python實現代碼
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數據結構的排序算法的詳細內容，更多關于python數據結構的資料請關注腳本之家其它相關文章！,希望大家以后多多支持腳本之家！
您可能感興趣的文章:- 如何利用Python動態展示排序算法
- Python 列表排序詳解
- python編程冒泡排序法實現動圖排序示例解析
- python教程對函數中的參數進行排序
- Python實現堆排序案例詳解
- python如何實現常用的五種排序算法詳解
- Python 數據結構之十大經典排序算法一文通關
