#include<iostream>
#include<vector>
using namespace std;
//打印
void foreach(vector<int> v)
{
for (vector<int>::iterator it = v.begin(); it!=v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
//交换函数
void swap(int &a,int &b)
{
int t = a;
a = b;
b = t;
}
//冒泡排序法（优化）
void BubbleSort(vector<int> &v)
{
bool flag = true;
for (int i = 0; i < v.size()-1 && flag; i++)
{
flag = false;
for (int j = v.size() - 2; j >= i; j--)
{
if (v[j]>v[j + 1])
{
swap(v[j], v[j + 1]);
flag = true;
}
}
}
}
//简单选择排序算法
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 (i != min)
{
swap(v[i], v[min]);
}
}
}
//直接插入排序算法
void InsertSort(vector<int>&v)
{
int x;
for (int i = 1; i < v.size(); i++)
{
if (v[i] < v[i - 1])
{
int a = v[i];
for (int j = i - 1; v[j] > a; j--)
{
v[j + 1] = v[j];
x = j;
if (j == 0)
break;
}
v[x] = a;
}
}
}
//希尔排序
void ShellSort(vector<int> &v)
{
int increment = v.size();
do
{
increment = increment / 3 + 1;
for (int i = increment+1; i < v.size()+1; i++)
{
if (v[i-1] < v[i - increment-1])
{
int m = v[i-1];
int x;
for (int j = i - increment; j > 0 && m < v[j-1]; j -= increment)
{
v[j + increment-1] = v[j-1];
x = j-increment;
}
v[x + increment-1] = m;
}
}
}
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)
{
if (j < m && v[j] < v[j + 1])
++j;
if (temp >= v[j])
break;
v[s] = v[j];
s = j;
}
v[s] = temp;
}
//堆排序
void HeapSort(vector<int> &v)
{
for (int i = v.size() / 2; i > 0; i--)
{
HeapAdjust(v, i - 1, v.size() - 1);
}
for (int i = v.size(); i > 0; i--)
{
swap(v[0], v[i - 1]);
HeapAdjust(v, 0, i - 2);
}
}
void Merge(vector<int> SR, vector<int> TR, int i, int m, int n)
{
int j, k, l;
for (j = m + 1, k = 1; i <= m && j <= n; k++)
{
if (SR[i] < SR[j])
TR[k] = SR[i++];
else
TR[k] = SR[j++];
}
if (i <= m)
{
for (l = 0; l <= m - i; l++)
{
TR[k + 1] = SR[i + 1];
}
}
if (j <= n)
{
for (l = 0; l <= n - j; l++)
{
TR[k + 1] = SR[j + 1];
}
}
}
void MSort(vector<int> &SR, vector<int> &TR1, int s, int t)
{
vector<int> TR2;
if (s == t)
TR1.push_back(SR[s]);
else
{
int m = (s + t) / 2;
MSort(SR, TR2, s, m);
MSort(SR, TR2, m + 1, t);
Merge(TR2, TR1, s, m, t);
}
}
//归并排序(有问题)
void MergeSort(vector<int> &v)
{
MSort(v, v, 0, v.size());
}
int Partition(vector<int> &v, int low, int high)
{
int pivotkey = v[low];
while (low < high)
{
while (low < high&&v[high] >= pivotkey)
high--;
swap(v[low], v[high]);
while (low < high && v[low] <= pivotkey)
low++;
swap(v[low], v[high]);
}
return low;
}
void QSort(vector<int> &v, int low, int high)
{
int pivot;
if (low < high)
{
pivot = Partition(v, low, high);
QSort(v, low, pivot - 1);
QSort(v, pivot + 1, high);
}
}
//快速排序算法
void QuickSort(vector<int> &v)
{
QSort(v, 0, v.size()-1);
}
void main()
{
vector<int> v;
v.push_back(9);
v.push_back(1);
v.push_back(5);
v.push_back(8);
v.push_back(3);
v.push_back(7);
v.push_back(4);
v.push_back(6);
v.push_back(2);
foreach(v);
//BubbleSort(v);//冒泡排序算法
//SelectSort(v);//简单选择排序算法
//InsertSort(v);//直接插入排序算法
//ShellSort(v);//希尔排序
//HeapSort(v);//堆排序
//MergeSort(v);//归并排序
QuickSort(v);
foreach(v);
system("pause");
}
