1.順序查找
-
當資料存盤在諸如串列的集合中時，我們說這些資料具有線性或順序關系， 每個資料元素都存盤在相對于其他資料元素的位置， 由于這些索引值是有序的，我們可以按順序訪問它們， 這個程序產實作的搜索即為順序查找，
-
順序查找原理剖析：從串列中的第一個元素開始，我們按斬訓本的順序排序，簡單地從一個元素移動到另一個元素，直到找到我們正在尋找的元素或遍歷完整個串列，如果我們遍歷完整個串列，則說明正在搜索的元素不存在，
-
代碼實作：該函式需要一個串列和我們正在尋找的元素作為引數，并回傳一個是否存在的布林值，found 布爾變數初始化為 False，如果我們發現串列中的元素，則賦值為 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.二分查找
-
有序串列對于我們的實作搜索是很有用的，在順序查找中，當我們與第一個元素進行比較時，如果第一個元素不是我們要查找的，則最多還有 n-1 個元素需要進行比較，
-
二分查找則是從中間元素開始，而不是按順序查找串列， 如果該元素是我們正在尋找的元素，我們就完成了查找， 如果它不是，我們可以使用串列的有序性質來消除剩余元素的一半，
如果我們正在查找的元素大于中間元素，就可以消除中間元素以及比中間元素小的一半元素，如果該元素在串列中，肯定在大的那半部分，然后我們可以用大的半部分重復該程序，繼續從中間元素開始，將其與我們正在尋找的內容進行比較，
#Python學習交流群：778463939
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.冒泡排序
原理：
- 比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，
- 對每一對相鄰元素做同樣的作業，從開始第一對到結尾的最后一對，在這一點，最后的元素應該會是最大的數，
- 針對所有的元素重復以上的步驟，除了最后一個，
- 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，
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.選擇排序
作業原理：第一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾，以此類推，直到全部待排序的資料元素的個數為零，選擇排序是不穩定的排序方法，
#Python學習交流群：778463939
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.插入排序
原理：
基本思想是，每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的檔案中適當位置上，直到全部插入完為止，關鍵碼是資料元素中某個資料項的值，用它可以標示一個資料元素，
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）”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序，因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率比直接插入排序有較大提高，
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.快速排序
基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列，
#Python學習交流群：778463939
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）的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，
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 result
alist = [3,8,5,7,6]
print(merge_sort(alist))
8.各個演算法的時間復雜度
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/162318.html
標籤：Python
上一篇：1. Spring Boot入門
下一篇：19道Python練習題