排序算法

插值排序法 时间复杂度o(n^2) 空间复杂度o(1)
vector<int> arrary;
for(int i = 1; i < arrary.size(); ++i)
{
for(int j = i; j -1 >= 0 && arrary[j] < arrary[j + 1]; --j)
{
swap(arrary, j, j - 1);
}
}

希尔排序 时间复杂度o(n^1.3) 空间复杂度o(1)
vector<int> arrary;
for(int gap = arrary.size()/2; gap > 0; gap/=2)
{
for(int i = gap; i < arrary.size(); ++i)
{
for(int j = i; j - gap >0 && arrary[j] < arrary[j-gap]; j-=gap)
{
swap(arrary, j, j-gap);
}
}
}

冒泡排序 时间复杂度o(n^2) 空间复杂度o(1)
vector<int> arrary;
for(int i = 1; i < arrary.size(); ++i)
{
bool flag = false;
for(int j=0; j < arrary.size() - i; ++j)
{
if(arrary[j] > arrary[j + 1])
{
swap(arrary, j, j+1);
flag=true;
}
}
if(flag) break;
}

选择排序 时间复杂度o(n^2) 空间复杂度o(1)
vector<int> arrary;
for(int i = 1; i < arrary.size(); ++i)
{
int maxpos = arrary.size() - i;
for(int j=0; j < arrary.size() - i; ++j)
{
if(arrary[j] > arrary[maxpos])
maxpos=j;
}
if(maxpos != arrary.size() - i)
swap(arrary, maxpos, arrary.size() - i);
}

插值排序与冒泡排序区别：
插值排序是往已排序区插入当前数，冒泡排序是从未排序区通过相邻数据交换取出最大值放到一端。
插值排序已排序区不稳定，不是最大（最小）的数值排序，冒泡排序已排序区是最大（最小）的数值排序
插值排序在往已排序区插入数据时，只要找到适当地位子就结束，冒泡排序需要变量所有未排序区数据才能确认最大值

选择排序与冒泡排序的区别：
选择排序与冒泡排序本质都是从未排序取取最大（最小）值放到一端，
不同地是选择排序通过遍历所有未排序取数值，取得最大（最小）值下标，然后放到一端，而冒泡排序是通过未排序取相邻数据两两交换得去最大（最小）值放到一端。