2021-01-02

Python selection sort 選擇排序法

本篇 ShengYu 介紹排序法中的選擇排序法 selection sort，並且由 Python 來實作選擇排序法 selection sort。

選擇排序法 selection sort 基本原理

選擇排序法 selection sort 的原理是先在所有資料中挑選出一個最小的數值放在放在第一個，再從第二個到尾端的資料中挑選出一個最小的數值放在第二個，這樣一直迭代下去，最終將能獲得排序好的升序串列(由小到大)，
讓我來舉個簡單的例子吧！假如今天有一串數字串列 5,4,3,1,2 要使用選擇排序 selection sort，

第一次迴圈排序結果如下，所以第一次迴圈就從全部資料挑選出最小的數值 1 給交換放到第一個了，剩餘要排序的數值還有 4 個，

1,4,3,5,2

第二次迴圈排序結果如下，第二次迴圈就從第二個到尾端挑選出最小的數值 2 給交換放到第二個了，剩餘要排序的數值還有 3 個，

1,2,3,5,4

第三次迴圈排序結果如下，第三次迴圈就從第三個到尾端挑選出最小的數值 3 給交換放到第三個了，剩餘要排序的數值還有 2 個，

1,2,3,5,4

第四次迴圈排序結果如下，第四次迴圈就從第四個到尾端挑選出最小的數值 4 給交換放到第四個了，剩餘要排序的數值還有 1 個，

1,2,3,4,5

迴圈結束，排序完成，

Python 實作選擇排序法 selection sort

由上述的簡單例子推演可以了解了選擇排序 selection sort 基本原理後，接著就開始練習用 Python 來寫程式，那我們來看看 Python 選擇排序怎麼寫吧！

python3-selection-sort.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def bubble_sort(nums):
    n = len(nums)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        # swap
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
            
nums = [5,4,3,1,2]
print("排序前 = %s" % nums)
bubble_sort(nums)
print("排序後 = %s" % nums)

Python 程式跑出來的結果如下，經過選擇排序法 selection sort 排序後的結果的確是由小排到大。

1 2	排序前 = [5, 4, 3, 1, 2] 排序後 = [1, 2, 3, 4, 5]