排序算法C++实现（一）
主要实现冒泡排序、简单选择排序、直接插入排序和希尔排序法。前三者的时间复杂度都为O(n2)，希尔排序作为插入排序法的一种，其在内部进行分组，使得时间复杂度为O(nlogn)。
运行结果: 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void exchange(int &a, int &b);
void test01(int a,int b);
void print(vector<int> input);
vector<int> sort1(vector<int> input);//冒泡排序法
vector<int> select_sort(vector<int> input);//简单选择排序
vector<int> InsertSort(vector<int> input);//直接插入排序
vector<int> Shellsort(vector<int> input);//希尔排序法
void exchange(int &a, int &b)//采用引用传递，不能使用值传递
{
int temp = a;
a = b;
b = temp;
}
void test01(int a,int b)
{
cout<<a<<" "<<b<<" "<<endl;
exchange(a,b);
cout<<a<<" "<<b<<" "<<endl;
}
void print(vector<int> input)
{
for(int i = 0;i<input.size();++i)
{
cout<<input[i]<<' ';
}
cout<<endl;
}
/*****************冒泡排序**************************/
//vector<int> sort1(vector<int> input)
//{
// int len = input.size();
// for(int i = 0;i<len;++i)
// {
// for(int j = i+1;j<len;++j)
for(int j = len-1;j>i;--j)//改进，小的值慢慢冒上来
// {
print(input);
// if(input[i]>input[j])
if(input[j-1]>input[j])//改进，小的值慢慢冒上来
// exchange(input[i],input[j]);
// }
// }
// return input;
//}
vector<int> sort1(vector<int> input)
{
int len = input.size();
for(int i = 0;i<len;++i)
{
// for(int j = i+1;j<len;++j)
for(int j = len-1;j>i;--j)//改进，小的值慢慢冒上来
{
// print(input);
// if(input[i]>input[j])
if(input[j-1]>input[j])//改进，小的值慢慢冒上来
exchange(input[j-1],input[j]);
}
}
return input;
}
/*****************简单选择排序**************************/
//选出第i小的，然后与当前i交换，时间复杂度为O(n2)
vector<int > select_sort(vector<int> input)
{
int i = 0, j = 0, len = input.size(), min = 0;
for( i =0; i < len;++i)
{
min = i;
for( j = i + 1; j < len;++j )
{
if(input[j]<input[min])
min = j;
}
if(i!=min)
exchange(input[i],input[min]);
}
return input;
}
/*****************直接插入法，打牌思想**************************/
//利用一个辅助空间存放当前数值，通过对比当前数与其他数，进行数据的移动 时间复杂度O(n2)
//如果当前数小于前面的一个数，前面的数后移，下标前移继续比较
//如：9 1 5 3，开始i = 1, j = 0,temp=1，temp<L[0] = 9,，第一轮结果 9 9 5 3; j = -1,不满足j>=0，执行107行，结果为 1 9 5 3
//第二轮：i = 2， j = 1，temp = 5， temp<L[1] = 9, 1 9 9 3; j = 0, temp = 5 > L[0] = 1,break; 执行107行，结果为 1 5 9 3
//第三轮: i = 3, j = 2, temp = 3, temp<L[2] = 9， 1 5 9 9; j=1,temp<L[1] = 5，1 5 5 9; j = 0, temp = 5 > L[0] = 1,break; 执行107行，结果为 1 3 5 9
vector<int> InsertSort(vector<int> input)
{
int len = input.size();
int temp = 0;//辅助空间
int i = 0,j = 0;
for(i = 1;i<len;++i)
{
if(input[i]<input[i-1])//无序才进行操作
{
temp = input[i];
for(j = i-1;j>=0;j--)
{
if(temp<input[j])
input[j+1] = input[j];
else
break;
}
input[j+1] = temp;
}
}
return input;
}
/*****************希尔排序法**************************/
//直插法排序的一种，将数据按照间隔进行分组，循环，直到间隔为1
vector<int> Shellsort(vector<int> input)
{
int len = input.size();
int gap = len;
int temp = 0;
int i = 0,j = 0;
do{
gap /=3;
gap += 1;
for(i = gap +1;i<len;++i)
{
if(input[i]<input[i-gap])
{
temp = input[i];
for(j = i-gap;j>=0;j-=gap)
{
if(temp<input[j])
input[j+gap] = input[j];
else
break;
}
input[j+gap] = temp;
}
}
}while(gap>1);
return input;
}
/************************测试****************************************/
int main()
{
int input[] = {90,11,5,8,13,7,4,6,2};
// test01(2,5);
// test01(input[0],input[1]);
// for(int i = 0;i<9;++i)
// cout<<input[i]<<' ';
// cout<<endl;
vector<int> Input;
for(int i = 0;i<9;++i)
{
Input.push_back(input[i]);
}
Input = Heapsort(Input);
print(Input);
cout<<"/****************利用自带的数据结构进行堆排序*************************/"<<endl;
priority_queue<int, vector<int>, less<int> > a;
priority_queue<int, vector<int>, greater<int> > b;
for(int i = 0;i<9;++i)
{
a.push(input[i]);
b.push(input[i]);
}
while(!a.empty())
{
cout<<a.top()<<' ';
a.pop();
}
cout<<endl;
while(!b.empty())
{
cout<<b.top()<<' ';
b.pop();
}
}