---
# System prepended metadata

title: 選擇排序法

---

## 選擇排序法
### 記憶體運作
![](https://hackmd.io/_uploads/ByVnd9sBn.png)
1. 每一個元素儲存時會有一個地址
2. 若是多個元素時就可以使用**陣列**或者**鏈結串列**的方法

### 陣列 & 鏈結串列
1. 陣列
連續存入記憶體中
![](https://hackmd.io/_uploads/BJZvt9sHn.png)
若是位置不夠時
![](https://hackmd.io/_uploads/Bku3FcjB3.png)
* 重新找尋記憶體位置，並將整組陣列搬過去
* 先預佔位置
  * 浪費空間
  * 若是超過，就必須再次移動

2. 鏈結串列
存放元素同時，也紀錄下一個元素的存放位置
![](https://hackmd.io/_uploads/S1U-i5oBh.png)

#### 陣列 & 鏈結串列的優缺點
* 鏈結串列必須逐一讀取元素但陣列可以隨機讀取
![](https://hackmd.io/_uploads/Sk0gUsjHn.png)

### 資料存取方式
1. 循序存取（鏈結串列）
2. 隨機存取（陣列：使用索引存取）

### 選擇排序法
![](https://hackmd.io/_uploads/SJxrOioBh.png)
```ruby=
# Finds the smallest value in an array
def find_smallest(arr)
  # Stores the smallest value
  smallest = arr[0]
  # Stores the index of the smallest value
  smallest_index = 0
  # (1...n) is the same as (1..(n-1))
  (1...(arr.length)).each do |i|
    if arr[i] < smallest
      smallest = arr[i]
      smallest_index = i
    end
  end
  smallest_index
end

# Sort array
def selection_sort(arr)
  new_arr = []
  arr.length.times do
    # Finds the smallest element in the array and adds it to the new array
    smallest = find_smallest(arr)
    new_arr.push(arr.delete_at(smallest))
  end
  new_arr
end

# 'p obj' is the same as 'puts obj.inspect'
p selection_sort([5, 3, 6, 2, 10])
```

[Python](https://pythontutor.com/visualize.html#mode=display)
[Book Example](https://github.com/egonSchiele/grokking_algorithms/blob/master/02_selection_sort/python/01_selection_sort.py)

### 摘要
1. 電腦記憶體像抽屜
2. 存放多個元素可以用陣列或者鏈結串列
3. 陣列元素彼此相鄰
4. 鏈結串列的各個元素會分散各處，但每個元素都會紀錄下個元素地址
5. 陣列可以快速讀取（隨機存取）
6. 鏈結串列可以快速『插入』和『刪除』
7. 陣列中資料型別必須一至