'''
1. 數(shù)據(jù)結(jié)構(gòu)和算法
排序算法（冒泡和歸并）和查找算法（順序和折半）
'''
def bubble_sort(origin_items, comp=lambda x, y: x > y):
"""?質(zhì)量冒泡排序(攪拌排序)"""
items = origin_items[:]
for i in range(len(items) - 1):
swapped = False
for j in range(len(items) - 1 - i):
if comp(items[j], items[j + 1]):
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if swapped:
swapped = False
for j in range(len(items) - 2 - i, i, -1):
if comp(items[j - 1], items[j]):
items[j], items[j - 1] = items[j - 1], items[j]
swapped = True
if not swapped:
break
return items
# 歸并排序（分治法）
def merger_sort(items, comp=lambda x, y: x <= y):
"""歸并排序"""
if len(items) < 2:
return items[:]
mid = len(items) // 2
left = merger_sort(items[:mid], comp)
right = merger_sort(items[mid:], comp)
# print(merge(left, right, comp))
print("this is left and right.")
print(left, right)
return merge(left, right, comp)
def merge(item1, item2, comp):
items = []
idx1, idx2 = 0, 0
while idx1 < len(item1) and idx2 < len(item2):
if comp(item1[idx1], item2[idx2]):
items.append(item1[idx1])
idx1 += 1
else:
items.append(item2[idx2])
idx2 += 1
items += item1[idx1:]
items += item2[idx2:]
# print(items)
return items
# 順序查找
def seq_search(items, key):
for index, num in enumerate(items):
if num == key:
return index
return -1
# 折半查找 有序數(shù)組中查找某一特定元素的搜索算法。
def bin_search(items, key):
start, end = 0, len(items) - 1
while start < end:
mid = (start + end) // 2
if key > items[mid]:
start = mid + 1
elif key < items[mid]:
end = mid - 1
else:
return mid
return -1
if __name__ == "__main__":
items_test = [2]
ls = [34, 12, 12, 4, 98, 5, 6]
# print(ls[:])
print(merger_sort(ls)) # [4, 5, 6, 12, 12, 34, 98]
python數(shù)據(jù)結(jié)構(gòu)和算法
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門怎憋，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人九昧，你說(shuō)我怎么就攤上這事绊袋。” “怎么了铸鹰？”我有些...
- 文/不壞的土叔 我叫張陵癌别，是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我蹋笼，道長(zhǎng)展姐，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任剖毯，我火速辦了婚禮圾笨，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘逊谋。我一直安慰自己擂达，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開(kāi)白布胶滋。 她就那樣靜靜地躺著板鬓，像睡著了一般悲敷。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上穗熬，一...
- 那天镀迂，我揣著相機(jī)與錄音，去河邊找鬼唤蔗。 笑死探遵，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的妓柜。 我是一名探鬼主播箱季，決...
- 文/蒼蘭香墨 我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼棍掐！你這毒婦竟也來(lái)了藏雏？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬(wàn)榮一對(duì)情侶失蹤作煌，失蹤者是張志新（化名）和其女友劉穎掘殴，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體粟誓，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡奏寨，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了鹰服。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片病瞳。...
- 正文 年R本政府宣布逗柴，位于F島的核電站，受9級(jí)特大地震影響顿肺，放射性物質(zhì)發(fā)生泄漏戏溺。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一挟冠、第九天 我趴在偏房一處隱蔽的房頂上張望于购。 院中可真熱鬧袍睡，春花似錦知染、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)嫌吠。三九已至，卻和暖如春掺炭，著一層夾襖步出監(jiān)牢的瞬間辫诅，已是汗流浹背。 一陣腳步聲響...
- 正文 我出身青樓者冤，卻偏偏與公主長(zhǎng)得像肤视，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子涉枫，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 將序列分解為單獨(dú)變量 我們有一個(gè)N個(gè)元素的元組或者序列邢滑，想要分解為N個(gè)單獨(dú)的變量 解決方案：任何序列或者可迭代的對(duì)...
- 上一篇文章為:→5.1.10小練習(xí) 數(shù)據(jù)結(jié)構(gòu)與算法（Python） Why困后？ 我們舉一個(gè)可能不太恰當(dāng)?shù)睦樱?如果...
- 上一篇文章為:→1.1.7Python內(nèi)置類型性能分析 數(shù)據(jù)結(jié)構(gòu) 我們?nèi)绾斡肞ython中的類型來(lái)保存一個(gè)班的學(xué)生...
- 上一篇文章為:→1.1.4算法效率衡量 算法分析 1.第一次嘗試的算法核心部分 時(shí)間復(fù)雜度： T(n) = O(n...
- 下午接待一位咨客，一進(jìn)咨詢室就開(kāi)始讓咨詢師幫忙找老公小腊，說(shuō)自己老公已經(jīng)離家出走一年多救鲤，至今未回。 問(wèn)報(bào)警了沒(méi)有秩冈，說(shuō)報(bào)...
