【算法筆記(五)】排序算法

算法筆記(五)

排序算法

• 算法筆記(五)
• 前言
• 一、冒泡排序
• • 1.什麼是冒泡排序
  • 2.實際需求
  • 3.代碼實作
• 二、選擇排序
• • 1.什麼是選擇排序
  • 2.需求規則
• 三.插入排序
• • 1.了解插入排序
  • 2.需求規則
  • 3.代碼實作
• 四.希爾排序
• • 1.什麼是希爾排序
  • 2.需求規則
  • 3.代碼實作
• 五.快速排序
• • 1.什麼是快速排序
  • 2.需求規則
  • 3.代碼示範
• 六.歸并排序
• • 1.什麼是歸并排序
  • 2.需求規則
  • 3.代碼展示
• 總結

前言

基礎資料結構告一段落，現在開始一起學習排序算法

一、冒泡排序

1.什麼是冒泡排序

冒泡排序(Bubble Sor)是把一組資料從左邊開始進行兩兩比較交換，小的放前面，大的放後面，通過反複比較一直到沒有資料需要交換為止。該排序方法由于很像水裡的泡泡，從水底冒出的小泡泡升到水面變成大的，展現了從小到大的排序過程(如圖所示)。

2.實際需求

(1)從隊首開始，兩兩比較數值，把大的往後交換，一直到隊尾，第一個最大值固定到最後。

(2)再從隊首開始，依次兩兩比較，把次最大放到倒數第二位置。

(3)依次循環比較，直到完成所有數的比較和交換，完成冒泡排序。

人工圖示示範

第一步，1=[9,0,6,5,3,10,36,2,1]清單傳入自定義函數bubblesort(), n=9。

第二步，i=0, j=0, s:[0]=9, s[1]=0, s[0]>s[1]為真， 則把0放前面9放後面;然後，9與6進行比較，6放前面9放後面; 9與5比較，5放前面9放後面; 9與3比較，3放前面9放後面；9與10比較，無須交換; 10 與36比較，無須交換位置; 36 與2比較，2放前面36放後面; 36與1比較，1放前面36放最後。第一次循環比較結果如圖4.2所示，最大的數36放到了最後。

第三步，i=1,j=0， s:[0]-0, s:[1]=6，0與6比較，無須交換位置: 6與5比較，5放前面6放後面: 6與3比較，3放前面6放後面； 6與9比較，無須交換位置: 9與10比較，無須交換位置:10與2比較，2放前面10放後面: 10與1比較，1放前面10放後面。第二次循環結束，如圖所示。

3.代碼實作

def bubblesort(s1):
    n = len(s1)
    for i in range(n):                           # 冒泡循環次數控制
        for j in range(n - i - 1):               # 冒泡循環一次，範圍往前面縮1
            if s1[j] > s1[j + 1]:
                c1 = s1[j]                       # 把大的賦給c1
                s1[j] = s1[j + 1]                # 把小的換到前一位
                s1[j + 1] = c1                   # 把c1賦給後一位


l1 = [9, 0, 6, 5, 3, 10, 36, 2, 1]
print("排序之前的順序", l1)
bubblesort(l1)
print("排序之後的順序", l1)

           

運作結果

二、選擇排序

1.什麼是選擇排序

選擇排序是另外一一種簡單的排序 方法。在資料集合裡，通過輪循環找到最小值，把它放到第一個位置，然後在剩餘的資料中再我最小值，放到第二個位置。以此類推，直到将所有值排序完成。

2.需求規則

(1)輸入n個數值的清單，開始0到n-1輪的循環。

(2) 每輪循環記住最小值的下标，目前循環結束， 把最小值放到最前面。

(3)接着進行下一 輪循環，把最小值下标進行标記， 最後把最小值放到目前輪循環開始的位置。

(4)一直到第n-1輪，結束所有最小值的選擇。

人工圖示

第一步，把清單s1傳入SeletSor(arr)自定義函數。

第二步 i = 0到5, j=i到S進行循環，每循環一次選擇一個最小值，放到循環的最前面，循環比較過程如圖

def selectsort(s1):
    n = len(s1)
    if n == 1:
        return 1
    for i in range(n):
        mid = i                                     # 獲得每次循環第一個比較值的下标
        for j in range(i, n - 1):                   # 每次循環裡尋找最小值
            if s1[mid] > s1[j + 1]:                 # 循環過程判斷最小值
                mid += 1                            # 獲得更小值的下标
        s1[i], s1[mid] = s1[mid], s1[i]             # 把最小的放到最前面


s1 = [3, 18, 0, 32, 2, 1]
print("排序之前：", s1)
selectsort(s1)
print("排序之後：", s1)
           

運作結果

三.插入排序

1.了解插入排序

插入排序(Insertion Sort)的原理是數列前而為排序完成的值，數列後面為未排序的值。取已

排序的值右邊第一個 未排序的值CI,與已經排序的值進行比較，當C1大于目前值時，把目前值向後

移動1位，繼續往前比較，當c小于目前值時，在目前位置插入Ci并把目前值向後移動1位，

完成一個循環的插入比較。接着進行下一輪的循環插入比較，一直 到所有未排序的值都完成插入

操作。第一次循環時，可以把數列第一。個值作為已經排序的數來看待，從第二個值開始進行插入

操作。

2.需求規則

(1)輸入n個數值的清單。

2)先進行下标是0和1的數值比較，把大的放後面，小的插入前面，第1輪插入比較結束。

(3)繼續選擇下标是2的數值和下标是1的數值進行比較，大的後移1位，小的放到臨時變量c中;然後繼續比較c1和下标是0的數值，大的後移1位，小的插入前面。

(4)依次比較插入，一直到n-1輪結束比較， 獲得最終排序結果。

人工圖示示範

3.代碼實作

def insertsort(arr):
    n = len(arr)
    if n == 1:
        return 1
    for i in range(1, n):
        c1 = arr[i]
        j = i
        while j > 0 and c1 < arr[j - 1]:
            arr[j] = arr[j - 1]
            j -= 1
        arr[j] = c1


l2 = [9, 3, 1, 5, 6]
print("排列前順序", l2)
insertsort(l2)
print("排列後的順序：", l2)
           

運作結果

四.希爾排序

1.什麼是希爾排序

希爾排序(Sel Sor)又叫作縮小增量排序算法，是插入排序的一種更高效的改進算法。

2.需求規則

希爾排序的基本思想是:在n個元素的數列裡，取增量spcn/數列開始值和增量尾值之間進行比較，小的放前面，大的放後面:把增量前後的數值都比較一遍， 然後增量數space減1,繼續從頭到尾做比較，并調整大小;一直到space=1,就完成了所有元素的大小調整和排序。

增量space的取法有各種方案。最初Shell提出取space=n//2向下取整，space =space//2 向下取整，直到increment=1。但由于直到最後一步，奇數位置的元素才會與偶數位置的元素進行比較，這祥使用這個序列的效率會很低。後來Knuth提出取spacen/3向下取整+1，還有人提出都取奇數也有人提出space互質。使用不同的序列會使希爾排序算法的性能有很大的差異。

人工示範圖

3.代碼實作

def sellsort(arr):
    n = len(arr)
    endi = 0                        # 最後修改下标
    if n == 1:
        return 1
    space = n // 3                  # 以清單中1/3作為增量
    while space > 0:
        for i in range(space):      # 控制一個變量循環space次
            key = arr[i]
            j = 0                   # 控制每個key元素在清單裡比較次數
            while i + (j + 1) * space < n:
                print(f'交換開始下标數{j},交換結束{i + (j + 1) * space}')
                if space > 1:
                    if arr[i + (j + 1) * space] < key:
                        arr[i + j * space] = arr[i + (j + 1) * space]
                        endi = i + (j + 1) * space
                else:               # 當增量為1時，相鄰元素比較并調整
                    if arr[j] > arr[j + 1]:
                        arr[j], arr[j + 1] = arr[j + 1], arr[j]
                j += 1
            if arr[i] != key:       # 必須考慮無需交換情況
                arr[endi] = key
        space -= 1


s1 = [18, 3, 0, 5, 2, 10, 7, 15, 38, 100]
print(f"排列前的為:{s1}")
sellsort(s1)
print(f"排列後的為:{s1}")
           

運作結果

五.快速排序

1.什麼是快速排序

快速排序(Quick Sort)是對冒泡排序的一種改進， 由C.A.R.Hoare在1960年提出。它的基本思想是:通過一輪排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，直到整個資料變成有序序列。分割時，先選擇一個元素作 為比較大小的基準(Pivot) 數。把數列裡小于Pivot 數的元素放到前面，大于Pivot數的元素放到後面。這個基準數可以任意取一一個， 一般取開始、結束或中間位置的一個元素。

由于該算法需要把不同部分的兩部分資料疊代縮小排序，是以采用了遞歸排序方法，通過空間換時間，實作快速排序。

2.需求規則

(1)選取清單最後一個數值作為基準數P, 把比P小的數放前面， 比P大的數放後面。

(2)分别對前面部分和後面部分的資料按照(1)的原則進行排列。

(3)一直到每部分的下标low==high,完成快速排序。

圖示示範

3.代碼示範

def movepivot(arr, low, hight):
    pivot = arr[hight]
    imove = (low - 1)
    for i in range(low, hight):
        if arr[i] <= pivot:
            imove += 1
            arr[imove], arr[i] = arr[i], arr[imove]
    arr[imove + 1], arr[hight] = arr[hight], arr[imove + 1]
    return imove + 1


def quicksort(arr, low, hight):
    if low < hight:
        pivot = movepivot(arr, low, hight)
        quicksort(arr, low, pivot - 1)
        quicksort(arr, pivot + 1, hight)


s1 = [10, 3, 28, 4, 12, 20]
print(f"排序前{s1}")
h = len(s1)
quicksort(s1, 0, h - 1)
print(f"排序後的結果{s1}")
           

結果如下

六.歸并排序

1.什麼是歸并排序

歸并排序(Merge Sort)是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。

2.需求規則

分治法先把數列分成相對均衡的兩部分n/2,

然後再把左邊的(eft) 子數列和右邊的(right)

的子數列再各分成兩部分:繼續如此等分，直到隻有一個元素。

等分過程采用遞歸方法，每分次， 在記憶體開辟臨時的記錄區域。所有元素分完後，開始大小比較歸并，從兩個元素比較歸并到n/比較歸并。

s1=[1,9,10,4,50,6,7,90,21,23,45],其數量長度為n=11

第一次分割， n//2=5，通過遞歸，把左邊left[:5]存儲到臨時空間，右邊right[:5]也如此。

第二次分制，把左邊lelt[:5]分别為 left1[:2]、right1[2:] 右邊right[5:]分割為left2[:7]、right2[7:]

第三次分割，在第二次分割的基礎上再分别遞歸分割。

第四次分割，完成了所有元素的分割，分割為最小單元1.

接下來對分割完成的各個數列進行并歸排序操作。

第一次并歸，分别完成1和9的比較合并、4和50的比較合并，在前面合并的基礎上生成了1、9、10、4、50子數組;同時完成了7和90比較合并、23和45比較合并。

第二次并歸，實作了1、4、9、10、50的比較和并歸，6、7、21、23、45、90的比較和并歸。

第三次并歸，實作了1、4、6、7、9、10、21、23、45、50、90所有元素的最終排序過程。

圖示示範

3.代碼展示

def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return merge(left, right)


def merge(left, right):
    r, l = 0, 0
    temp = []
    lmax = len(left)
    rmax = len(right)
    while l < lmax and r < rmax:
        if left[l] <= right[r]:
            temp.append(left[l])
            l += 1
        else:
            temp.append(right[r])
            r += 1
    temp += list(left[l:])
    temp += list(right[r:])
    return temp

s1 = [1,9,10,4,50,6,7,90,21,23,45]
print(f"排列之前為{s1}")
print(f"排列之後為{mergesort(s1)}")
           

運作結果如下

總結

到此，排序算法就結束了，大家可以點選這裡一起探讨吧，下章将帶上檢索算法的筆記