常见排序算法总结

《常见排序算法总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、常见排序算法总结【转载+整合】2009-09-1415:171、稳定排序和非稳定排序简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳

2、定的了。2、内排序和外排序在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。3、算法的时间复杂度和空间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。=======================================一.插入排序首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。重复2号步骤，直至原

3、数列为空。插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。①.直接插入排序(稳定)    接插入排序的过程为：在插入第i个记录时，R1,R2,..Ri-1已经排好序，将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。代码如下:voidDir_Insert(intA[],intN)  //直接插入排序{    intj,t;    for(inti=1;i

4、   t=A[i];        j=i-1;        while(A[j]>t)        {            A[j+1]=A[j];            j--;        }        A[j+1]=t;    }}②.希尔排序(不稳定)：    希尔(Shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二个增量d2

5、种分组插入方法。    一般取d1=n/2，di+1=di/2。如果结果为偶数，则加1，保证di为奇数。    希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平均时间复杂度为O(n^1.3).代码如下:voidShell(intA[],intn)  //Shell排序{    inti,j,k,t;    (n/2)%2==0?k=n/2+1:k=n/2;//保证增量为奇数    while(k>0)    {        for(j=k;j

6、le(i>=0&&A[i]>t)            {                A[i+k]=A[i];                i=i-k;            }            A[i+k]=t;        }        if(k==1)break;        (k/2)%2==0?k=k/2+1:k=k/2;    }}==============================================二.选择排序设数组内存放了n个待排数字，数组下标从1开始，到n结束。i=1从数组的第i个元素开始到第n个元素，寻找最小的元素。将上一步找

7、到的最小元素和第i位元素交换。如果i=n－1算法结束，否则回到第3步①.直接选择排序(不稳定)    直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换......依次类推，直到所有记录排完为止。    无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较，因此，总的比较次数为n(n-1)/2=O(n^2)。当初始文件为正序