排序算法论文.docx

排序算法

姓名：邓 海 波

学号：2013222053

年级：2013 级

专业: 生物信息学

一、 算法介绍
排序算法是为了解决输入的n个数的一个序列{,,...,},经过我们的排序后输出已排好的序列{,,...,}(满足≤≤...≤)。我们将通过不同的排序算法解决这个问题，比如选择排序、插入排序、冒泡排序、快速排序、堆排序、归并排序、希尔排序、基数排序等，并通过对其时间复杂度进行对比进而得出相应的结论。
二、 基本算法
1、 选择排序
选择排序的基本思想是： 对待排序的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]);
}
}
2、 冒泡排序
冒泡排序基本思想是:对待排序的数字进行两两比较,如发现两个数字是反序的,则进行交换,直到无反序的记录为止（此处是按从大到小的顺序排列）。总共比较 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]);
}
}
3、 插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法--插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为()。是稳定的排序方法。
算法代码：
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]);
}
}
4、 快速排序
思想：每次找一个数位基准，把小于等于它的放到这个数的左边，把大于等于它的放到它的右边，每排完一趟，小于等于基准值的，在其左侧。大于等于基准值的在其右侧。平均时间复杂度：()是不稳定的排序算法。
算法代码：

void quiksort(int a[],int low,int high)
{
int i = low;
int j = high;
int temp = a[i];
if( low < high)
{
while(i < j)
{
while((a[j] >= temp) && (i < j))
{
j--;
}
a[i] = a[j];
while((a[i] <= temp) && (i < j))
{
i++;
}
a[j]= a[i];
}
a[i] = temp;
quiksort(a,low,i-1);
quiksort(a,j+1,high);
}
else
{
return;
}
}
void main()
{
int arry[11] = {2,32,43,23,45,36,57,14,27,39,11},i;
printf("源程序为：\n");
for(i=0;i<11;i++)
{
printf("%d ",arry[i]);
}
printf("\n");
quiksort(arry,0,10);
printf("排序后为：\n");
for(i=0;i<11;i++)
{
printf("%d ",arry[i]);
}
printf("\n");
}
5、 堆排序
堆的定义:n个元素的序列{,,...,}，当≤&≤时我们称为最小化堆或小顶堆，当≥&≥时我们称为最大化堆或大顶堆(i=1,2,...,n)。由此，若序列{,,...,}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。
排序过程：堆排序是一种选择排序。建立的初始堆为初始的无序区。
排序开始，首先输出堆顶元素（因为它是最值），将堆顶元素和最后一个元素交换，这样，第n个位置（即最后一个位置）作为有序区，前n-1个位置仍是无序区，对无序区进行调整，得到堆之后，再交换堆顶和最后一个元素，这样有序区长度变为2，不断进行此操作，将剩下的元素重新调整为堆，然后输出堆顶元素到有序区。每次交换都导致无序区-1，有序区+1。不断重复此过程直到有序区长度增长为n-1，排序完成。
想得到升序，则建立大顶堆，若想得到降序，则建立小顶堆。堆排序在最坏的情况下，其时间复杂度：()是不稳定的排序算法。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小的供交换用的辅助存储空间。
算法代码：
/*堆排序 实现，算法复杂度O(nlgn)*/
#include<stdio.h>
#include<stdlib.h>
/*假设节点i的左右子树都是最大堆，操作使节点i的子树变成最大堆*/
void maxHeap(int A[],int len,int i)
{
int l,r,large,temp;
l=2*i;
r=2*i+1;
large=i;
if(l<len)
{
if(A[l]>A[i])
{
large=l;
}
}
if(r<len)
{
if(A[r]>A[large])
{
large=r;
}
}

if(large!=i)
{
temp=A[large];
A[large]=A[i];
A[i]=temp;
maxHeap(A,len,large);
}
}
/*建立大根堆*/
void buildMaxHeap(int A[],int len)
{
int i;
for(i=len/2-1;i>=0;i--)
maxHeap(A,len,i);
}
/*堆排序*/
void maxHeapSort(int A[],int len)
{
int i,temp;
buildMaxHeap(A,len);
printf("建立大跟堆:\n");
for(i=0;i<len;i++)
printf("%-3d",A[i]);
printf("\n");
printf("大跟堆序列为:\n");
for(i=len;i>1;i--)
{
temp=A[0];
A[0]=A[i-1];
A[i-1]=temp;
printf("%-3d",A[i-1]);
buildMaxHeap(A,i-1);
}
printf("\n");
}
/*测试堆排序*/
int main()
{
int i;
int A[11]={4,11,38,23,16,98,10,14,81,78,66};
printf("源序列为：\n");
for(i=0;i<11;i++)
{
printf("%-3d",A[i]);
}
printf("\n");
maxHeapSort(A,11);

printf("排序后为：\n");
for(i=0;i<11;i++)
{
printf("%-3d",A[i]);
}
printf("\n");
}

三、 总结
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。其时间复杂度也不相同，虽然各自的排序原理不同，但是排序的最终结果相同。