本次所統整的排序演算法只有內部排序法，沒有外部排序法。
###### 一個內建sort砸下去這小節的用途就小好多。
:::info
:::spoiler 資料在經過排序後有什麼好處?
1.容易閱讀
2.利於統計及整理
3.減少搜尋的時間
:::
### 排序方式
> **直接排序:** <font color="#D83507">直接交換</font>儲存資料的位置。(耗費較多時間進行資料的更動)
> **邏輯移動:** <font color="#D83507">改變</font>指向資料的<font color="#D83507">輔助指標的值</font>。
### 使用的記憶體種類
>**內部排序:** 資料量小，<font color="#D83507">可在記憶體內排序。</font>
>**外部排序:** 資料量大到無法在記憶體內排序，<font color="#D83507">用到輔助記憶體</font>。(ex.硬碟)
### 穩定性
> **穩定的排序:** 在排序後，兩相同鍵值保持原本的次序。
> **不穩定的排序** 在排序後，兩相同鍵值<font color="#D83507">不一定</font>保持原本的次序。
:::success
::: spoiler 舉例
排序前: 3~左~ 6 2 8 3~右~
穩定的排序: 2 3~左~ 3~右~ 6 8
不穩定的排序: 2 3~右~ 3~左~ 6 8
:::
### 時間複雜度
進行排序的執行時間我們叫他**時間複雜度**，其中又分為最好情況、最壞情況和平均情況。
(正文所出現的皆為平均情況。)
> **最好情況:** 資料已排序完成。
> **最懷情況:** 每一鍵值皆須重新排列。
> **平均情況:** 輸入的資料以等概率出現。(就是取平均)
:::success
::: spoiler 舉例
最好情況:
> 排序前: 2 4 6 8 9
> 排序後: 2 4 6 8 9
最壞情況:
> 排序前: 9 8 6 4 2
> 排序後: 2 4 6 8 9
:::
### 空間複雜度
進行排序所需的空間我們叫他**空間複雜度**，<font color="#D83507">任何排序法都有資料對調的動作，所以必定會用到一個額外空間</font>，若該排序法必須藉由遞迴的方式進行，其所使用到的堆疊則是該排序法須付出的額外空間。
---
# 泡沫排序法(bubble sort)
由第一個元素開始，比較相鄰元素的大小，若大小有誤則交換，以此類推直至排序完成。
### <font color="#2FB428">分析</font>
$1.$ 穩定的排序法。
$2.$ 時間複雜度為 $O(n^2)$。
$3.$ 空間複雜度為 $O(n)$。
$4.$ 適用資料量小或有部分排序的資料。
### <font color="#2FB428">圖例</font>
:::warning
:::spoiler 點我打開 (太長了，建議看完收起)
**第一輪之第一次交換(前者大於後者，交換)**
**第一輪之第二次交換(後者大於前者，不交換)**
**第一輪之第三次交換(前者大於後者，交換)**
**第一輪之第四次交換(後者大於前者，不交換)**
**以此類推重複至迴圈結束**
:::
### <font color="#2FB428">程式碼(配合例題)</font>
:::danger
:::spoiler 點我打開 (太長了，建議看完收起)
```cpp=
#include<iostream>
using namespace std ;
int main () {
int a ;
cin >> a ;
int arr[a] ;
for (int i = 0 ; i < a ; i ++) { //輸入資料
cin >> arr[i] ;
}
for (int i = 0 ; i < a - 1 ; i ++) { //泡沫排序法
for (int j = 0 ; j < a - i - 1 ; j ++) {
if(arr[j] > arr[j+1]) {
int tmp ;
tmp = arr[j] ;
arr[j] = arr[j+1] ;
arr[j+1] = tmp ;
}
}
}
cout << arr[0] ; //輸出資料(配合例題故以此方式輸出)
for (int i = 1 ; i < a ; i ++) {
cout << ' ' << arr[i] ;
}
cout << '\n' ;
}
```
:::
---
# 插入排序法(insert sort)
將陣列中的元素與與排序好的資料做比較，將元素插入適當的位置(已排序好的資料中)，以此類推直至排序完成。
### <font color="#2FB428">分析</font>
$1.$ 穩定的排序法。
$2.$ 時間複雜度為 $O(n^2)$。
$3.$ 空間複雜度為 $O(n)$。
$4.$ 適用資料量小或有部分排序的資料。
### <font color="#2FB428">圖例</font>
:::warning
:::spoiler 點我打開 (太長了，建議看完收起)
**原始資料:**
**第一次交換(將第一個元素放入陣列中的第一個位置)**
**第二次交換(將第二個元素與陣列中的元素比較後插入)**
**第三次交換(將第三個元素與陣列中的元素比較後插入)**
**第四次交換(將第四個元素與陣列中的元素比較後插入)**
**第五次交換(將第五個元素與陣列中的元素比較後插入)**
:::
### <font color="#2FB428">程式碼(配合例題)</font>
:::danger
:::spoiler 點我打開 (太長了，建議看完收起)
```cpp=
#include<iostream>
using namespace std ;
int main () {
int a , j ;
cin >> a ;
int arr[a] ;
for (int i = 0 ; i < a ; i ++) { //輸入資料
cin >> arr[i] ;
}
for (int i = 1 ; i < a ; i ++) { //插入排序法
int tmp ;
tmp = arr[i] ;
j = i - 1 ;
while (j >= 0 && arr[j] > tmp) {
arr[j+1] = arr[j] ;
j-- ;
}
arr[j+1] = tmp ;
}
cout << arr[0] ; //輸出資料(配合例題故以此方式輸出)
for (int i = 1 ; i < a ; i ++) {
cout << ' ' << arr[i] ;
}
cout << '\n' ;
}
```
:::
---
# 選擇排序法(selection sort)
有兩種方式，**由大至小**和**由小到大**。以由大至小為例，最小值放至第一個位置，第二小值放至第二個位子，以此類推直至排序完成。
### <font color="#2FB428">分析</font>
$1.$ 不穩定的排序法。
$2.$ 時間複雜度為 $O(n^2)$。
$3.$ 空間複雜度為 $O(n)$。
### <font color="#2FB428">圖例</font>
:::warning
:::spoiler 點我打開 (太長了，建議看完收起)
**第一次交換(找到最小值與第一個元素交換)**
**第二次交換(找到第二小值與第二個元素交換)**
**第三次交換(找到第三小值與第三個元素交換)**
**第四次交換(找到第三小值與第三個元素交換(本次大小相同，不交換))**
:::
### <font color="#2FB428">程式碼(配合例題)</font>
:::danger
:::spoiler 點我打開 (太長了，建議看完收起)
```cpp=
#include<iostream>
using namespace std ;
int main () {
int a ;
cin >> a ;
int arr[a] ;
for (int i = 0 ; i < a ; i ++) { //輸入資料
cin >> arr[i] ;
}
for (int i = 0 ; i < a ; i ++) { //選擇排序法
for (int j = i+1 ; j < a ; j ++) {
if(arr[i] > arr[j]) {
int tmp ;
tmp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = tmp ;
}
}
}
cout << arr[0] ; //輸出資料(配合例題故以此方式輸出)
for(int i = 1 ; i < a ; i ++) {
cout << ' ' << arr[i] ;
}
cout << '\n' ;
}
```
:::
---
# 謝耳排序法(shell sort)
分成特定的小區塊，以插入排序法排完區塊內的資料漸漸減少間隔的距離。
### <font color="#2FB428">分析</font>
$1.$ 穩定的排序法。
$2.$ 時間複雜度為 $O(n^{3/2})$。(以這題為例，最好的情況為 $O(n \;log^2 \; n) 。$
$3.$ 空間複雜度為 $O(n)$。
$4.$ 適用資料量小或有部分排序的資料。
### <font color="#2FB428">圖例</font>
:::warning
:::spoiler 點我打開 (太長了，建議看完收起)
**第一次交換(將該資料的長度($6$)除以$2$(不必定為$2$)，$6/2$得$3$，便是將他隔成3區。相同區塊做比較後交換，即顏色所示，其中綠的後者大於前者，不交換)**
**第二次交換(將區塊($3$)除以$2$(不必定為$2$)，$3/2$得$1$，便是將他隔成1區(在這等於直接做插入排序法)，相同區塊做比較後交換，即顏色所示)**
:::
### <font color="#2FB428">程式碼(配合例題)</font>
:::danger
:::spoiler 點我打開 (太長了，建議看完收起)
```cpp=
#include<iostream>
using namespace std ;
int main () {
int a , j , shell ;
cin >> a ;
int arr[a] ;
for (int i = 0 ; i < a ; i ++) { //輸入資料
cin >> arr[i] ;
}
shell = a / 2 ; //謝耳排序法
while (shell != 0) {
for (int i = shell ; i < a ; i ++) { //裡頭的插入排序法
int tmp ;
tmp = arr[i] ;
j = i - shell ;
while (j >= 0 && arr[j] > tmp) {
arr[j+shell] = arr[j] ;
j = j - shell ;
}
arr[j+shell] = tmp ;
}
shell = shell / 2 ;
}
cout << arr[0] ; //輸出資料(配合例題故以此方式輸出)
for (int i = 1 ; i < a ; i ++) {
cout << ' ' << arr[i] ;
}
cout << '\n' ;
}
```
:::
---
# 快速排序法(quick sort)
目前公認最佳的排序法，使用切割征服法，自行設定一個中間值，以此中間值將所有資料分成兩部分，小於中間值置於左側，大於則相反，在以相同方式處理兩邊資料，以此類推直至排序完成。(於我看來，和二分搜的概念類似)
### <font color="#2FB428">分析</font>
$1.$ 不穩定的排序法。
$2.$ 時間複雜度為 $O(n~log_2~n)$。
$3.$ 空間複雜度最差為 $O(n)$ ，最佳為 $(log_2~n)$。
$4.$ 平均執行時間最快。
### <font color="#2FB428">圖例</font>
:::warning
:::spoiler 點我打開 (太長了，建議看完收起)
**原始資料:**
**設一鍵值(通常取第一位)，小丟左大丟右:**
**再來在五的左側設一鍵值(通常取第一位)，小丟左大丟右，左半排序完成(若在這取的鍵值不為0或1還要繼續):**
**再來在五的右側設一鍵值(通常取第一位)，小丟左大丟右，右半排序完成(若在這取的鍵值不為0或1還要繼續):**
:::
### <font color="#2FB428">程式碼(配合例題)</font>
:::danger
:::spoiler 點我打開 (太長了，建議看完收起)
```cpp=
#include<iostream>
using namespace std ;
int partition(int arr[], int low, int high);
void quickSort(int arr[], int low, int high) { //快速排序法
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
int tmp ;
tmp = arr[i+1] ;
arr[i+1] = arr[high] ;
arr[high] = tmp ;
return i + 1;
}
int main() {
int a;
cin >> a;
int arr[a];
for (int i = 0; i < a; i++) { //輸入資料
cin >> arr[i];
}
quickSort(arr, 0, a - 1);
cout << arr[0]; //輸出資料(配合例題故以此方式輸出)
for (int i = 1; i < a; i++) {
cout << ' ' << arr[i];
}
cout << '\n';
return 0;
}
```
:::
---
# 合併排序法(merge sort)
針對已排序好的兩個或兩個以上的檔案由合併的方式，組成一個排序好的檔案。
#### <font color="#2FB428">分析</font>
$1.$ 穩定的排序法。
$2.$ 時間複雜度為 $O(n~log~n)$。
$3.$ 空間複雜度為 $O(n)$。
$4.$ 適用資料量大的外部檔案。
### <font color="#2FB428">圖例</font>
:::warning
:::spoiler 點我打開 (太長了，建議看完收起)
**原始資料:**
**先拆分:**
**會得到:**
再來進行合併的動作。
**後合併(合併的資料做排序):**
:::
### <font color="#2FB428">程式碼(配合例題)</font>
:::danger
:::spoiler 點我打開 (太長了，建議看完收起)
```cpp=
#include<iostream>
using namespace std;
void merge(int arr[], int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
int leftArr[n1], rightArr[n2];
for (int i = 0; i < n1 ; i++) {
leftArr[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
rightArr[j] = arr[middle + 1 + j];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) { //合併排序法
if (left < right) {
int middle = left + (right - left) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
int main() {
int a;
cin >> a;
int arr[a];
for (int i = 0; i < a; i++) { //輸入資料
cin >> arr[i];
}
mergeSort(arr, 0, a - 1);
cout << arr[0] ; //輸出資料(配合例題故以此方式輸出)
for (int i = 1 ; i < a ; i++) {
cout << ' ' << arr[i] ;
}
cout << '\n' ;
}
```
:::
---
# 堆積排序法(heap sort)
選擇排序法的改版，減少其的比較次數，利用到二元樹(後續的課程)的堆積樹。
### <font color="#2FB428">分析</font>
$1.$ 不穩定的排序法。
$2.$ 時間複雜度為 $O(n~log_2~n)$。
$3.$ 空間複雜度為 $O(n)$。
### <font color="#2FB428">圖例</font>
在進行堆積排序法的圖例前要先介紹什麼是堆積樹，不然不好解釋堆積排序法是怎麼進行的。
::: info
::: spoiler 堆積樹 (本題以最大堆積樹舉例)
**同樣以5 2 7 4 9 來解釋**
**arr [0] 跟arr [1] 比較，前者大於後者，不交換**
**arr [0] 跟arr [2] 比較，後者大於前者，交換**
**arr [1] 跟arr [3] 比較，後者大於前者，交換。
此時的arr [1] 再跟 arr[0] 做比較，後者大於前者，不交換**
**arr [1] 跟arr [4] 比較，後者大於前者，交換。
此時的arr [1] 再跟 arr[0] 做比較，前者大於後者，交換**
(第一步)
(第二步)
**便可得到該陣列中最大的元素，提出，刪掉樹根，重複直至排序結束。**
:::
:::warning
:::spoiler 點我打開 (太長了，建議看完收起)
**原始資料:**
**第一次建立堆積樹**
**第二次建立堆積樹**
**第三次建立堆積樹**
**第四次建立堆積樹**
**第五次建立堆積樹**
:::
### <font color="#2FB428">程式碼(配合例題)</font>
:::danger
:::spoiler 點我打開 (太長了，建議看完收起)
```cpp=
#include <iostream>
using namespace std;
void heap(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heap(arr, n, largest);
}
}
void heapSort(int arr[], int n) { //堆積排序法
for (int i = n / 2 - 1; i >= 0; i--) {
heap(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heap(arr, i, 0);
}
}
int main() {
int a ;
cin >> a ;
int arr[a] ;
for (int i = 0 ; i < a ; i++) { //輸入資料
cin >> arr[i] ;
}
heapSort(arr, a-1);
cout << arr[0] ; //輸出資料(配合例題故以此方式輸出)
for (int i = 1 ; i < a ; i++) {
cout << ' ' << arr[i] ;
}
cout << '\n' ;
}
```
:::
---
# 基數排序法(radix sort)
以分配模式排序，有 最高有效鍵值開始排序(MSD) 和 從最低有效鍵值開始排序(LSD)。
換句話說基數排序法不同於其他類型的排序法，他排序的方法利用的了數學的概念，**數字的大小和其位數有關**，利用這一點來進行排序。
### <font color="#2FB428">分析</font>
$1.$ 穩定的排序法。
$2.$ 時間複雜度為 $O(n \; log_b \; k)$，$b$ 為底數。
$3.$ 空間複雜度為 $O(n+k)$。
### <font color="#2FB428">圖例</font>
:::warning
:::spoiler 點我打開 (太長了，建議看完收起)
**原始資料:(為更詳細介紹，故將資料增加不同位數)**
**第一次排序:(排個位數)**
**第二次排序:(排十位數)**
**第三次排序:(排百位數，若無則當0)**
**第四次排序:(排千位數，若無則當0)**
:::
### <font color="#2FB428">程式碼(配合例題)</font>
:::danger
:::spoiler 點我打開 (太長了，建議看完收起)
```cpp=
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n;i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
void countSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
void radixSort(int arr[], int n) { //基數排序法
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, n, exp);
}
}
int main() {
int a ;
cin >> a ;
int arr[a] ;
for (int i = 0 ; i < a ; i++) { //輸入資料
cin >> arr[i] ;
}
radixSort(arr, a-1);
cout << arr[0] ; //輸出資料(配合例題故以此方式輸出)
for (int i = 1 ; i < a ; i++) {
cout << ' ' << arr[i] ;
}
cout << '\n' ;
}
```
:::
# 例題
###### 有什麼題目沒提到或有新增的煩請留言告知。
[a066: Sort! Sort! Sort!](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a066)
[a083: Sort yourself 1](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a083)
[a084: Sort yourself 2](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a084)
[a208: 真 ● 泡沫排序法](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a208)
[a248: pI 你那第幾中隊的R 會不會排隊R 亂七八糟 一點紀律都沒有](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a248)
[a934: 泡沫排...?](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a934)
###### 都看到這了難道不按個愛心支持一下嗎?
Sign in with Wallet
Connect another wallet