您好,登錄后才能下訂單哦!
1.順序查找
當(dāng)數(shù)據(jù)存儲(chǔ)在諸如列表的集合中時(shí),我們說(shuō)這些數(shù)據(jù)具有線(xiàn)性或順序關(guān)系。 每個(gè)數(shù)據(jù)元素都存儲(chǔ)在相對(duì)于其他數(shù)據(jù)元素的位置。 由于這些索引值是有序的,我們可以按順序訪問(wèn)它們。 這個(gè)過(guò)程產(chǎn)實(shí)現(xiàn)的搜索即為順序查找。
順序查找原理剖析:從列表中的第一個(gè)元素開(kāi)始,我們按照基本的順序排序,簡(jiǎn)單地從一個(gè)元素移動(dòng)到另一個(gè)元素,直到找到我們正在尋找的元素或遍歷完整個(gè)列表。如果我們遍歷完整個(gè)列表,則說(shuō)明正在搜索的元素不存在。
代碼實(shí)現(xiàn):該函數(shù)需要一個(gè)列表和我們正在尋找的元素作為參數(shù),并返回一個(gè)是否存在的布爾值。found 布爾變量初始化為 False,如果我們發(fā)現(xiàn)列表中的元素,則賦值為 True。
def search(alist,item): find = False cur = 0 while cur < len(alist): if alist[cur] == item: find = True break else: cur += 1 return find
2.二分查找
有序列表對(duì)于我們的實(shí)現(xiàn)搜索是很有用的。在順序查找中,當(dāng)我們與第一個(gè)元素進(jìn)行比較時(shí),如果第一個(gè)元素不是我們要查找的,則最多還有 n-1 個(gè)元素需要進(jìn)行比較。
二分查找則是從中間元素開(kāi)始,而不是按順序查找列表。 如果該元素是我們正在尋找的元素,我們就完成了查找。 如果它不是,我們可以使用列表的有序性質(zhì)來(lái)消除剩余元素的一半。
如果我們正在查找的元素大于中間元素,就可以消除中間元素以及比中間元素小的一半元素。如果該元素在列表中,肯定在大的那半部分。然后我們可以用大的半部分重復(fù)該過(guò)程,繼續(xù)從中間元素開(kāi)始,將其與我們正在尋找的內(nèi)容進(jìn)行比較。
def search(alist,item): left = 0 right = len(alist) - 1 find = False while left <= right: mid_index = (left + right)//2 if item == alist[mid_index]: find = True break else: if item > alist[mid_index]: left = mid_index + 1 else: right = mid_index -1 return find
3.冒泡排序
原理:
比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。對(duì)每一對(duì)相鄰元素做同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn),最后的元素應(yīng)該會(huì)是最大的數(shù)。針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。
def sort(alist): length = len(alist) for i in range(0,length-1): for j in range(0,length-1-i): if alist[i] > alist[i+1]: alist[i],alist[i+1] = alist[i+1],alist[i]
4.選擇排序
工作原理:第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素,存放在序列的起始位置,然后再?gòu)氖S嗟奈磁判蛟刂袑ふ业阶钚。ù螅┰?,然后放到已排序的序列的末尾。以此?lèi)推,直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。
def sort(alist): length = len(alist) for j in range(length-1,0,-1): max_index = 0 for i in range(1,j+1): if alist[max_index] < alist[i]: max_index = i alist[max_index],alist[j] = alist[j],alist[max_index]
5.插入排序
原理:
基本思想是,每步將一個(gè)待排序的記錄,按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上,直到全部插入完為止。關(guān)鍵碼是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值,用它可以標(biāo)示一個(gè)數(shù)據(jù)元素。
def sort(alist): length = len(alist) for j in range(1,length): i = j while i > 0: if alist[i] < alist[i-1]: alist[i],alist[i-1] = alist[i-1],alist[i] i -= 1 else: break
希爾排序(Shell's Sort)是插入排序的一種又稱(chēng)“縮小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
該方法的基本思想是:先將整個(gè)待排元素序列分割成若干個(gè)子序列(由相隔某個(gè)“增量(gap)”的元素組成的)分別進(jìn)行直接插入排序,然后依次縮減增量再進(jìn)行排序,待整個(gè)序列中的元素基本有序(增量足夠?。r(shí),再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下(接近最好情況),效率是很高的,因此希爾排序在時(shí)間效率比直接插入排序有較大提高。
def sort(alist): gap = len(alist)//2 while gap >= 1: for j in range(gap,len(alist)): i = j while i > 0: if alist[i] < alist[i-gap]: alist[i],alist[i-gap] = alist[i-gap],alist[i] i -= gap else: break gap = gap // 2
6.快速排序
基本思想是:通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過(guò)程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
def sort(alist,start,end): low = start high = end if low >= high: return mid = alist[low] while low < high: while low < high: if alist[high] >= mid: high -= 1 else: alist[low] = alist[high] break while low < high: if alist[low] < mid: low += 1 else: alist[high] = alist[low] break alist[low] = mid sort(alist,start,low-1) sort(alist,high+1,end)
7.歸并排序
歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并,得到完全有序的序列;即先使每個(gè)子序列有序,再使子序列段間有序。
def merge_sort(alist): n = len(alist) #結(jié)束遞歸的條件 if n <= 1: return alist #中間索引 mid = n//2 left_li = merge_sort(alist[:mid]) right_li = merge_sort(alist[mid:]) #指向左右表中第一個(gè)元素的指針 left_pointer,right_pointer = 0,0 #合并數(shù)據(jù)對(duì)應(yīng)的列表:該表中存儲(chǔ)的為排序后的數(shù)據(jù) result = [] while left_pointer < len(left_li) and right_pointer < len(right_li): #比較最小集合中的元素,將最小元素添加到result列表中 if left_li[left_pointer] < right_li[right_pointer]: result.append(left_li[left_pointer]) left_pointer += 1 else: result.append(right_li[right_pointer]) right_pointer += 1 #當(dāng)左右表的某一個(gè)表的指針偏移到末尾的時(shí)候,比較大小結(jié)束,將另一張表中的數(shù)據(jù)(有序)添加到result中 result += left_li[left_pointer:] result += right_li[right_pointer:] return result alist = [3,8,5,7,6] print(merge_sort(alist))
8.各個(gè)算法的時(shí)間復(fù)雜度
到此這篇關(guān)于Python實(shí)現(xiàn)七個(gè)基本算法的實(shí)例代碼的文章就介紹到這了,更多相關(guān)Python基本算法內(nèi)容請(qǐng)搜索億速云以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持億速云!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。