# 排序演算法
## Bubble sort(泡沫排序法)
泡沫排序法是一個很直觀且簡易的一種排序算法，以升冪從未排序的第一筆開始，第一筆資料和第二筆做交換，如果第二筆大於第三筆，就將第二筆和第三筆交換，以此類推。
Time complexity :O(n^2)
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main(){
int counts;
while(cin >> counts){
vector<int> vec;
int temp;
for(int i = 0;i < counts;i++){
cin >> temp;
vec.push_back(temp);
}
for(int i = 0;i < counts;i++){
for(int k = 0;k < counts-1;k++){
if(vec[k] > vec[k+1])
swap(vec[k],vec[k+1]);
}
}
for(int i = 0 ;i < counts;i++){
cout << vec[i] << " ";
}
cout << endl;
}
return 0;
}
```
## Merge sort(合併排序法)
merge sort 是一個運用divide and conquer 演算法的演算法，先將問題分為數個子問題，最後再結合起來就會是問題的答案了。
<span style = "color:red">time complexity : O(nlogn)</span>
```cpp=
#include <iostream>
#include <vector>
using namespace std;
long long int infinity = 999999999;
void merge(vector<int> &vec,int first,int mid,int last){
vector<int> left_area(vec.begin()+first,vec.begin()+mid+1);
vector<int> right_area(vec.begin()+mid+1,vec.begin()+last+1);
left_area.emplace(left_area.end(),infinity);
right_area.emplace(right_area.end(),infinity);
int left_idx = 0,right_idx = 0;
for(int i = first;i <= last;i++){
if(left_area[left_idx] <= right_area[right_idx]){
vec[i] = left_area[left_idx];
left_idx++;
}
else{
vec[i] = right_area[right_idx];
right_idx++;
}
}
}
void merge_sort(vector<int> &vec,int first,int last){
if(first < last){
int mid = (first+last)/2;
merge_sort(vec,first,mid);
merge_sort(vec,mid+1,last);
merge(vec,first,mid,last);
}
}
int main(){
vector<int> vec{48,23,19,34,65,20,3};
cout << "original : ";
for(int i = 0;i < vec.size();i++)
cout << vec[i] << " ";
cout << endl;
cout << "After merge sort : ";
merge_sort(vec,0,7);
for(int i = 0;i < vec.size();i++)
cout << vec[i] << " ";
return 0;
}
```
首先使用vector來儲存資料，接著把vector加入merge_sort()函式，merge_sort主要運行遞迴，前面有說merge_sort是將大問題分為數個子問題，而此遞迴就是為了實現此方式，首先將矩陣分為兩個，各自再分為兩個，一直分到不能分為止，此時停止遞迴，接著合併各個矩陣，在第6行和第7行是vector的constructor，將兩個矩陣分別放入left_area和right_area，然後用emplace把一個極大的數字插在他們的最後的地方，然後開始比較，兩個不同的vector用兩個不同的指標，把小的依序擺下來，擺好後在和下一個比，直到完成排序，這樣就完成merge_sort了。
## Quick sort(快速排序法)
quick sort是一個運用divide and conquer 演算法的演算法，而隸屬於algorithm這個函式庫中有一個函式sort()就是利用quick sort，這是別人寫好的，可以接利用，首先先介紹這個函式，這個函式可加入三個參數，第一個參數是陣列或向量的第一個值，而第二個值是陣列或向量的最後一個值，第三個參數可有可無，是放入自訂函式，決定升冪或降冪，或當陣列或向量並不純，而是有和結構做連接，所以此時適合加入第三個參數，幫助解決。
<span style = "color:red">time complexity : O(nlogn)
但是worst case的時候是O(n^2)</span>
```cpp=
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
struct data{
int a;
int b;
};
bool cmp(data x,data y){
if(x.a == y.a) return x.b < y.b;
else return -1;
}
int main(){
data foo[10];
srand(time(NULL));
for(int j = 0;j < 10;j++)
foo[j].a = 0;
for(int i = 0;i < 10;i++){
foo[i].b = rand()%1000;
}
sort(foo,foo+10,cmp);//此處加入第三個參數
for(int i = 0;i < 10;i++)
cout << foo[i].b << " ";
return 0;
}
```
但是不能只會用別人的東西，自己也要會寫，所以接下來要介紹quick sort是如何運行的。
```cpp=
#include <bits/stdc++.h>
using namespace std;
void quick_sort(int *arr,int front_,int end_);
void swap_(int *a,int *b);
int partition_(int *arr,int front_,int end_);
int main(){
int arr[10] = {3,5,7,2,13,21,6,1};
for(int i = 0;i < 8;i++)
cout << arr[i] << " ";
cout << endl;
quick_sort(arr,0,7);
for(int i = 0;i < 8;i++)
cout << arr[i] << " ";
return 0;
}
void swap_(int *a,int *b){
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void quick_sort(int *arr,int front_,int end_){
if(front_ < end_){
int pivot = partition_(arr,front_,end_);
quick_sort(arr,pivot+1,end_);
quick_sort(arr,front_,pivot-1);
}
}
int partition_(int *arr,int front_,int end_){
int pivot = arr[end_];
int i = front_-1;
for(int j = front_;j < end_;j++){
if(arr[j] < pivot){//to control ascending power and Descending powers
i++;
swap_(&arr[i],&arr[j]);
}
}
i++;
swap_(&arr[i],&arr[end_]);
return i;
}
```
quick sort有一個很重要的東西，就是pivot，他就像一個標準，每個值要和他比較，在他左邊的值是比他小的，在他右邊是比他大的，保持這個特性一直做下去，而我們的pivot會採用陣列裡最後一個值，沒有強制規定要找哪一個，而在partition_裡的迴圈作用是一個一個做比較，最後再將pivot插入中間，以得到在他左邊的值是比他小的，在他右邊是比他大的。而quick_sort函式裡是一個遞迴，一直重複直到無法再分到更小的，這邊和merge sort有幾分相似。
## 總結
我覺得排序演算法是一堂很重要的課，也是進入演算法世界的第一把鑰匙，表面上在排序，但實際上有許多的觀念在背後，其實排序演算法有很多，但我這邊就舉三個例子即可，學玩排序後就來學搜尋吧！
Sign in with Wallet
Connect another wallet