目錄十大經(jīng)典的排序算法 一、交換排序1、冒泡排序（前后比較-交換）2、快速排序（選取一個(gè)基準(zhǔn)值，小數(shù)在左大數(shù)在右）二、插入排序1、簡(jiǎn)單插入排序（逐個(gè)插入到前面的有序數(shù)中）2、希爾排序（從大范圍到小范圍進(jìn)行比較-交換）三、選擇排序1、簡(jiǎn)單選擇排序（選擇最小的數(shù)據(jù)放在前面） 2、堆排序（利用最大堆和最小堆的特性）四、歸并排序 五、其他排序1、計(jì)數(shù)排序（字典計(jì)數(shù)-還原）2、桶排序（鏈表）3、基數(shù)排序十大經(jīng)典的排序算法

數(shù)據(jù)結(jié)構(gòu)中的十大經(jīng)典算法：冒泡排序、快速排序、簡(jiǎn)單插入排序、希爾排序、簡(jiǎn)單選擇排序、堆排序、歸并排序、計(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 blist2、快速排序（選取一個(gè)基準(zhǔn)值，小數(shù)在左大數(shù)在右）

（1）算法思想找基準(zhǔn)數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?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、簡(jiǎn)單插入排序（逐個(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 ilist2、希爾排序（從大范圍到小范圍進(jìn)行比較-交換）

（1）算法思想先取一個(gè)正整數(shù) d1，以 d1 間隔分組，先對(duì)每個(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 // 2for 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、簡(jiǎn)單選擇排序（選擇最小的數(shù)據(jù)放在前面）

（1）算法思想第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長(zhǎng)直到全部排序完畢

（2）python實(shí)現(xiàn)代碼

def select_sort(slist): for i in range(len(slist) - 1):x = ifor j in range(i, len(slist)): if slist[j] < slist[x]:x = jslist[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 + 1right = 2 * i + 2largest = iif left < al and a[left] > a[largest]: largest = leftif right < al and a[right] > a[largest]: largest = rightif 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 -= 1heapify(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)化為鍵存儲(chǔ)在額外開辟的數(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]]=0bucket[arr[i]]+=1 for j in range(bucketLen):while bucket[j]>0: arr[sortedIndex] = j sortedIndex+=1 bucket[j]-=1 return arr2、桶排序（鏈表）

（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 tmp3、基數(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)的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！,希望大家以后多多支持好吧啦網(wǎng)！