摘要:創(chuàng)建最大堆堆排序八計(jì)數(shù)排序以上節(jié)選自維基百科代碼如下為數(shù)組中的最大值待排序數(shù)組長(zhǎng)度設(shè)置輸出序列,初始化為設(shè)置技術(shù)序列,初始化為本文章參考維基百科和八大排序算法實(shí)現(xiàn)合輯
一、冒泡排序
冒泡排序算法的運(yùn)作如下:
比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后,最后的元素會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。
以上節(jié)選自維基百科
代碼實(shí)現(xiàn):
</>復(fù)制代碼
def bubble_sort(numberlist):
length = len(numberlist)
for i in range(length):
for j in range(1, length - i):
if numberlist[j - 1] > numberlist[j]:
numberlist[j], numberlist[j - 1] = numberlist[j - 1], numberlist[j]
return numberlist
二、選擇排序
選擇排序(Selection sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再?gòu)氖S辔磁判蛟刂欣^續(xù)尋找最小(大)元素,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
以上節(jié)選自維基百科
代碼實(shí)現(xiàn):
</>復(fù)制代碼
def findSmallest(arr): # 用于查找出數(shù)組中最小的元素,返回最小元素的索引。
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if smallest > arr[i]:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectSort(arr):
newArr = []
while arr:
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
三、插入排序
步驟如下
從第一個(gè)元素開(kāi)始,該元素可以認(rèn)為已經(jīng)被排序
取出下一個(gè)元素,在已經(jīng)排序的元素序列中從后向前掃描
如果該元素(已排序)大于新元素,將該元素移到下一位置
重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復(fù)步驟2~5
以上節(jié)選自維基百科
代碼實(shí)現(xiàn)
</>復(fù)制代碼
def insert_sort(data):
for k in range(1, len(data)):
cur = data[k]
j = k
while j > 0 and data[j - 1] > cur:
data[j] = data[j - 1]
j -= 1
data[j] = cur
return data
四、希爾排序
希爾排序通過(guò)將比較的全部元素分為幾個(gè)區(qū)域來(lái)提升插入排序的性能。這樣可以讓一個(gè)元素可以一次性地朝最終位置前進(jìn)一大步。然后算法再取越來(lái)越小的步長(zhǎng)進(jìn)行排序,算法的最后一步就是普通的插入排序,但是到了這步,需排序的數(shù)據(jù)幾乎是已排好的了(此時(shí)插入排序較快)。
以上節(jié)選自維基百科
代碼實(shí)現(xiàn):
</>復(fù)制代碼
def shell_sort(numberlist):
length = len(numberlist)
gap = length // 2
while gap > 0:
for i in range(gap, length):
temp = numberlist[i]
j = i
while j >= gap and numberlist[j - gap] > temp:
numberlist[j] = numberlist[j - gap]
j -= gap
numberlist[j] = temp
gap = gap // 2
return numberlist
五、歸并排序
原理如下(假設(shè)序列共有{displaystyle n}個(gè)元素):
將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作,形成{displaystyle ceil(n/2)}個(gè)序列,排序后每個(gè)序列包含兩/一個(gè)元素
若此時(shí)序列數(shù)不是1個(gè)則將上述序列再次歸并,形成{displaystyle ceil(n/4)}個(gè)序列,每個(gè)序列包含四/三個(gè)元素
重復(fù)步驟2,直到所有元素排序完畢,即序列數(shù)為1
以上節(jié)選自維基百科
代碼如下:
</>復(fù)制代碼
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))
if left:
result += left
if right:
result += right
return result
def merge_sort(numberlist):
if len(numberlist) <= 1:
return numberlist
mid = len(numberlist) // 2
left = numberlist[:mid]
right = numberlist[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
六、快速排序
從數(shù)列中挑出一個(gè)元素,稱為“基準(zhǔn)”(pivot),
重新排序數(shù)列,所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面,所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面(相同的數(shù)可以到任何一邊)。在這個(gè)分割結(jié)束之后,該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分割(partition)操作。
遞歸地(recursively)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸到最底部時(shí),數(shù)列的大小是零或一,也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束,因?yàn)樵诿看蔚牡╥teration)中,它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
以上節(jié)選自維基百科
代碼如下:
</>復(fù)制代碼
def quick_sort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
七、堆排序
若以升序排序說(shuō)明,把數(shù)組轉(zhuǎn)換成最大堆積(Max-Heap Heap),這是一種滿足最大堆積性質(zhì)(Max-Heap Property)的二叉樹:對(duì)于除了根之外的每個(gè)節(jié)點(diǎn)i, A[parent(i)] ≥ A[i]。
重復(fù)從最大堆積取出數(shù)值最大的結(jié)點(diǎn)(把根結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)交換,把交換后的最后一個(gè)結(jié)點(diǎn)移出堆),并讓殘余的堆積維持最大堆積性質(zhì)。
</>復(fù)制代碼
def heap_sort(numberlist):
length = len(numberlist)
def sift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 <= end and numberlist[child] < numberlist[child + 1]:
child += 1
if numberlist[root] < numberlist[child]:
numberlist[root], numberlist[child] = numberlist[child], numberlist[root]
root = child
else:
break
# 創(chuàng)建最大堆
for start in range((length - 2) // 2, -1, -1):
sift_down(start, length - 1)
# 堆排序
for end in range(length - 1, 0, -1):
numberlist[0], numberlist[end] = numberlist[end], numberlist[0]
sift_down(0, end - 1)
return numberlist
八、計(jì)數(shù)排序
以上節(jié)選自維基百科
代碼如下:
</>復(fù)制代碼
def counting_sort(numberlist, maxnumber): # maxnumber為數(shù)組中的最大值
length = len(numberlist) # 待排序數(shù)組長(zhǎng)度
b = [0 for i in range(length)] # 設(shè)置輸出序列,初始化為0
c = [0 for i in range(maxnumber+ 1)] # 設(shè)置技術(shù)序列,初始化為0
for j in numberlist:
c[j] = c[j] + 1
for i in range(1, len(c)):
c[i] = c[i] + c[i - 1]
for j in numberlist:
b[c[j] - 1] = j
c[j] = c[j] - 1
return b
本文章參考維基百科和八大排序算法python實(shí)現(xiàn)合輯
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/45058.html
摘要:排序算法總結(jié)排序算法平均時(shí)間復(fù)雜度冒泡排序選擇排序插入排序希爾排序快速排序歸并排序堆排序基數(shù)排序一冒泡排序基本思想兩個(gè)數(shù)比較大小,較大的數(shù)下沉,較小的數(shù)冒起來(lái)。 排序算法總結(jié) 排序算法 平均時(shí)間復(fù)雜度 冒泡排序O(n2) 選擇排序O(n2) 插入排序O(n2) 希爾排序O(n1.5) 快速排序O(N*logN) 歸并排序O(N*logN) 堆排序O(N*logN) 基數(shù)排序O(d(n+...
摘要:是穩(wěn)定的排序方法。也稱縮小增量排序,是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。算法實(shí)現(xiàn)選擇排序堆排序描述堆排序是指利用堆積樹堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法,它是選擇排序的一種。 1、插入排序 描述 插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù),算法適用于少量數(shù)據(jù)的排序,時(shí)間復(fù)雜度為O(n^2)。是穩(wěn)定...
摘要:今天,一條就帶大家徹底跨過(guò)排序算法這道坎,保姆級(jí)教程建議收藏。利用遞歸算法,對(duì)分治后的子數(shù)組進(jìn)行排序。基本思想堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法,堆排序是一種選擇排序,它的最壞,最好,平均時(shí)間復(fù)雜度均為,它也是不穩(wěn)定排序。 ...
摘要:常見(jiàn)的八大排序算法,他們之間關(guān)系如下被人忽視的面向?qū)ο蟮牧笤瓌t后端掘金前言作為文集的第一篇,我覺(jué)得有必要介紹一下大概的寫作規(guī)劃。 Java多線程干貨系列—(四)volatile關(guān)鍵字| 掘金技術(shù)征文 - 掘金原本地址:Java多線程干貨系列—(四)volatile關(guān)鍵字博客地址:http://tengj.top/ 前言 今天介紹下volatile關(guān)鍵字,volatile這個(gè)關(guān)鍵字可能...
摘要:常見(jiàn)的八大排序算法,他們之間關(guān)系如下被人忽視的面向?qū)ο蟮牧笤瓌t后端掘金前言作為文集的第一篇,我覺(jué)得有必要介紹一下大概的寫作規(guī)劃。 Java多線程干貨系列—(四)volatile關(guān)鍵字| 掘金技術(shù)征文 - 掘金原本地址:Java多線程干貨系列—(四)volatile關(guān)鍵字博客地址:http://tengj.top/ 前言 今天介紹下volatile關(guān)鍵字,volatile這個(gè)關(guān)鍵字可能...
閱讀 1678·2021-11-12 10:35
閱讀 1620·2021-08-03 14:02
閱讀 2691·2019-08-30 15:55
閱讀 2034·2019-08-30 15:54
閱讀 770·2019-08-30 14:01
閱讀 2432·2019-08-29 17:07
閱讀 2259·2019-08-26 18:37
閱讀 3039·2019-08-26 16:51