---
# System prepended metadata

title: 排序法整理
tags: [排序法]

---

# 排序法整理
###### 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)

