1、冒泡排序 - 實現(xiàn)列表[5, 3, 4, 7, 2]排序:
# 冒泡法實現(xiàn)列表排序
def bubble_sort(alist):
"""冒泡排序"""
# 數(shù)列的長度
n = len(alist)
# 控制比較輪數(shù)
for j in range(0, n - 1):
# 計數(shù)
count = 0
# 控制每一輪的比較次數(shù)
for i in range(0, n - j - 1):
# 比較相鄰的；兩個數(shù)字，不符合要求交換位置
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
count += 1
# 如果遍歷一遍發(fā)現(xiàn)沒有數(shù)字交換，退出循環(huán)，證明數(shù)列有序
if count == 0:
break
if __name__ == '__main__':
alist = [5, 3, 4, 7, 2]
bubble_sort(alist)
print(alist)
- 冒泡排序運行結(jié)果：
冒泡排序運行結(jié)果.png
2、選擇排序 - 實現(xiàn)列表[1, 3, 4, 10, 0, 1000, 88]排序：
def select_sort(alist):
"""選擇排序"""
# 列表的長度
n = len(alist)
# 控制比價輪數(shù)
for j in range(0, n - 1):
# 假定的最小值的下標(biāo)
min_index = j
# 控制比較次數(shù)
for i in range(j + 1, n):
# 進(jìn)行比較獲得最小值
if alist[i] < alist[min_index]:
min_index = i
# 如果假定的最小值下標(biāo)發(fā)生了變化，那么就進(jìn)行交換
if min_index != j:
alist[j], alist[min_index] = alist[min_index], alist[j]
if __name__ == '__main__':
alist = [1, 3, 4, 10, 0, 1000, 88]
select_sort(alist)
print(alist)
- 選擇排序運行結(jié)果：
選擇排序運行結(jié)果.png
3、插入排序 - 實現(xiàn)列表[1, 100, 99, 20, 5, 1000]排序：
def insert_sort(alist):
"""插入排序"""
# 列表的長度
n = len(alist)
# 控制輪數(shù)
for j in range(1, n):
# [j, j-1, j-2, ……，,1]
# 找到合適的位置安放我們的無序的數(shù)據(jù)
for i in range(j, 0, -1):
if alist[i] < alist[i - 1]:
alist[i], alist[i - 1] = alist[i - 1], alist[i]
else:
break
if __name__ == '__main__':
alist = [1, 100, 99, 20, 5, 1000]
print("原來的列表：", alist)
insert_sort(alist)
print("排序后的列表：", alist)
- 插入排序運行結(jié)果：
插入排序運行結(jié)果.png
4、快速排序 - 實現(xiàn)列表[1, 3, 100, 50, 1000, 0, 1, 1]排序：
def quick_sort(alist, start, end):
"""快速排序"""
# 遞歸的結(jié)束條件
if start >= end:
return
# 界限值
mid = alist[start]
# 左右游標(biāo)
left = start
right = end
while left < right:
# 從右邊開始找尋小于mid的值 歸類到左邊
while alist[right] >= mid and left < right:
right -= 1
alist[left] = alist[right]
# 從左邊開始找尋大于mid的值 歸類到左邊
while alist[left] < mid and left < right:
left += 1
alist[right] = alist[left]
# 循環(huán)一旦結(jié)束了 證明找到了mid應(yīng)該在的位置
alist[left] = mid
# 遞歸操作
quick_sort(alist, start, left - 1)
quick_sort(alist, right + 1, end)
if __name__ == '__main__':
aist = [1, 3, 100, 50, 1000, 0, 1, 1]
quick_sort(aist, 0, len(aist) - 1)
print(aist)
- 快速排序運行結(jié)果：
快速排序運行結(jié)果.png
5、二分查找（1）遞歸法 - 查找元素是否在列表[1, 3, 6, 31, 100]中：
def binary_search(alist, item):
"""二分查找"""
# 獲取數(shù)列的長度
n = len(alist)
# 遞歸的結(jié)束條件
if n == 0:
return False
# 中間值
mid = n // 2
if item == alist[mid]:
return True
elif item < alist[mid]:
return binary_search(alist[0:mid], item)
elif item > alist[mid]:
return binary_search(alist[mid + 1:], item)
else:
return False
if __name__ == '__main__':
alist = [1, 3, 6, 31, 100]
print('31是否在列表[1, 3, 6, 31, 100]：', binary_search(alist, 31))
print('32是否在列表[1, 3, 6, 31, 100]：', binary_search(alist, 32))
- 二分查找遞歸法運行結(jié)果：
二分查找遞歸法運行結(jié)果.png
6、二分查找（2）非遞歸法 - 查找元素是否在列表[1, 3, 6, 31, 100]中：
def binary_search(alist, item):
"""二分查找"""
# 設(shè)置起始位置 獲取中間值
start = 0
end = len(alist) - 1
while start <= end:
# 中間值
mid = (start + end) // 2
if item == alist[mid]:
return True
elif item < alist[mid]:
end = mid - 1
elif item > alist[mid]:
start = mid + 1
# 沒有找到想要的數(shù)字
return False
if __name__ == '__main__':
alist = [1, 2, 3, 4, 5]
print('1是否在列表[1, 2, 3, 4, 5]中：', binary_search(alist, 1))
print('100是否在列表[1, 2, 3, 4, 5]中：', binary_search(alist, 100))
- 二分查找非遞歸法運行結(jié)果：
二分查找非遞歸法運行結(jié)果：.png
