jlzzjlzz亚洲乱熟在线播放

系統城裝機大師 - 唯一官網:www.farandoo.com!

當前位置:首頁 > 腳本中心 > python > 詳細頁面

Python實現七個基本算法的實例代碼

時間:2020-10-08來源:www.farandoo.com作者:電腦系統城

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)”的元素組成的)分別進行直接插入排序,然后依次縮減增量再進行排序,待整個序列中的元素基本有序(增量足夠?。r,再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下(接近最好情況),效率是很高的,因此希爾排序在時間效率比直接插入排序有較大提高。

?
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 result
 
alist = [3,8,5,7,6]
print(merge_sort(alist))

8.各個算法的時間復雜度

到此這篇關于Python實現七個基本算法的實例代碼的文章就介紹到這了,

分享到:

相關信息

系統教程欄目

欄目熱門教程

人氣教程排行

站長推薦

熱門系統下載