程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

Python算法實踐Week5-排序算法

編輯:Python

0x01 選擇排序

排序是計算機最為常見的操作之一,排序就是將一組雜亂無章的數據按照一定的規律排序起來(遞增或遞減),排序的對象可以是數字型,也可以是字符型(按照ASCII碼的順序排列)

  • 選擇排序(升序) 每次在若干無序數據中查找最小數,放在無序數據的首位
    • N個元素的列表中找最小值及下標,與第一個元素交換
    • 從第二個元素開始的N-1個元素中找出最小值及其下標,與第二個元素交換
    • 以此類推,N-1輪後即為排好序的數據
  • 選擇排序算法的實現
# 選擇排序
list = [49, 38, 65, 97, 76, 13, 27, 49]
for i in range(len(list) - 1):
m = i
for j in range(i + 1, len(list)):
if list[j] < list[m]:
m = j
list[i], list[m] = list[m], list[i]
print(list)
  • 算法分析 選擇排序共需比較N-1輪,總共比較的輪數為(N-1)+(N-2)+...+2+1=N(N-1)/2

選擇排序執行交換的次數是N-1

0x02 冒泡排序

  • 算法思想
    • 第一輪比較:從第一個元素開始,按照順序對列表中所有N個元素中連續的兩個元素進行兩兩比較,如果兩者不滿足升序關系則交換。第一輪比較過後,最大數將下沉到列表最後。
    • 第二輪比較:從第一個元素開始,對列表中前N-1個元素之間進行兩兩比較,使第二大的數字沉到最後
    • 以此類推,N-1輪後,排序完畢
  • 冒泡排序算法的實現
list = [77, 42, 35, 10, 22, 101, 5]
for i in range(len(list) - 1):
for j in range(len(list) - 1 - i):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
print(list)
  • 冒泡排序算法的改進 如果在某一輪的比較中,一次交換也沒有執行過,就說明已經排好序了
# 改進
list = [77, 42, 35, 10, 22, 101, 5]
for i in range(len(list) - 1):
flag = True
for j in range(len(list) - 1 - i):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
flag = False
if flag:
break
print(list)
  • 冒泡算法的分析
    • 算法主要時間消耗是比較的次數
    • 冒泡算法共需比較N-1輪,總共比較次數為(N-1)+(N-2)+...+2+1=N(N-1)/2
    • 冒泡排序執行交換的次數不確定
    • 冒泡排序是一種執行效率很低的排序算法

0x03 函數、遞歸

  • 函數的好處
    • 在程序中分離不同的任務
    • 實現結構化程序設計
    • 減少程序復雜度
    • 實現代碼的復用
    • 提高代碼的質量
    • 協作開發
    • 實現特殊功能(遞歸)
    • .......
  • Python中函數的分類
    • 內置函數 input()、print()、int()、float()、len()、max()等
    • 標准庫函數 math包中的sqrt()、sin()、cos();random包中的random()等
    • 第三方庫函數
    • 自定義庫函數
  • 函數
# 自定義函數的定義
def 函數名([形參列表]):
函數體
# 函數的調用
函數名([實參列表])
# 例子:定義一個求平均值的函數
def average(a, b):
return (a + b / 2)
temp = average(1, 3)
print(temp)
  • 問題:編寫一個函數判斷一個數是否為素數,並調用其輸出200以內的素數
import math
def isPrime(a):
m = int(math.sqrt(a))
for i in range(2, m + 1):
if a % i == 0:
return False
return True
for i in range(2, 200):
if isPrime(i):
print(i)
  • 問題:將冒泡排序算法寫成函數形式
def bubbleSort(a):
for i in range(len(a) - 1):
for j in range(len(a) - 1 - i):
if a[j] > a[i]:
a[j], a[i] = a[i], a[j]
list = [77, 42, 35, 10, 22, 101, 5]
bubbleSort(list)
print(list)
  • 遞歸函數 自調用函數,在函數體內部直接或間接調用自己
# 非遞歸方法
def factorial(n):
s = 1
for i in range(1, n + 1):
s = s * i
return s
# 遞歸方法
def factorial(n):
if n == 1:
return 1
else:
s = n * factorial(n - 1)
return s
print(factorial(3))

0x04 歸並排序

  • 算法思想
    • 將包含N個元素的列表拆分成兩個含N/2個元素的子列表
    • 對兩個子列表遞歸調用歸並排序(最後可將整個列表分為N個子列表)
    • 合並兩個已經排序好的子列表
  • 歸並排序算法的實現
def merge(left, right): # 合並兩個列表
merged = []
i, j = 0, 0 # i和j分別作為left和right的下標
left_len, right_len = len(left), len(right) # 分別獲取左右列表的長度
while i < left_len and j < right_len: # 循環歸並左右子列表元素
if left[i] <= right[j]:
merged.append(left[i]) # 歸並左子列表元素
i += 1
else:
merged.append(right[j]) # 歸並右子列表元素
j += 1
merged.extend(left[i:]) # 歸並左子列表剩余元素
merged.extend(right[j:]) # 歸並右子列表剩余元素
print(left, right, merged) # 跟蹤調試
return merged # 返回歸並好的列表
def mergeSort(a): # 歸並排序
if len(a) <= 1: # 空或者只有一個元素,直接返回列表
return a
mid = len(a) // 2 # 列表中間位置
left = mergeSort(a[:mid]) # 歸並排序左子列表
right = mergeSort(a[mid:]) # 歸並排序右子列表
return merge(left, right) # 合並排好序的左右兩個子列表
a = [98, 23, 11, 10, 33, 42]
temp = mergeSort(a)
print(temp)

python語言系統提供的排序算法,底層就采用了歸並排序算法實現

a = sorted([24, 8, 10, 35])
print(a)
# [8, 10, 24, 35]
a.sort(reverse=True)
print(a)
# [35, 24, 10, 8]
b = sorted(a)
print(b)
# [8, 10, 24, 35]
c = sorted(a, reverse=True)
print(c)
# [35, 24, 10, 8]

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved