1.順序查找
當數據存儲在諸如列表的集合中時，我們說這些數據具有線性或順序關系。 每個數據元素都存儲在相對于其他數據元素的位置。 由于這些索引值是有序的，我們可以按順序訪問它們。 這個過程產實現的搜索即為順序查找。
順序查找原理剖析：從列表中的第一個元素開始，我們按照基本的順序排序，簡單地從一個元素移動到另一個元素，直到找到我們正在尋找的元素或遍歷完整個列表。如果我們遍歷完整個列表，則說明正在搜索的元素不存在。
代碼實現：該函數需要一個列表和我們正在尋找的元素作為參數，并返回一個是否存在的布爾值。found 布爾變量初始化為 False，如果我們發現列表中的元素，則賦值為 True。
|
1
2
3
4
5
6
7
8
9
10
|
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.二分查找
有序列表對于我們的實現搜索是很有用的。在順序查找中，當我們與第一個元素進行比較時，如果第一個元素不是我們要查找的，則最多還有 n-1 個元素需要進行比較。
二分查找則是從中間元素開始，而不是按順序查找列表。 如果該元素是我們正在尋找的元素，我們就完成了查找。 如果它不是，我們可以使用列表的有序性質來消除剩余元素的一半。
如果我們正在查找的元素大于中間元素，就可以消除中間元素以及比中間元素小的一半元素。如果該元素在列表中，肯定在大的那半部分。然后我們可以用大的半部分重復該過程，繼續從中間元素開始，將其與我們正在尋找的內容進行比較。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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.冒泡排序
原理：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。針對所有的元素重復以上的步驟，除了最后一個。持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
|
1
2
3
4
5
6
|
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.選擇排序
工作原理：第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。選擇排序是不穩定的排序方法。
|
1
2
3
4
5
6
7
8
|
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.插入排序
原理：
基本思想是，每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。關鍵碼是數據元素中某個數據項的值，用它可以標示一個數據元素。
|
1
2
3
4
5
6
7
8
9
10
|
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)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。
該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量（gap）”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率比直接插入排序有較大提高。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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.快速排序
基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
def merge_sort(alist): n = len(alist) #結束遞歸的條件 if n <= 1: return alist #中間索引 mid = n//2 left_li = merge_sort(alist[:mid]) right_li = merge_sort(alist[mid:]) #指向左右表中第一個元素的指針 left_pointer,right_pointer = 0,0 #合并數據對應的列表：該表中存儲的為排序后的數據 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 #當左右表的某一個表的指針偏移到末尾的時候，比較大小結束，將另一張表中的數據（有序）添加到result中 result += left_li[left_pointer:] result += right_li[right_pointer:] return resultalist = [3,8,5,7,6]print(merge_sort(alist)) |
8.各個算法的時間復雜度
到此這篇關于Python實現七個基本算法的實例代碼的文章就介紹到這了,更多相關Python基本算法內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://www.cnblogs.com/xxpythonxx/archive/2020/10/07/13778790.html
