接下来，我们就来到了排序的章节，嘿嘿！加油！
冒泡排序
代码语言：javascript复制void BubbleSort(int* a,int n)
{
for(int j=0;j<n;i )
{
for(int i=1;i<n-j;i )
{
if(arr[i-1]>arr[i])
{
swap(&arr[i-1],&arr[i]);
}
}
}
}插入排序
时间复杂度：O（N^2），什么情况下最坏：逆序
最好：顺序有序，O（N）
代码语言：javascript复制void InsertSort(int* a,int n)
{
for(int i=0;i<n-1;i )
{
int end;
int tmp=a[end 1];//如果小，原有end 1的位置上就要往后覆盖，所以要把原有end 1位置的值往后挪
//[0,end]有序，end 1位置的值插入
while(end>=0)
{
if(a[end]>tmp)
{
a[end 1]=a[end];
--end;
}
else
{
break;
}
a[end 1]=tmp;
}
}希尔排序
1、预排序（接近有序） gap组
2、插入排序
代码语言：javascript复制void ShellSort(int*a,int n)
{
int gap=3;
for(int j=0;j<i;j )
{
for(size_t i=j;i<n-gap;i =gap)
{
int end=0;
int tmp=a[end gap];
while(end>=0)
{
if(tmp<a[end])
{
a[end gap]=a[end];
end-=gap;
}
else
{
break;
}
}
a[end gap]=tmp;
}
}我们可以观察到gap等于1，实际上就是插入排序。
绿色和紫色这两组仍然需要排序。
那么，我们在外面再加上一层排序就可以了。
如果我们把两次循环改为一次循环，该怎么改呢？
代码语言：javascript复制void ShellSort(int*a,int n)
{
int gap=n;
while(gap>1)
{
gap=gap/3 1;//保证最后一次插入时gap是1
for(size_t i=0;i<n-gap;i--)
{
int end=0;
int tmp=a[end gap];
while(end>=0)
{
if(tmp<a[end])
{
a[end gap]=a[end];
end-=gap;
}
else
{
break;
}
}
a[end gap]=tmp;
}
}希尔排序时间复杂度：O（N^1.3）
每组数据个数等于n/gap
最坏情况下，gap/3，第一趟预排序的消耗：（1 2）*n/3(组数）=n
gap/9，每组消耗：（1 2 .... 8）*n/9=4n
最后一趟：已经很接近有序了，就是直接插入排序，消耗为n
选择排序
代码语言：javascript复制void SelectSort(int* a,int n)
{
int begin=0,end=n-1;
int mini=begin,maxi=begin;
for(int i=begin 1;i<=end;i )
{
if(a[i]>a[max])
{
maxi=i;
}
if(a[i]<a[mini])
{
mini=i;
}
begin;
--end;
}
