文档介绍：排序算法
姓名:邓海波
学号:2013222053
年级:2013 级
专业: 生物信息学
算法介绍
排序算法是为了解决输入的n个数的一个序列{,,...,},经过我们的排序后输出已排好的序列{,,...,}(满足≤≤...≤)。我们将通过不同的排序算法解决这个问题,比如选择排序、插入排序、冒泡排序、快速排序、堆排序、归并排序、希尔排序、基数排序等,并通过对其时间复杂度进行对比进而得出相应的结论。
基本算法
选择排序
选择排序的基本思想是: 对待排序的n个数据进行n-1遍的处理,第1遍处理是将a[2..n]中最小者与a[1]交换位置,第2遍处理是将a[3..n]中最小者与a[2]交换位置,......,第i遍处理是将a[i+1..n]中最小者与a[i]交换位置。这样,经过i遍处理之后,前i个记录的位置就已经按从小到大的顺序排列好了。总共比较 n(n-1)/2 次,时间复杂度为(),其稳定性为不稳定(稳定性是指值相同的数字在排序前后其相对位置是否要发生改变,若要改变就是不稳定,否则就是稳定的。)
算法代码:
main()
{
int flag,temp,i,j,a[10]={12,33,45,67,89,99,45,11,22,48};
printf("源程序为:\n");
for(i=0;i<10;i++)
printf("%-3d",a[i]);
for(i=0;i<9;i++)
{
flag=i;
for(j=i+1;j<10;j++)
{
if(a[flag]>a[j])
{
flag=j;
}
}
if(i!=flag)
{
temp=a[flag];
a[flag]=a[i];
a[i]=temp;
}
}
printf("\n排序后为:\n");
for(i=0;i<10;i++)
{
printf("%-3d",a[i]);
}
}
冒泡排序
冒泡排序基本思想是:对待排序的数字进行两两比较,如发现两个数字是反序的,则进行交换,直到无反序的记录为止(此处是按从大到小的顺序排列)。总共比较 n(n-1)/2 次,时间复杂度为(),是稳定的排序算法。
算法代码:
main()
{
int i,j,l,a[10]={9,89,90,23,56,12,45,67,36,99};
printf("源程序为:\n");
for(i=0;i<10;i++)
{
printf("%-3d",a[i]);
}
printf("\n");
printf("排序后为:\n");
for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
{
if(a[i]>a[j])
{
l=a[i];
a[i]=a[j];
a[j]=l;
}
}
}
for(i=0;i<10;i++)
{
printf("%-3d",a[i]);
}
}
插入排序
有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法--插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为()。是稳定的排序方法。
算法代码:
void insert(int a[],int leng)
{
int i,j,key;
for(i=1;i<leng;i++)
{
key=a[i];
j=i-1;
while(j>=0 && a[j]<key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
main()
{
int a[]={23,56,88,97,45,33,11,3,89,67},i,j;
printf("源数组为:\n");
for(i=0;i<10;i++)
{
printf("%-3d",a[i]);
}
insert(a,10);
printf("\n插入后序列为:\n");
for(j=0;j<10;j++)
{
printf("%-3d",a[j]);
}
}
快速排序
思想:每次找一个数位基准,把小于等于它的放到这个数的左边,把大于等于它的放到它的右边,每排完一趟,小于等于基准值的,在其左侧。大于等于基准值的在其右侧。
平均时间复杂度:()是不稳定的排序算法。
算法代码:
void q