---
tags: paper
---

# Efficiency of Sorting Algorithm

## 目錄

[TOC]

---

## 摘要

---

## 研究動機

排序一直是一個值得研究的問題，大部分情況下，資料都必須先排序、整理過才能成為有意義的資料。而我十分好奇，在已經被發明出來的常用排序演算法中，哪種演算法才最具有效率。

---

## 研究目標

### 實驗1
比較基數排序基於不同基數的效率

### 實驗2
比較各種常見排序演算法的效率

---

## 原理簡述

### 基數排序

基於鴿巢原理的穩定排序

#### 理論時間複雜度

| 平均 | 最差 |
| --------------- | -------- |
| $O (n\times k)$ | $O(n^2)$ |

### 快速排序

基於比較及分治的非穩定排序

#### 理論時間複雜度

| 平均 | 最差 |
| ------------------ | -------- |
| $O (n\times logn)$ | $O(n^2)$ |

### 歸併排序

基於比較及分治的穩定排序

#### 理論時間複雜度

| 平均 | 最差 |
| ------------------ | -------- |
| $O (n\times logn)$ | $O(n\times logn)$ |

### 堆積排序

基於比較及二元堆積的穩定排序

#### 理論時間複雜度

| 平均 | 最差 |
| ------------------ | -------- |
| $O (n\times logn)$ | $O(n\times logn)$ |

### C++內建排序(內省排序)

使用快速排序，遞迴至一定深度後改用堆積排序的穩定排序

#### 理論時間複雜度

| 平均 | 最差 |
| ------------------ | -------- |
| $O (n\times logn)$ | $O(n\times logn)$ |

---

## 實驗變因

### 控制變因

- 實驗平台 -
- 編譯器 - GNU GCC compiler mingw32 10.2.0
- 編譯選項 - g++ -std=c++20

### 操作變因

#### 實驗1
- 欲排序之數字範圍
- 欲排序之數字數量
- 基數排序之基數

#### 實驗2
- 欲排序之數字範圍
- 欲排序之數字數量
- 排序演算法

### 應變變因

- 排序所需時間

---

## 研究方法

### 實驗1

1. 編寫程式碼產生測試資料
2. 編寫基數排序之程式碼
3. 運行，並透過C++內建函式庫`chrono`計時
4. 比較並分析實驗數據

### 實驗2

1. 編寫程式碼產生測資資料
2. 編寫各種排序之程式碼
3. 運行，並透過C++內建函式庫`chrono`計時
4. 比較並分析實驗數據

---

## 實驗數據

---

## 結論

---

## 討論

---

## 外部連結

- [基數排序程式碼 - pastebin.com](https://pastebin.com/tXeyaFSY)
- [快速排序程式碼 - pastebin.com](https://pastebin.com/egfxbQxW)
- [歸併排序程式碼 - pastebin.com]()
- [堆積排序程式碼 - pastebin.com]()
- [內省排序程式碼 - pastebin.com]()

---

## 參考資料

- https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
- https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F
- https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
- https://zh.wikipedia.org/wiki/%E5%86%85%E7%9C%81%E6%8E%92%E5%BA%8F
- https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F