#include<iostream>
#include<algorithm>
#include<vector>
#define MAXSIZE 100;
using namespace std;
//时间复杂度最好o(n)最差o(n^2)平均o(n^2) 稳定排序
//冒泡排序
void bubbleSort(vector<int> &v)
{
for (int i = 0; i < v.size(); ++i)
{
for (int j = 0; j < v.size() - i-1; ++j)
{
if (v[j] > v[j + 1])
swap(v[j], v[j + 1]);
}
}
}
//选择排序 时间复杂度最好o(n^2)最差o(n^2)平均o(n^2) 稳定排序
void SelectSort(vector<int> &v)
{
for (int i = 0; i < v.size(); ++i)
{
int min = i;
for (int j = i + 1; j < v.size(); ++j)//在未排好序里面选取最小的排在排好序最后
{
if (v[min] > v[j])
min = j;
}
if (min != i)
swap(v[min], v[i]);
}
}
//插入排序 时间复杂度最好o(n)最差o(n^2)平均o(n^2) 稳定排序
void InsertSort(vector<int> &v)//插入排序
{
for (int i = 1; i < v.size(); i++)
{
if (v[i] < v[i - 1])//需要将v[i]进行插入
{
int temp = v[i];
int j;
for (j = i - 1; temp < v[j]; j--)//找到该插入的位置
{
v[j+1] = v[j];//将其后面的都往后移动一位
}
v[j+1] = temp;//插入
}
}
}
//不稳定排序
void ShellSort(vector<int> &v)//希尔排序
{
int increment = v.size();
do
{
increment = increment / 3 + 1;
for (int i = increment; i < v.size(); i++)
{
if (v[i] < v[i-increment])//大踏步交换
{
swap(v[i], v[i - increment]);
}
}
}
while (increment > 1);
}
void HeapAdjust(vector<int> &v, int s, int m)//堆排序调整
{
int temp = v[s];
for (int j = 2 * s; j < m; j *= 2)//堆的调整可能影响其子节点，需要对其子节点进行调整，所以要j*2
{
if (j < m && v[j] < v[j + 1])//取出其子树中大的那一个
j++;
if (temp >= v[j])//如果根节点大就不用调整
break;
v[s] = v[j];//将大的改为根节点
s = j;
}
v[s] = temp;//交换一下
}
//堆排序最好最坏时间复杂度都为o(nlogn)，不稳定，不适合排序个数较少情况
void HeapSort(vector<int> &v)//堆排序
{
for (int i = v.size() / 2; i >= 0; i--)//构建堆：只需要调整非叶子节点即可，个数为n/2
{
HeapAdjust(v, i, v.size()-1);
}
for (int i = v.size()-1; i > 0; i--)
{
swap(v[0], v[i]);//取根节点
HeapAdjust(v ,0 ,i - 1);//取完根节点之后再调整一个相对小的堆
}
}
/*
//以下为归并排序最好最坏都是o(nlog(n)),排序稳定
void MergeSort(int sr[], int tr[], int s, int m, int t)
{
int i, j, k;//i,j左右两个数组合并
for (i = s, j = m + 1; i <= m&&j <= t; k++)
{
if (sr[i] < sr[j])//选择左右两个数组里面较小的那个到合并的数组里面
tr[k] = sr[i];
else
tr[k] = sr[j];
}
//若左右两个数组有一个已经合并完了，另外一个直接接上即可
if (i < m)
{
for (int l = 0; l < m - i; l++)
tr[k + l] = sr[i + l];
}
if (j < t)
{
for (int l = 0; l < t - j; l++)
tr[k + l] = sr[j + l];
}
}
//归并排序
void MSort(int sr[], int tr1[], int s, int t)
{
int m;
int tr2[100];//归并排序需要多余空间
if (s == t)
tr1[s] = sr[1];
else
{
m = (s + t) / 2;
MSort(sr, tr2.s, m);
MSort(sr, tr2, m + 1, t);
MergeSort(tr2, tr1, s, m, t);
}
}*/
//快速排序 不稳定排序o(nlogn) 空间复杂度为log(n) 至 n
void quickSort(vector<int> &s, int l, int r)
{
if (l< r)
{
int i = l, j = r, temp = s[l];
while (i < j)
{
while (i < j && s[j] >= temp) // 从右向左找第一个小于x的数
j--;
swap(s[i], s[j]);
while (i < j && s[i]< temp) // 从左向右找第一个大于等于x的数
i++;
swap(s[i], s[j]);
}
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
void print(vector<int> l)//打印
{
for (int i = 0; i < l.size(); ++i)
{
cout <<l[i] << " ";
}
cout << endl;
}
void main()
{
vector<int> vec = { 1,2,3,1,1,2,4,5,7,3,5,7,9,1,1,12,11,10};
print(vec);
//bubbleSort(vec);
//SelectSort(vec);
//InsertSort(vec);
//ShellSort(vec);
//HeapSort(vec);
quickSort(vec, 0, vec.size()-1);
print(vec);
system("pause");
}
原文：https://www.cnblogs.com/wangqijun/p/11687340.html