1 插入排序
插入排序：将待排序的值插入到前面已排序的序列中，直到所有元素都已经插入。
1.1 直接插入排序
//直接插入排序
for(j=1;j<size;j++)
{
tmp=a[j];
for(k=j-1;k>=0&&a[k]>tmp;k--)
a[k+1]=a[k];
a[k+1]=tmp;
}时间复杂度分析
最好情况：O（n） [各只需要比较一次]
最坏情况：O（n^2）
平均情况：O（n^2）
如果使用二分插入排序，能使比较次数降低到O（nlogn），但移动次数仍然是O（n^2）
上面的直接插入排序是稳定排序 。
1.2 希尔排序
//希尔排序
//按照希尔的建议，选取增量序列N/2...1
for(step=size/2;step>0;step/=2)
{
for(j=step;j<size;j+=step)
{
tmp=a[j];
for(k=j-step;k>=0&&a[k]>tmp;k-=step)
a[k+step]=a[k];
a[k+step]=tmp;
}
}时间复杂度分析：
在O（n）与O（n^2）之间，大约O（n^1.25）
希尔排序是不稳定排序 ，例如1 3 4 2 2， H={2,1}
2 选择排序
选择排序：在n个元素中找到最小的元素作为排序后第一个元素，然后从剩下的n-1个元素中再找最小的元素作为排序后第二个元素，...，重复上述过程
2.1 直接选择排序
//直接选择排序
for(i=0;i<size-1;i++)
{
min=i;
for(j=i+1;j<size;j++)
{
if(a[j]<a[min]) min=j;
}
tmp=a[i];
a[i]=a[min];
a[min]=tmp;
}时间复杂度分析：
O（n^2）
直接选择排序是不稳定排序，例如2 2 3 2 1。
2.2 堆排序
//堆排序
//下滤函数（小下大上）
void percolateDown(int a[],int hole,int size)
{
tmp=a[hole];
for(;hole<=size/2;hole=child)
{
child=2*hole;
if(child!=size&&a[child+1]>a[child])
child++;
if(a[child]>a[hole]) a[hole]=a[child];
else break;
}
a[hole]=tmp;
}
void HeapSort(int a[],size)
{
//构建大顶堆
for(int i=size/2;i>=1;i--)
percolateDown(a,i,size);
//逐个删除堆顶元素（与堆尾元素交换，然后下滤）
for(int i=size-1;i>0;--i)
{
tmp=a[0];
a[0]=a[i];
a[i]=tmp;
percolateDown(a,0,size);
}
}时间复杂度分析：
下滤时间复杂度O（logN），堆排序时间复杂度O（NlogN）
堆排序是不稳定排序。
3 交换排序
交换排序：通过比较元素的值来判断是否要交换元素的值
3.1 冒泡排序
//冒泡排序
for(int i=1;i<size-1&&flag=true;i++)
{
flag=false;
for(j=0;j<size-i;j++)
{
if(a[j]>a[j+1])
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
flag=false;
}
}
}时间复杂度分析：
最好情况：O（N）
平均/最坏情况：O（N^2）
冒泡排序是稳定排序。
3.2 快速排序 、
基于分治法实现。
//快速排序
//分划函数
int divide(int a[],int low,int high)
{
k=a[low];
do{
while(low<high&&a[high]>=k) high--;
{
a[low]=a[high];
low++;
}
while(low<high&&a[low]<=k) low++;
{
a[high]=a[low];
high--;
}
}while(low<high)
return low;
}
void quickSort(int a[],int low,int high)
{
//递归结束条件
if(low>=high) return;
//分划
int mid=divide(a,0,size-1);
//两边排序
quickSort(a,0,mid-1);
quickSort(a,mid+1,high);
}
void quickSort(int a[],int size)
{
quickSort(a,0,size-1);
}时间复杂度分析：
最坏情况（有序/逆序）：O（N^2）
平均情况：O(NlogN) ->认为最快的内排序算法
快速排序是不稳定排序。
4 归并排序
归并排序：基于有序线性表的合并，基于分治法实现。
//归并排序
void merge(int a[],int low,int mid,int high)
{
*tmp= new int[high-low+1];
int i=low;
int j=mid;
int k=0;
while(i<mid&&j<=high)
{
if(a[i]<a[j]) tmp[k++]=a[i++];
else tmp[k++]=a[j++];
}
while(i<mid) tmp[k++]=a[i++];
while(j<=high) tmp[k++]=a[j++];
for(i=0,k=low;k<=high;) a[k++]=tmp[i++];
delete[] tmp;
}
void mergeSort(int a[],int low,int high)
{
if(low==high) return;
int mid=(low+high/2;
//先对两边进行排序
mergeSort(a,low,mid-1);
mergeSort(a,mid,high);
merge(a,low,mid-1,high);
}
void mergeSort(int a[],int size)
{
mergeSort(a,0,size-1);
}时间复杂度分析：
O（NlogN）
归并排序是稳定排序。
5 基数排序
基数排序：通过分配的方法对整数进行排序。
时间复杂度分析：
最大位数为len，则经过len次分配和重组，重组需要10次链接，分配需要遍历所有元素，
时间复杂度O（len*n）
基数排序是稳定排序。