#### 六种常见的排序方法

```#include "iostream"
#include "vector"
#include "iterator"
#include "ctime"
#include "random"

template<typename T>
inline void Swap(T & a, T & b){  //交换变量
T tmp = a;
a = b;
b = tmp;
}

template<typename T>
inline bool cmp(const T & a, const T & b){  //比较函数
return a <= b;
}

template<typename T>
void Select_sort(std::vector<T> & v){    //选择排序
for (unsigned i = 0; i < v.size() - 1; ++i){
int best = i;
for (unsigned j = i + 1; j < v.size(); ++j)
if (cmp(v[j], v[best]))
best = j;
Swap(v[i], v[best]);
}
}

template<typename T>
void Bubble_sort(std::vector<T> & v){    //冒泡排序
for (unsigned i = 0; i < v.size() - 1; ++i){
bool exchange = false;
for (unsigned j = v.size() - 1; j > i; --j)
if (cmp(v[j], v[j - 1])){
Swap(v[j], v[j - 1]);
exchange = true;
}
if (!exchange) return;
}
}

template<typename T>
void Insertion_sort(std::vector<T> & v){     //插入排序
for (int i = 1, j; i < v.size(); ++i){
T key = v[i];
for (j = i - 1; j >= 0; --j){
if (cmp(key, v[j])) v[j + 1] = v[j];
else break;
}
v[j + 1] = key;
}
}

template<typename T>
void Shell_sort(std::vector<T> & v){     //希尔排序
for(int gap = v.size()/2; gap > 0; gap /= 2)
for(int i = gap; i < v.size(); ++i)
for(int j = i - gap; j >= 0 && cmp(v[j + gap], v[j]); j -= gap)
Swap(v[j], v[j + gap]);
}

template<typename T>
void Merge_sort(std::vector<T> & v, std::vector<T> & t, int x, int y){    //归并排序
if (y - x <= 1) return;
int m = x + (y - x) / 2;
int p = x, q = m, i = x;
Merge_sort(v, t, x, m);
Merge_sort(v, t, m, y);
while (p < m || q < y){
if (q >= y || (p < m && cmp(v[p], v[q]))) t[i++] = v[p++];
else t[i++] = v[q++];
}
std::copy(t.begin() + x, t.begin() + y, v.begin() + x);
}

template<typename T>
void Quick_sort(std::vector<T> & v, int x, int y){    //快速排序
if (y <= x) return;
int i = x, j = y, m = v[i];
while (i < j){
while (i < j && cmp(m, v[j])) --j;
if (i < j) v[i++] = v[j];
while (i < j && cmp(v[i], m)) ++i;
if (i < j) v[j--] = v[i];
}
v[i] = m;
Quick_sort(v, x, i - 1);
Quick_sort(v, i + 1, y);
}

int main(int argc, char const *argv[])
{
std::vector<int> v;
srand(time(NULL));
for(int i = 0; i < 102400; ++i)
v.push_back(rand());
std::vector<int> T(v.size());
clock_t start_time = clock();
//Select_sort(v);                     //3931MS
//Bubble_sort(v);                     //22230MS
//Insertion_sort(v);                  //1809MS
//Shell_sort(v);                      //31MS
//Merge_sort(v, T, 0, v.size());      //15MS
//Quick_sort(v, 0, v.size()-1);       //15MS
clock_t end_time = clock();
std::cout << "Running Time:" << (double)(end_time - start_time) / CLOCKS_PER_SEC * 1000 << "MS" << std::endl;
//std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, "\n"));  //输出
return 0;
}
```