# 資料結構 - CH5:Sort

###### tags: `資料結構和演算法`

## Insertion Sort

## Merge Sort

- 先divide到最小，再一層層merge回去，並在merge的同時完成排序

## Heap Sort

1. 建立max/min heap: O(n)
2. 重複n次extract: O(nlogn)
3. Time complexity: O(n) + O(nlogn) = O(nlogn)

## Quick Sort

1. 選任意數當作pivot
2. lptr往右找大於pivot的數，rptr往左找比pivot小的數
3. 交換ptr和pivot，以pivot為中心分為兩個array
4. 各自選一個pivot，並遞迴下去

// Pseudocode

QuickSort(){
    i = Partition();
    QuickSort(L,i-1);
    QuickSort(i+1,R);
}

Partition(){
    while(1){
        while(array[i] < pivot) i++;
        while(array[j] > pivot) j--;
        if(i >= j) break;
        swap(i,j);
    }
    swap(pivot,i)
    return i;
}

- 平均時間複雜度: O(nlgn)
- 最壞時間複雜度: O(n²)

## Counting Sort

- 先找出陣列中的最大和最小值
- 每一個元素出現的次數，用一個陣列存起來，一個元素對應一個數字
- 將計數陣列中的每一項和前一項作累加
- 依照計數陣列排出所有元素
- 適合用在元素重複出現率高且範圍不大的情形，例如radix或bucket的subfunction
- 時間複雜度: O(n+k)，k為最大值減去最小值，也就是計數陣列的大小

## Bucket Sort

- 先依照大概的大小分為幾個bucket，例如(0~10, 11~20, 21~30, ...)
- 再依序對每個桶子內的元素簡單排序

## Radix Sort

1. 準備10個vector(0~9)
2. 從LSD或MSD開始分類
3. 分完之後依序從0到9取出
4. 分類下一個digit，並重複直到排序完成

有空會再補充 ◟(∗ ˊωˋ ∗)◞