# Sorting 介紹
###### tags: `Sort`
<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;
}

body > .ui-infobar {
display: none;
}

.ui-view-area > .ui-infobar {
display: block;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

</style>
### 介紹
**Sorting(排序)** 可以讓資料以我們想要的呈現方式進行呈現。舉例來說，在購物網站中，我們可以對商品的「熱門程度」、「上架日期」、「價格」等條件來將商品依照特定方式排序。

Sorting可以分為兩類，分別是**Comparison Sort(基於比較的排序)** 和 **Non-comparision Sort(不基於比較排序)**。我們常使用的排序如**Bubble Sort**,**Insertion Sort**,**Quick Sort**等都是基於比較的排序，透過比較資料內容來決定資料的位置。

在N筆資料下，各個排序法的比較如表一：
| 排序法 | 時間複雜度 | 空間複雜度 | 穩定性 |
|:------------------- | ---------- | ---------- |:------ |
| [Bubble Sort][0] | O(N^2^) | O(1) | YES |
| [Insertion Sort][1] | O(N^2^) | O(1) | YES |
| [Selection Sort][2] | O(N^2^) | O(1) | NO |
| Merge Sort | O(NlogN) | O(N) | YES |
| Quick Sort | O(NlogN) | O(logN) | NO |
| Heap Sort | O(NlogN) | O(1) | NO |

[0]:https://hackmd.io/kzhWNN-ZQ9O3Ylatmvf9nw?view#Bubble-Sort
[1]:https://hackmd.io/2LOyrze-QTq79mL0RthJwg
[2]:https://hackmd.io/ynjSKvt1StuePhCXi9tZ8g?both

穩定性：需要排序的資料中，存在多筆相同值的數據，在完成排序後，其相對位置不變。
Ex：[2,1,2,3,5] -> [1,2,2,3,5]，前面的2依舊在前面。

<hr style="height:1px;border:none;border-top:1px dashed #0066CC;">

[資料結構與演算法](/FP0Vd0lqQM2gDIadctxk2Q)