# 排序
## 冒泡排序（n^2）
每次交換把當前剩余元素中最大的元素移動到一端，剩余元素不斷交換直至剩余元素為0
```c++
// 從小到大排序
void bubbleSort(int a[], int n){
for(int i=1; i<n; i++){
for(int j=0; j<n-i; j++){
if(a[j]>a[j+1]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
```
## 簡單選擇排序（n^2）
每次將當前剩余元素中最小的元素與剩余元素的第一個元素交換，直至剩余元素為0
```C
// 從小到大排序
void selectSort(int a[], int n){
for(int i=0; i<n; i++){
int k = i;
for(int j=i; j<n; j++){
if(a[j]<a[k])
k = j;
}
int temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
```
## 直接插入排序（n^2）
數列分為前面有序、后面無序兩部分，每次將第一個無序的數插入到前面有序數列中，直至剩余無序元素為0
``` c
// 從小到大排序
void insertSort(int a[], int n){
for(int i=1; i<n; i++){
int temp = a[i], j = i;
while(j>1 && temp<a[j-1]){
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
```
## 兩路歸并排序
```C++
// 合并有序序列
const int maxn=100;
void merge(int a[], int L1, int R1, int L2, int R2){
int i=L1, j=L2;
int tmp[maxn], index=0;
while(i<=R1 && j<=R2){
if(a[i]<=a[j]) tmp[index++]=a[i++];
else tmp[index++]=a[j++];
}
while(i<=R1) tmp[index++]=a[i++];
while(j<=R2) tmp[index++]=a[j++];
for(i=0;i<index;i++){
a[L1+i]=tmp[i];
}
}
// 遞歸實現
void mergeSort(int a[], int left, int right){
if(left<right){
int mid=(left+right)/2;
mergeSort(a, left, mid);
mergeSort(a, mid+1, right);
merge(a, left, mid, mid+1, right);
}
}
// 非遞歸實現
void mergeSort(int a[]){
for(int step=2;step/2<=n;step*=2){
for(int i=1;i<=n;i+=step){
int mid=i+step/2-1;
if(mid+1<=n){
merge(a,i,mid,mid+1,min(i+step-1,n));
}
}
}
}
```
### 遞歸實現
## 快速排序（nlogn）
```C++
// 對區間 [left, right] 進行劃分，使得 a[left] 左邊的數都小于它，右邊的數都大于它
int partition(int a[], int left, int right){
int tmp=a[left];
while(left<right){
while(left<right && A[right]>tmp) right--;
A[left]=A[right];
while(left<right && A[left]<tmp) left++;
A[right]=A[left];
}
A[left]=tmp;
return left; // 返回相遇的下標
}
// 快速排序
void quickSort(int a[], int left, int right){
if(left<right){
int pos=partition(a,left,right);
quickSort(a,left,pos-1);
quickSort(a,pos+1,right);
}
}
```
## ChangeLog
> 2018.08.25 初稿
>
> 2018.09.03 添加歸并排序和快速排序
