常見算法：
一、排序引入
1.排序與搜索
排序算法（英語：Sorting algorithm）是一種能將一串?dāng)?shù)據(jù)依照特定順序進(jìn)行排列的一種算法。
2.排序算法的穩(wěn)定性
穩(wěn)定性：穩(wěn)定排序算法會讓原本有相等鍵值的紀(jì)錄維持相對次序。
1 8 3 8 5 6 7 2
(4,1) (3,1) (3,7) (5,6)
(3,7)(3,1)
如果一個排序算法是穩(wěn)定的，當(dāng)有兩個相等鍵值的紀(jì)錄R和S，且在原本的列表中R出現(xiàn)在S之前，在排序過的列表中R也將會是在S之前。
不穩(wěn)定排序算法可能會在相等的鍵值中改變紀(jì)錄的相對次序
二、冒泡排序
1.什么是冒泡排序
冒泡排序（Bubble Sort）是一種簡單的排序算法。
它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。
遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
冒泡排序算法的工作原理如下：
比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
除了最后一個，所有的元素重復(fù)以上的步驟。
持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
2.冒泡排序的分析
交換過程：
3.冒泡排序的實現(xiàn)
def bubble_sort(alist):
# 外層循環(huán)控制比較幾輪
n = len(alist)
for j in range(n - 1):
# 內(nèi)存循環(huán)控制交換
# -j是不再換已經(jīng)排好的
for i in range(n - 1 - j):
# 若前一個比后一個大，則換
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
if __name__ == '__main__':
li = [33, 11, 26, 78, 3, 9, 40]
print(li)
bubble_sort(li)
print(li)
優(yōu)化有序的情況，最優(yōu)時間復(fù)雜度O(n)
def bubble_sort(alist):
# 外層循環(huán)控制比較幾輪
n = len(alist)
for j in range(n - 1):
# 定義計數(shù)器
count = 0
# 內(nèi)存循環(huán)控制交換
# -j是不再換已經(jīng)排好的
for i in range(n - 1 - j):
# 若前一個比后一個大，則換
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
# 計數(shù)器
count += 1
if count == 0:
return
4.時間復(fù)雜度
最優(yōu)時間復(fù)雜度：O(n)
最壞時間復(fù)雜度：O(n2)
穩(wěn)定性：穩(wěn)定
5.評價
優(yōu)點：穩(wěn)定，簡單
缺點：效率不很高，運(yùn)行時間較長
三、選擇排序
1.什么是選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。
選擇排序算法的工作原理如下：
首先在序列中找到最小或最大元素，存放到排序序列的前或后。
然后，再從剩余元素中繼續(xù)尋找最小或最大元素。
然后放到已排序序列的末尾。
以此類推，直到所有元素均排序完畢。
2.選擇排序的分析
排序過程：
3.選擇排序的實現(xiàn)
alist = [3, 11, 26, 26,7, 3, 9, 4]
選擇排序把數(shù)據(jù)當(dāng)成2部分
alist = [3, 11, 26, 26,7, 9, 4]
alist = [3, 4 11, 26, 26,7, 9]
怎么找到最小值？ 索引min = 0
最終min = 0
min = 1開始
min = 6
alist[1] alist[6]
def select_sort(alist):
n = len(alist)
# 外層控制比較幾輪
for j in range(n - 1):
min_index = j
# 內(nèi)層控制元素比較和更新索引
for i in range(j + 1, n):
# 進(jìn)行比較
if alist[min_index] > alist[i]:
# 更新索引
min_index = i
# 退出循環(huán)后，交換數(shù)據(jù)
alist[j], alist[min_index] = alist[min_index], alist[j]
if __name__ == '__main__':
li = [3, 11, 26, 26, 7, 3, 9, 4]
print(li)
select_sort(li)
print(li)
4.時間復(fù)雜度
最優(yōu)時間復(fù)雜度：O(n2)
最壞時間復(fù)雜度：O(n2)
穩(wěn)定性：不穩(wěn)定
5.評價
優(yōu)點：移動次數(shù)少
缺點：比較次數(shù)多
四、插入排序
1.什么是插入排序
插入排序（Insertion Sort）是一種簡單直觀的排序算法。
插入排序算法的工作原理如下：
構(gòu)建有序序列
在已排序序列中掃描未排序數(shù)據(jù)
找到相應(yīng)位置并插入
2.插入排序的分析
排序過程：
3.插入排序的實現(xiàn)
插入排序
def insert_sort(alist):
n = len(alist)
# 外層循環(huán)控制從右邊取多少元素
for j in range(1, n):
# i = [1，2，3...]
i = j
# 內(nèi)存循環(huán)
while i > 0:
if alist[i] < alist[i - 1]:
alist[i], alist[i - 1] = alist[i - 1], alist[i]
# 控制循環(huán)結(jié)束
i -= 1
else:
break
if __name__ == '__main__':
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
insert_sort(li)
print(li)
4.時間復(fù)雜度
最優(yōu)時間復(fù)雜度：O(n)
最壞時間復(fù)雜度：O(n2)
穩(wěn)定性：穩(wěn)定
5.評價
優(yōu)點：穩(wěn)定，比較快
缺點：比較次數(shù)不確定，數(shù)據(jù)量越大，該算法越渣
五、希爾排序
1.什么是希爾排序
希爾排序（Shell Sort）是插入排序的一種，也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。
希爾排序是非穩(wěn)定排序算法，是DL．Shell于1959年提出的。
希爾排序算法的工作原理如下：
把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序。
隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多。
當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。
2.希爾排序的分析
排序過程：
增量用gap代表，第一次增量3是將數(shù)據(jù)分3組
3.希爾排序的實現(xiàn)
def shellSort(nums):
# 設(shè)定步長
step = len(nums)/2
while step > 0:
for i in range(step, len(nums)):
# 類似插入排序, 當(dāng)前值與指定步長之前的值比較, 符合條件則交換位置
while i >= step and nums[i-step] > nums[i]:
nums[i], nums[i-step] = nums[i-step], nums[i]
i -= step
step = step/2
return nums
if __name__ == '__main__':
nums = [9,3,5,8,2,7,1]
print shellSort(nums)
"""
[1, 2, 3, 5, 7, 8, 9]
"""
4.時間復(fù)雜度
最優(yōu)時間復(fù)雜度：根據(jù)步長序列的不同而不同，最優(yōu)是1.3，根據(jù)數(shù)學(xué)運(yùn)算算出的gap
最壞時間復(fù)雜度：O(n2)
穩(wěn)定性：不穩(wěn)定
5.評價
優(yōu)點：平均時間短，數(shù)據(jù)移動少
缺點：不穩(wěn)定
六、快速排序
1.什么是快速排序
快速排序（Quicksort），又稱劃分交換排序（partition-exchange sort）。
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序。
整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
快速排序算法的工作原理如下：
從數(shù)列中挑出一個元素，稱為"基準(zhǔn)"（pivot）。
重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。
在這個分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
2.快速排序的分析
排序過程：
3.快速排序的實現(xiàn)
快排：first理解為第一個位置的索引，last是最后位置索引
def quick_sort(alist, first, last):
# 遞歸終止條件
if first >= last:
return
# 設(shè)置第一個元素為中間值
mid_value = alist[first]
# low指向
low = first
# high
high = last
# 只要low小于high就一直走
while low < high:
# high大于中間值，則進(jìn)入循環(huán)
while low < high and alist[high] >= mid_value:
# high往左走
high -= 1
# 出循環(huán)后，說明high小于中間值,low指向該值
alist[low] = alist[high]
# high走完了，讓low走
# low小于中間值，則進(jìn)入循環(huán)
while low < high and alist[low] < mid_value:
# low向右走
low += 1
# 出循環(huán)后，說明low大于中間值,high指向該值
alist[high] = alist[low]
# 退出整個循環(huán)后，low和high相等
# 將中間值放到中間位置
alist[low] = mid_value
# 遞歸
# 先對左側(cè)快排
quick_sort(alist, first, low - 1)
# 對右側(cè)快排
quick_sort(alist, low + 1, last)
if __name__ == '__main__':
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)
4.時間復(fù)雜度
最優(yōu)時間復(fù)雜度：O(nlogn)
遍歷每個數(shù)是O(n)，訪問每個數(shù)是O(logn)，最終是O(nlogn)
可以轉(zhuǎn)換為求二叉樹深度的思想
最壞時間復(fù)雜度：O(n2)
穩(wěn)定性：不穩(wěn)定
5.評價
優(yōu)點：效率高，數(shù)據(jù)移動比較少，數(shù)據(jù)量越大，優(yōu)勢越明顯
缺點：不穩(wěn)定
七、歸并排序
1.什么是歸并排序
歸并排序（MergeSort）是采用分治法的一個非常典型的應(yīng)用。
歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。
歸并排序算法的工作原理如下：
將數(shù)組分解最小之后，然后合并兩個有序數(shù)組。
比較兩個數(shù)組的最前面的數(shù)，誰小就先取誰，取了后相應(yīng)的指針就往后移一位。
然后再比較，直至一個數(shù)組為空，最后把另一個數(shù)組的剩余部分復(fù)制過來即可。
2.歸并排序的分析
排序過程：
3.歸并排序的實現(xiàn)
歸并排序
def merge_sort(alist):
n = len(alist)
# 遞歸結(jié)束條件
if n <= 1:
return alist
# 中間位置
mid = n // 2
# 遞歸拆分左側(cè)
left_li = merge_sort(alist[:mid])
# 遞歸拆分右側(cè)
right_li = merge_sort(alist[mid:])
# 需要2個游標(biāo)，分別指向左列表和右列表第一個元素
left_point, right_point = 0, 0
# 定義最終返回的結(jié)果集
result = []
# 循環(huán)合并數(shù)據(jù)
while left_point < len(left_li) and right_point < len(right_li):
# 誰小誰放前面
if left_li[left_point] <= right_li[right_point]:
# 放進(jìn)結(jié)果集
result.append(left_li[left_point])
# 游標(biāo)移動
left_point += 1
else:
result.append(right_li[right_point])
right_point += 1
# 退出循環(huán)時，形成左右兩個序列
result += left_li[left_point:]
result += right_li[right_point:]
return result
if __name__ == '__main__':
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
sort_li = merge_sort(li)
print(li)
print(sort_li)
4.時間復(fù)雜度
最優(yōu)時間復(fù)雜度：O(nlogn)
最壞時間復(fù)雜度：O(nlogn)
穩(wěn)定性：穩(wěn)定
5.評價
優(yōu)點：穩(wěn)定，數(shù)據(jù)量越大越優(yōu)秀
缺點：需要額外空間
6.常見算法的效率比較
快速排序消耗空間因為每次遞歸時，要保持一些數(shù)據(jù)
最優(yōu)情況：每一次平均分組的情況 O(logn)
最壞情況：退化為冒泡排序的情況 O(n)
堆排序是結(jié)合二叉樹去做的
八、搜索
1.搜索引入
搜索是在一個數(shù)據(jù)集合中找到一個特定數(shù)據(jù)的算法
搜索通常的答案是真的或假的
搜索的常見方法有二分查找、哈希查找等
2.二分法查找
二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好。
缺點是要求待查表為有序表
因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。
二分查找的工作原理如下：
首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功。
否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。
重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
3.二分查找的實現(xiàn)
遞歸實現(xiàn)
非遞歸實現(xiàn)
遞歸的實現(xiàn)
def my_search(alist, item):
n = len(alist)
# 遞歸結(jié)束條件
if n > 0:
# 折半
mid = n // 2
# 判斷中間元素是否為要查的元素
if alist[mid] == item:
return True
# 判斷中間元素與item的大小
elif item < alist[mid]:
# 繼續(xù)遞歸查找
return my_search(alist[:mid], item)
else:
return my_search(alist[mid + 1:], item)
return False
非遞歸實現(xiàn)
def my_search2(alist, item):
n = len(alist)
# 起始，0
first = 0
# 結(jié)束位置
last = n - 1
while first <= last:
# 折半
mid = (first + last) // 2
# 判斷中間元素
if alist[mid] == item:
return True
elif item < alist[mid]:
last = mid - 1
else:
first = mid + 1
return False
if __name__ == '__main__':
# 2個注意點：必須用有序的順序表
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
print(my_search(li, 17))
print(my_search2(li, 111))
4.時間復(fù)雜度
最優(yōu)時間復(fù)雜度：O(1)
最壞時間復(fù)雜度：O(logn)
總結(jié)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
