排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。
象州網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)公司！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)公司成立與2013年到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)公司。
排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括：
點(diǎn)擊以下圖片查看大圖：
關(guān)于時(shí)間復(fù)雜度
平方階 (O(n2)) 排序 各類簡(jiǎn)單排序：直接插入、直接選擇和冒泡排序。
線性對(duì)數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。
關(guān)于穩(wěn)定性
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
名詞解釋：
n：數(shù)據(jù)規(guī)模 k："桶"的個(gè)數(shù) In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存 Out-place：占用額外內(nèi)存 穩(wěn)定性：排序后 2 個(gè)相等鍵值的順序和排序之前它們的順序相同
包含以下內(nèi)容：
1、冒泡排序 2、選擇排序 3、插入排序 4、希爾排序 5、歸并排序 6、快速排序 7、堆排序 8、計(jì)數(shù)排序 9、桶排序 10、基數(shù)排序
排序算法包含的相關(guān)內(nèi)容具體如下：
冒泡排序算法
冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端。
選擇排序算法
選擇排序是一種簡(jiǎn)單直觀的排序算法，無(wú)論什么數(shù)據(jù)進(jìn)去都是 O(n?) 的時(shí)間復(fù)雜度。所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間。
插入排序算法
插入排序的代碼實(shí)現(xiàn)雖然沒有冒泡排序和選擇排序那么簡(jiǎn)單粗暴，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
希爾排序算法
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。
歸并排序算法
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。
快速排序算法
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。
堆排序算法
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說是一種利用堆的概念來排序的選擇排序。
計(jì)數(shù)排序算法
計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
桶排序算法
桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。
基數(shù)排序算法
基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
因?yàn)閙erge_sort函數(shù)沒有返回值,所以l1=merge_sort(left)和r1=merge_sort(right)中出l1和r1沒有類型的錯(cuò)誤,加一個(gè)返回值return li就沒問題了.
完整的Python程序如下(改動(dòng)的地方見注釋)
def?merge_sort(li):
if?len(li)==1:
return?li??#這里return改成return?li
mid=len(li)//2
left=li[:mid]
right=li[mid:]
l1=merge_sort(left)
r1=merge_sort(right)
return?merge(l1,r1)
def?merge(left,right):
result=[]
while?len(left)0?and?len(right)0:
if?left[0]=right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result+=left
result+=right
return?result
a=[2,39,92,19,28,32,85,53]
print(merge_sort(a))
源代碼(注意源代碼的縮進(jìn))
def?merge(left,right):?
result?=?[]?
i,j?=?0,?0?
while?i??len(left)?and?j??len(right):
if?left[i]?=?right[j]:
result.append(left[i])?
i?=?i?+?1?
else:
result.append(right[j])?
j?=?j?+?1
while?(i??len(left)):
result.append(left[i])?
i?=?i?+?1?
while?(j??len(right)):
result.append(right[j])?
j?=?j?+?1?
return(result)
def?mergsort(L):
print(L)
if?len(L)??2:
print(L[:])
#?Missing?the?following?line
return?L
else:
middle?=?len(L)/2
left?=?mergsort(L[:int(middle)])
right?=?mergsort(L[int(middle):])
together?=?merge(left,right)
print(together)
return(together)
class SortMethod:
'''
插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。
插入算法把要排序的數(shù)組分成兩部分：
第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外（讓數(shù)組多一個(gè)空間才有插入的位置）
第二部分就只包含這一個(gè)元素（即待插入元素）。
在第一部分排序完成后，再將這個(gè)最后元素插入到已排好序的第一部分中。
'''
def insert_sort(lists):
# 插入排序
count = len(lists)
for i in range(1, count):
key = lists[i]
j = i - 1
while j = 0:
if lists[j] key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists
'''
希爾排序 (Shell Sort) 是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因 DL．Shell 于 1959 年提出而得名。
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至 1 時(shí)，整個(gè)文件恰被分成一組，算法便終止。
'''
def shell_sort(lists):
# 希爾排序
count = len(lists)
step = 2
group = count / step
while group 0:
for i in range(0, group):
j = i + group
while j count:
k = j - group
key = lists[j]
while k = 0:
if lists[k] key:
lists[k + group] = lists[k]
lists[k] = key
k -= group
j += group
group /= step
return lists
'''
冒泡排序重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
'''
def bubble_sort(lists):
# 冒泡排序
count = len(lists)
for i in range(0, count):
for j in range(i + 1, count):
if lists[i] lists[j]:
temp = lists[j]
lists[j] = lists[i]
lists[i] = temp
return lists
'''
快速排序
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
'''
def quick_sort(lists, left, right):
# 快速排序
if left = right:
return lists
key = lists[left]
low = left
high = right
while left right:
while left right and lists[right] = key:
right -= 1
lists[left] = lists[right]
while left right and lists[left] = key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists
'''
直接選擇排序
第 1 趟，在待排序記錄 r[1] ~ r[n] 中選出最小的記錄，將它與 r[1] 交換；
第 2 趟，在待排序記錄 r[2] ~ r[n] 中選出最小的記錄，將它與 r[2] 交換；
以此類推，第 i 趟在待排序記錄 r[i] ~ r[n] 中選出最小的記錄，將它與 r[i] 交換，使有序序列不斷增長(zhǎng)直到全部排序完畢。
'''
def select_sort(lists):
# 選擇排序
count = len(lists)
for i in range(0, count):
min = i
for j in range(i + 1, count):
if lists[min] lists[j]:
min = j
temp = lists[min]
lists[min] = lists[i]
lists[i] = temp
return lists
'''
堆排序 (Heapsort) 是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。
可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即 A[PARENT[i]] = A[i]。
在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。
'''
# 調(diào)整堆
def adjust_heap(lists, i, size):
lchild = 2 * i + 1
rchild = 2 * i + 2
max = i
if i size / 2:
if lchild size and lists[lchild] lists[max]:
max = lchild
if rchild size and lists[rchild] lists[max]:
max = rchild
if max != i:
lists[max], lists[i] = lists[i], lists[max]
adjust_heap(lists, max, size)
# 創(chuàng)建堆
def build_heap(lists, size):
for i in range(0, (size/2))[::-1]:
adjust_heap(lists, i, size)
# 堆排序
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)
'''
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法 （Divide and Conquer） 的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
歸并過程為：
比較 a[i] 和 a[j] 的大小，若 a[i]≤a[j]，則將第一個(gè)有序表中的元素 a[i] 復(fù)制到 r[k] 中，并令 i 和 k 分別加上 1；
否則將第二個(gè)有序表中的元素 a[j] 復(fù)制到 r[k] 中，并令 j 和 k 分別加上 1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到 r 中從下標(biāo) k 到下標(biāo) t 的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間 [s,t] 以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間 [s,t]。
'''
def merge(left, right):
i, j = 0, 0
result = []
while i len(left) and j len(right):
if left[i] = right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
def merge_sort(lists):
# 歸并排序
if len(lists) = 1:
return lists
num = len(lists) / 2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left, right)
'''
基數(shù)排序 （radix sort） 屬于“分配式排序” （distribution sort），又稱“桶子法” （bucket sort） 或 bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序。
其時(shí)間復(fù)雜度為 O (nlog(r)m)，其中 r 為所采取的基數(shù)，而 m 為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
'''
import math
def radix_sort(lists, radix=10):
k = int(math.ceil(math.log(max(lists), radix)))
bucket = [[] for i in range(radix)]
for i in range(1, k+1):
for j in lists:
bucket[j/(radix**(i-1)) % (radix**i)].append(j)
del lists[:]
for z in bucket:
lists += z
del z[:]
return lists
---------------------
作者：CRazyDOgen
來源：CSDN
原文：
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請(qǐng)附上博文鏈接！
python內(nèi)置關(guān)于排序的工具主要有兩個(gè)一個(gè)是列表自帶的 sort() 方法，另外一個(gè)是 sorted() 函數(shù)。Python 列表內(nèi)置方法可以直接修改列表。而 sorted() 內(nèi)置函數(shù)從一個(gè)可迭代對(duì)象（列表，元組等都可以）構(gòu)建一個(gè)新的排序列表。其函數(shù)原型分別如下：
對(duì)列表進(jìn)行默認(rèn)排序
從函數(shù)原型來看，可以看到兩者都具有兩個(gè)可選參數(shù)，它們都必須指定為關(guān)鍵字參數(shù)。
key 指定帶有單個(gè)參數(shù)的函數(shù)，用于從 iterable 的每個(gè)元素中提取用于比較的鍵 (例如 key=str.lower)。默認(rèn)值為 None (直接比較元素)。 key 形參的值應(yīng)該是個(gè)函數(shù)（或其他可調(diào)用對(duì)象），它接受一個(gè)參數(shù)并返回一個(gè)用于排序的鍵。
假設(shè)有其他類型的變量，比如一個(gè)自定義的類或者列表中又是一個(gè)列表。以官網(wǎng)例子為例有這樣一個(gè)列表，其元素為元組，
可以用以下方式按照年齡排序
類似的有自定義類
可以用如下方式進(jìn)行排序
也可以顯示定義一個(gè)函數(shù)，且只有一個(gè)參數(shù)，返回用于排序的鍵，比如
總之就是定義一個(gè)函數(shù)返回一個(gè)用于排序的鍵，可以用lambda函數(shù)或者 def 定義都可以。
上面實(shí)現(xiàn)的簡(jiǎn)單函數(shù)實(shí)際就是實(shí)現(xiàn)了返回一個(gè)有序結(jié)構(gòu)的第 n 的元素，或者某個(gè)類中的某個(gè)屬性，因此 Python 提供了便利功能，使訪問器功能更容易，更快捷。operator 模塊有 itemgetter() 、 attrgetter() 函數(shù)。分別完成返回第 n 個(gè)元素，某個(gè)屬性功能。上面的排序可以用如下方式進(jìn)行實(shí)現(xiàn)
在python2中，sort有一個(gè) cmp 參數(shù)，即用一個(gè)函數(shù)來自定義比較，在python3中這種方式被取消。為了繼承類似的用法，在 Python 3.2 中， functools.cmp_to_key() 函數(shù)被添加到標(biāo)準(zhǔn)庫(kù)中的 functools 模塊中。
這種作用先定義如何比較兩個(gè)變量，以上面的學(xué)生列表按照年齡排序?yàn)槔?/p>
這種做法自定義比較函數(shù)接收兩個(gè)形參，返回比較結(jié)果（bool），而新式方法接受一個(gè)參數(shù)，返回的是比較的鍵。
假設(shè)有字典 d = {'b':2, 'a':1,'c':8,'d':4} ，則可以通過以下方式對(duì)字典按照鍵和值進(jìn)行排序
python實(shí)現(xiàn)折半查找和歸并排序算法
今天依舊是學(xué)算法，前幾天在搞bbs項(xiàng)目，界面也很丑，評(píng)論功能好像也有BUG?，F(xiàn)在不搞了，得學(xué)下算法和數(shù)據(jù)結(jié)構(gòu)，筆試過不了，連面試的機(jī)會(huì)都沒有……
今天學(xué)了折半查找算法，折半查找是蠻簡(jiǎn)單的，但是歸并排序我就挺懵比，看教材C語(yǔ)言寫的歸并排序看不懂，后來參考了別人的博客，終于搞懂了。
折半查找
先看下課本對(duì)于 折半查找的講解。注意了，折半查找是對(duì)于有序序列而言的。每次折半，則查找區(qū)間大約縮小一半。low,high分別為查找區(qū)間的第一個(gè)下標(biāo)與最后一個(gè)下標(biāo)。出現(xiàn)lowhigh時(shí)，說明目標(biāo)關(guān)鍵字在整個(gè)有序序列中不存在，查找失敗。
看我用python編程實(shí)現(xiàn):
defBinSearch(array, key, low, high): mid=int((low+high)/2) ifkey==array[mid]:# 若找到 returnarray[mid] iflow high: returnFalse ifkey array[mid]: returnBinSearch(array, key, low, mid-1)#遞歸 ifkey array[mid]: returnBinSearch(array, key, mid+1, high) if__name__=="__main__": array=[4,13,27,38,49,49,55,65,76,97] ret=BinSearch(array,76,0,len(array)-1)# 通過折半查找，找到65 print(ret)
輸出: 在列表中查找76.
76
時(shí)間復(fù)雜度：O(logn)
歸并排序算法
先闡述一下排序思路：
首先歸并排序使用了二分法，歸根到底的思想還是分而治之。歸并排序是指把無(wú)序的待排序序列分解成若干個(gè)有序子序列，并把有序子序列合并為整體有序序列的過程。長(zhǎng)度為1的序列是有序的。因此當(dāng)分解得到的子序列長(zhǎng)度大于1時(shí)，應(yīng)繼續(xù)分解，直到長(zhǎng)度為1.
(下圖是分解過程，圖自python編程實(shí)現(xiàn)歸并排序)
合并的過程如下:
很好，你現(xiàn)在可以和別人說，老子會(huì)歸并排序了。但是讓你寫代碼出來，相信你是不會(huì)的……
來來來，看我用python寫的歸并排序算法:
defmerge_sort(array):# 遞歸分解 mid=int((len(array)+1)/2) iflen(array)==1:# 遞歸結(jié)束的條件，分解到列表只有一個(gè)數(shù)據(jù)時(shí)結(jié)束 returnarray list_left=merge_sort(array[:mid]) list_right=merge_sort(array[mid:]) print("list_left:", list_left) print("list_right:", list_right) returnmerge(list_left, list_right)# 進(jìn)行歸并 defmerge(list_left, list_right):# 進(jìn)行歸并 final=[] whilelist_leftandlist_right: iflist_left[0] =list_right[0]:# 如果將"="改為"",則歸并排序不穩(wěn)定 final.append(list_left.pop(0)) else: final.append(list_right.pop(0)) returnfinal+list_left+list_right# 返回排序好的列表 if__name__=="__main__": array=[49,38,65,97,76] print(merge_sort(array))輸出:
輸出：
list_left: [49]
list_right: [38]
list_left: [38, 49]
list_right: [65]
list_left: [97]
list_right: [76]
list_left: [38, 49, 65]
list_right: [76, 97]
[38, 49, 65, 76, 97]
時(shí)間度雜度: 平均情況＝最好情況＝最壞情況＝O(nlogn)
空間復(fù)雜度:O(n)
穩(wěn)定性:穩(wěn)定
對(duì)序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進(jìn)行歸并排序的實(shí)例如下:
使用歸并排序?yàn)橐涣袛?shù)字進(jìn)行排序的宏觀過程:
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助
重慶分公司
重慶分公司
