# 排序法整理
###### tags: `排序法`

## 其他排序法
### Insertion sort

#### 概念
* 撲克牌整牌法
* algorithm
* index i：1 to n-1 as boundary of sorted array
* j：i to n-1
* **compare with sorted array**, and insert into the right position

        while ( arr[j] > arr[j-1] ){
            swap(arr[j],arr[j-1]);
            j = j-1  continue to compare with more front items
        } 

---
### Selection sort
#### 概念
* 有**min指標**來記錄最小值，i：0 to n-1，通常假設arr[0]
* 跟右邊比較，j：i to n-1，如果有更小的，就把min index指到該值
* 做完一輪，再swap(arr[min],arr[i])

---
### Bubble sort
#### 概念
* 因為最大值會浮出到右邊所以稱bubble sort
* 兩兩相鄰一直比較，第一個for loop 代表作**N-1**次
* algorithm

    for(int i=0; i<n; i++){    做N-1次
        for(int j=0; j<n-1; j++){  每次都要兩兩相比
            if(arr[j]>arr[j+1]){
                swap(arr[j],arr[j+1]);
            }
        }
    }

---
### Shell sort
#### 概念
* **分群**的insertion sort
* gap = gap/3+1 means 間隔3的一組，每比較一次就再除一次
* init gap = n
* gap = gap/3+1
* do insertion sort
* 做到gap=1時，就差不多排序好了

---

## 排序法時間複雜度比較

| sort | average | best |worst|space|
| -------- | -------- | -------- | --- | ---|
| insertion| O(n*n) | **O(n)** |O(n*n) | O(1)|
| selection | O(n*n) | O(n*n) |O(n*n)| O(1)|
| bubble | O(n*n) | **O(n)** |O(n*n)|O(1)|
| shell | O(nlog2n) | O(nlog2n) |O(n*s)，1<s<2 |O(1)|
|**merge**|**O(nlogn)**|**O(nlogn)**|**O(nlogn)**|**O(n)/O(logn)**|
|**quick**|O(nlogn)|O(nlogn)|**O(n*n)**|**O(logn)**|
|**heap**|**O(nlogn)**|**O(nlogn)**|**O(nlogn)**|O(1)|
|**tree**|O(nlogn)|O(nlogn)|**O(n*n)**|O(1)|

其他排序法請看連結
[Merge Sort](/h4mGj2xuTdGRasAzlqpRYw)
[Heap Sort](/fL8XbK_eQ-m4LBdtfnoq4Q)
[Quick Sort](/Gt_b7YLXTpSqk5acRyzlSw)
[Tree Sort](/LoYcpNPbROqsm9Ekh2eIUw)