---
# System prepended metadata

title: Sorting 介紹
tags: [Sort]

---

# 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)