# -*- coding: utf-8 -*-
def merge(array, start, middle, end):
n1 = middle - start + 1 # 第一個子序列長度
n2 = end - middle # 第二個子序列長度
left_array = []
right_array = []
for i in range(n1):
left_array.append(array[start + i])
for i in range(n2):
right_array.append(array[middle + i + 1])
left_array.append(float('Inf')) # float('Inf') 表示正無窮
right_array.append(float('Inf'))
i = j = 0
for index in range(start, end + 1):
if (left_array[i] <= right_array[j]):
array[index] = left_array[i]
i += 1
else:
array[index] = right_array[j]
j += 1
return array
def merge_sort(array, start, end):
if start < end:
middle = (start + end) // 2
merge_sort(array, start, middle)
merge_sort(array, middle + 1, end)
merge(array, start, middle, end)
array = [1, 9, 2, 6, 7, 8, 8, 7, 9, 11, 18, 12, 13]
merge_sort(array, 0, len(array) - 1)
print(array)
歸并排序
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來搏屑，“玉大人争涌，你說我怎么就攤上這事±绷担” “怎么了亮垫？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長抑党。 經(jīng)常有香客問我包警，道長，這世上最難降的妖魔是什么底靠？ 我笑而不...
- 正文 為了忘掉前任害晦，我火速辦了婚禮，結(jié)果婚禮上暑中，老公的妹妹穿的比我還像新娘壹瘟。我一直安慰自己，他們只是感情好鳄逾，可當(dāng)我...
- 文/花漫 我一把揭開白布稻轨。 她就那樣靜靜地躺著，像睡著了一般雕凹。 火紅的嫁衣襯著肌膚如雪殴俱。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼趴泌，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了拉庶？” 一聲冷哼從身側(cè)響起嗜憔，我...
- 正文 年R本政府宣布浪感，位于F島的核電站昔头，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏影兽。R本人自食惡果不足惜揭斧，卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望峻堰。 院中可真熱鬧讹开，春花似錦、人聲如沸捐名。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽镶蹋。三九已至成艘，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間贺归，已是汗流浹背淆两。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 選擇排序 對于任何輸入腹殿，時間為O(n*n)独悴； 冒泡排序 最優(yōu)（對于升序的數(shù)組，因為加入了一個跳出判斷）：O(n)锣尉，...
- 一般來說，這三者的時間復(fù)雜度O(NlogN)雨效，空間復(fù)雜度O(n)優(yōu)化后迅涮，空間復(fù)雜度均可為O(1)，如下文中的快排和...
- 轉(zhuǎn)載：http://blog.csdn.net/pzhtpf/article/details/7559943 一传透、...
