资源描述：
《排序算法总结范文.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、排序算法总结范文 //插入排序代码给定待排序序列A[1.....n]，现假设A[1...i]已经有序，那么我们取出A[i+1]插入到序列A[1...i].这样有序序列记录数就增加了1.如此重复上述操作，不断取出记录插入有序序列，直到A[n]插入到有序序列，排序完成。 publilassmain{/***@paramargs*/staticvoidstraightInsert(int[]s,intlengths){intj;inttemp;for(inti=1;i=0;j‐‐){if(temps[j]{s[j+1]=s[j];}elsebreak
2、;System.out.print(j);}System.out.println(j);s[j+1]=temp;}}publicstaticvoidmain(String[]args){//TODOAuto‐generatedmethodstubint[]arr={5,7,6,9,2,8,3};straightInsert(arr,7);for(intm=0;m 在最佳情况下（待排序序列有序），比较次数和移动次数时间为o （1），所以时间复杂度为o（n）.在最坏情况下（待排序序列逆序）和平均时间均为o（n^2）.从上述分析中可以看出，直接插入排
3、序适合记录数比较少、给定序列基本有序的情况。 熟悉了排序过程我们发现，直接插入排序是一种稳定的原地排序算法。 最坏情况n(n-1)/2//折半插入排序在直接插入排序过程中，我们是把一个记录插入到有序序列中，至于要插入到有序序列中的哪个位置呢？采用的是顺序查找确定插入的位置。 显然对于有序序列，折半查找的效率要高，所以在寻找插入位置时可以用折半查找。 折半查找主要分为三步 1、查找要插入的位置 2、移位 3、把记录插入相应的位置。 publilassmain{publicstaticintbinarySearch(int[]s,int
4、low,inthigh,inttarget){intmid=(low+high)/2;if(low>high)returnlow;if(s[mid]==target)returnmid;elseif(target>s[mid])//改为targetsite;j‐‐){s[j]=s[j‐1];}s[site]=temp;}}publicstaticvoidmain(String[]args){int[]l={5,2,23,545,235,56,44,2,4};binaryInsertSort(l,l.length);for(intw=0;w 再来看
5、一下最佳情况（待排序序列有序），此时关键字比较次数并不为o （1），时间复杂度为o（n*log2n）。 （其中折半查找时间复杂度o（log2n），这个在以后写查找的时候再分析，这里不做详细讲解。 ）。 所以在记录数较小、待排序序列基本有序情况下直接插入排序优于折半插入排序。 此外，折半插入排序是不稳定的原地排序，实现起来也较复杂。 //希尔排序上述两种排序都是只考虑减少关键字比较次数或者只考虑减少关键字移动次数。 有没有别的改进办法呢？我们注意到，直接插入排序适合于记录数较少、基本有序的情况。 于是我们可以先将整个待排序序列分割成若
6、干子序列分别进行直接插入排序，整个序列基本有序时，再对序列进行一次直接插入排序。 这就是希尔排序。 publilassmain{//增量为dk的希尔插入排序publicstaticvoidshellInsert(int[]s,intlengths,intdk){inti,j;inttemp;for(i=dk;i=0;j‐=dk){if(s[j]>temp)s[j+dk]=s[j];elsebreak;}s[j+dk]=temp;}}publicstaticvoidshellSort(int[]s,intlengths){int[]dk={5,4
7、,3,2,1};for(inti=0;i 再希尔排序的过程中，关键字是跳跃式移动的，这样就减少了移动次数。 希尔排序性能的分析是一个复杂的问题，时间与所取的增量有关。 增量选取的不好可能会大大降低排序效率。 //冒泡排序插入排序是基于“逐个记录插入”，选择排序是基于“选择”，那么冒泡排序其实是基于“交换”。 每次从第一个记录开始， 一、二两个记录比较，大的往后放，二三两个记录比较...依次类推，这就是一趟冒泡排序。 每一趟冒泡排序后，无序序列中值最大的记录冒到序列末尾，所以称之为冒泡排序。 publilassmain{//冒泡排序p
8、ublicstaticvoidbubbleSort(int[]s,intlengths){for(inti=0;is[j+
