《各种排序算法的分析及java实现》由会员分享，可在线阅读，更多相关《各种排序算法的分析及java实现（20页珍藏版）》请在金锄头文库上搜索。
1、各种排序算法的分析及java实现排序一直以来都是让我很头疼的事，以前上数据结构打酱油去了，整个学期下来才勉强能写出个 冒泡排序。由于下半年要准备工作了，也知道排序算法的重要性(据说是面试必问的知识点)，所以又花 了点时间重新研究了一下。排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序， 如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。内排序有可以分为以下几类：(1) 、插入排序：直接插入排序、二分法插入排序、希尔排序。(2) 、选择排序：简单选择排序、堆排序。(3) 、交换排序：冒泡排序、快速排序。(4) 、归并排序(5) 、基数排
2、序一、插入排序思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插 入排序完为止。关键问题：在前面已经排好序的序列中找到合适的插入位置。方法：-直接插入排序-二分插入排序-希尔排序直接插入排序(从后向前找到合适位置后插入)1、基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置(从 后向前找到合适位置后)，直到全部插入排序完为止。初始状态57 68 59 5257 68 59 5257 59 68 526857, 不处理I1 O57 68 59 525257,摘在町之前结果；52 57 59 68a二49,38, 65,9
3、7,76,13,27,49,7& 34,12,64,1;System.out.println(排序之前：)；(in t i 二 0; i a.leng th; i+) Sys tem.o ut .pri nt( ai+);57596Br插在57之后3、java实现曲lpackage com.sor t;23publicclass直接插入排序45publicstaticvoid main(String args) 6int 78for911/直接插入排序12for (int i 二 1; i temp)2324 25break;262728ai;i-1; j=0 & ajtemp; j) /将大
4、于temp的往后移动一位 aj+1 = aj;*/i-1; j=0; j-) aj+1 = aj; else aj+1 = temp;1030 Sys tem.o ut .pri ntln();31 System.out.println(排序之后：)； 32for (int i 二 0; i 36)36!69 42=152736thigh1527363、java实现flow t high.Tnitd(4253 )69 42lpackage com.sor t;23publicclass二分插入排序4publicstaticvoid main(String args) 5int 67for89a
5、=49,38,65,97,176,213,227,49,78,34,12,164,11,18,1;System.out.println(排序之前：)；(in t i 二 0; i a.leng th; i+) Sys tem.o ut .pri nt( ai+);10/二分插入排序11121314for1516171819priva testati cvoid sor t(int a) 20for21in t22in t23in t24in tsor t( a);Sys tem.o ut .pri ntln();System.out.println(排序之后：);(in t i 二 0; i
6、a.leng th; i+) Sys tem.o ut .pri nt( ai+);(int i 二 0; i a.length; i+) ai;0;=i-1;0;t emp = lef t 二 righ t mid =25while (lef t 二righ t)2627i f(t emp= left; j-) aj+1 = aj;i)aleft二 temp;当然，二分法插入排序也是稳定的。二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。当n较大时，比直接 插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序 算法的相同，最坏的情
7、况为n2/2,最好的情况为n,平均移动次数为O(n2)。希尔排序1、基本思想：先取一个小于n的整数di作为第一个增量，把文件的全部记录分成di个组。所有距 离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复 上述的分组和排序，直至所取的增量dt=1(dtdt-ld2dl),即所有记录放在同一组中进行直接插入排 序为止。该方法实质上是一种分组插入方法。57685952722896332419d2=di/2=368332419965952572419332859527296571924283352575968723、java实现2、实例di=n/2=5取
8、奇数lpackage com.sor t;23/不稳定4publicclass 希尔排序567publicstaticvoid main(String args) 8int a二49,38, 65,97,76,13,27,49,7& 34,12,64,1;9 System.out.println(排序之前：)；10for (int i 二 0; i a.leng th; i+) 11 Sys tem.o ut .pri nt( ai+);12 13/希尔排序14i nt d = a.leng th;15while (true)16d = d / 2;17for(i nt x=O;xd;x+)1
9、8for(i nt i二x+d;i=0 & aj temp;j二j-d)22aj+d = aj2324aj+d = temp;252627if(d =1)28break;293031Sys tem.o ut .pri ntln();32Sys tem.o ut .pri ntln(排序之后:33for (inti = 0; i a.leng th; i+) 34 Sys tem.o ut .pri nt( ai+);35 36 3737 俞4、分析我们知道一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中 移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。希尔
10、排序的时间性能优于直接插入排序，原因如下：(1) 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。(2) 当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度0(n)和最坏时间复杂 度0(n2)差别不大。(3) 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量 di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件 较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插人排序有较大的改进。希尔排序的平均时间复杂度为0(nlogn)。二、选择排序思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。 关键问题：在剩余的待排序记录序列中找到最小关键码记录。方法：-直接选择排序堆排序 简单的选择排序1、基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中 再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。2、实例初始状态57 68 59 52O 最小值为5乙与第一个交换52 68 59 57最小值为5人与第二个交换52 57J59 68 阳就是最小值，无需交换.完成52 57 59 683、java实现lpackage c
