排序算法总结！！！！

冒泡排序
稳定的排序，但是算法复杂度较高，
平均和最差都是：O(n^2)
空间复杂度为：O(1)
#include<stdio.h>
void bubble_sort(int a[],int n)
{
int i,j,tmp;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}
void main()
{
int a[10]={7,17,6,84,56,1,34,10,100,0};
bubble_sort(a,10); //快速排序
for(int i=0;i<10;i++)
{
printf("%d\n",a[i]);
}
}

插入排序
是稳定的排序
平均情况和最坏情况的算法复杂度为O(n^2)
最好情况为O(n)
空间复杂度为：O(1)。
#include<stdio.h>
void InsertSort(int a[],int n)
{
int i,j,rc;
for(i=1;i<n;i++)
{
if(a[i-1]>a[i])
{
rc=a[i];
j=i;
while(j-1>=0 && rc<a[j-1])
{
a[j]=a[j-1];
j--;
}
a[j]=rc;
}
}
}
void main()
{
int a[]={49,38,65,97,76,13,27,49};
int n=sizeof(a)/sizeof(a[0]);
InsertSort(a,n);
for(int i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
}

快速排序
不稳定的排序
但是算法复杂度低
平均算法复杂度为：O(nlgn)
最差为O(n^2)
空间复杂度为：O(lgn)
#include<stdio.h>
int PARTITION(int a[],int i,int j)
{
int key=a[i]; //记录关键字
while(i<j)
{
while(i<j && key<=a[j]) //向右扫描
j--;
//此时的j为key的位置
if(i<j)
a[i++]=a[j]; //交换位置
while(i<j && key>=a[i])
i++;
//此时的i为key的位置
if(i<j)
a[j--]=a[i]; //交换位置
}
a[i]=key; //key最终的位置
return i;
}
void qsort(int a[],int i,int j)
{
int pos; //关键字的位置
if(i<j)
{
pos=PARTITION(a,i,j);
qsort(a,i,pos-1);
qsort(a,pos+1,j);
}
}
void main()
{
int a[10]={7,17,6,84,56,1,34,10,100,0};
qsort(a,0,9); //快速排序
for(int i=0;i<10;i++)
{
printf("%d\n",a[i]);
}
}

选择排序
是不稳定排序
平均算法复杂度和最坏算法复杂度为：O(n^2)
空间复杂度为O(1)；
稳定性
举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法
#include<stdio.h>
void select_sort(int a[],int n)
{
int i,j,pos,tmp;
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++) //选取第i趟的最小元素
{
if(a[pos]>a[j])
{
pos=j;
}
}
tmp=a[pos];
a[pos]=a[i];
a[i]=tmp;
}
}
void main()
{
int a[]={49,38,65,97,76,13,27,49};
int n=sizeof(a)/sizeof(a[0]);
select_sort(a,n);
for(int i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
}

堆排序
是不稳定的排序
平均情况和最坏情况的算法复杂度为O(NlgN)
空间复杂度为：O(1)
#include<stdio.h>
#include<string.h>
void swap(int &a,int &b)
{
int tmp;
tmp=a;
a=b;
b=tmp;
}
void HeapAjust(int a[],int i,int n)
{
int rc=i;
int rs=a[rc];
for(int j=2*rc;j<=n;j*=2)
{
if(j<n&&a[j]<a[j+1]) //左右子树选个大的
j++;
if(rs>a[j]) //调整是否结束
break;
a[rc]=a[j]; //调整堆
rc=j; //继续向下
}
a[rc]=rs; //节点a[i]的最终位置
}
void HeapSort(int a[],int n)
{
int i;
for(i=n/2;i>0;i--) //成堆
{
HeapAjust(a,i,n);
}
for(i=n;i>1;i--) //交换，调整
{
swap(a[1],a[i]);
HeapAjust(a,1,i-1);
}
}
void main()
{
int a[10]={7,17,6,84,56,1,34,10,100,0};
int b[11];
memmove(b+1,a,sizeof(a));
HeapSort(b,10);
memmove(a,b+1,sizeof(a));
for(int i=0;i<10;i++)
{
printf("%d\n",a[i]);
}
}