《java培训-java实现的几个常用排序算法详细解读》由会员分享，可在线阅读，更多相关《java培训-java实现的几个常用排序算法详细解读（11页珍藏版）》请在金锄头文库上搜索。
1、Java实现的几个常用排序算法详细解读排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料。废话不多说，下面逐一看看经典的排序算法。排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料。废话不多说，下面逐一看看经典的排序算法：1. 选择排序选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 in-1 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。举个实
2、例来看看：1. 初始：38,17,16,16,7,31,39,32,2,11 2. 3. i=0:2,17,16,16,7,31,39,32,38,11(0th388th2) 4. 5. i=1:2,7,16,16,17,31,39,32,38,11(1st384th17) 6. 7. i=2:2,7,11,16,17,31,39,32,38,16(2nd119th16) 8. 9. i=3:2,7,11,16,17,31,39,32,38,16(无需交换) 10. 11. i=4:2,7,11,16,16,31,39,32,38,17(4th179th16) 12. 13. i=5:2,7,
3、11,16,16,17,39,32,38,31(5th319th17) 14. 15. i=6:2,7,11,16,16,17,31,32,38,39(6th399th31) 16. 17. i=7:2,7,11,16,16,17,31,32,38,39(无需交换) 18. 19. i=8:2,7,11,16,16,17,31,32,38,39(无需交换) 20. 21. i=9:2,7,11,16,16,17,31,32,38,39(无需交换)由例子可以看出，选择排序随着排序的进行（ i 逐渐增大），比较的次数会越来越少，但是不论数组初始是否有序，选择排序都会从 i 至数组末尾进行一次选择比
4、较，所以给定长度的数组，选择排序的比较次数是固定的： 1 + 2 + 3 + . + n = n * (n + 1) / 2 ，而交换的次数则跟初始数组的顺序有关，如果初始数组顺序为随机，则在最坏情况下，数组元素将会交换 n 次，最好的情况下则可能 0 次（数组本身即为有序）。由此可以推出，选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) （选择排序只需要一个额外空间用于数组元素交换）。实现代码：1. /* 2. *SelectionSorting 3. */4. SELECTION(newSortable() 5. publicTextendsComparablevoids
5、ort(Tarray,booleanascend) 6. intlen=array.length; 7. for(inti=0;ilen;i+) 8. intselected=i; 9. for(intj=i+1;jlen;j+) 10. intcompare=pareTo(arrayselected); 11. if(compare!=0&compare0=ascend) 12. selected=j; 13. 14. 15. 16. exchange(array,i,selected); 17. 18. 19. )2. 插入排序插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的
6、元素即 0.i-1 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，插入排序也是根据排序的特性来命名的。以下是一个实例，红色 标记的数字为插入的数字，被划掉的数字是未参与此次排序的元素，红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素，比如第二趟参与排序的元素为 11, 31, 12 ，需要插入的元素为 12 ，但是 12 当前并没有处于正确的位置，于是我们需要依次与前面的元素 31 、 11 做比较，一边比较一边移动比较过的元素，直到找到第一个
7、比 12 小的元素 11 时停止比较，此时 31 对应的索引 1 则是 12 需要插入的位置。1. 初始：11,31,12,5,34,30,26,38,36,18 2. 3. 第一趟：11,31,12,5,34,30,26,38,36,18（无移动的元素） 4. 5. 第二趟：11,12,31,5,34,30,26,38,36,18（31向后移动） 6. 7. 第三趟：5,11,12,31,34,30,26,38,36,18（11,12,31皆向后移动） 8. 9. 第四趟：5,11,12,31,34,30,26,38,36,18（无移动的元素） 10. 11. 第五趟：5,11,12,30,
8、31,34,26,38,36,18（31,34向后移动） 12. 13. 第六趟：5,11,12,26,30,31,34,38,36,18（30,31,34向后移动） 14. 15. 第七趟：5,11,12,26,30,31,34,38,36,18（无移动的元素） 16. 17. 第八趟：5,11,12,26,30,31,34,36,38,18（38向后移动） 18. 19. 第九趟：5,11,12,18,26,30,31,34,36,38（26,30,31,34,36,38向后移动）插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次
9、数，当然这种优势得看数组的初始顺序如何，最坏的情况下（给定的数组恰好为倒序）插入排序需要比较和移动的次数将会等于 1 + 2 + 3 + n = n * (n + 1) / 2 ，这种极端情况下，插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法，插入效率与数组初始顺序息息相关。一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。实现代码：1. /* 2. *InsertionSorting 3. */4. INSERTION(newSortable() 5. publicTextendsComparablevoidsort(Tarray,boo
10、leanascend) 6. intlen=array.length; 7. for(inti=1;i0;j-) 11. intcompare=arrayj-pareTo(toInsert); 12. if(compare=0|compare0=ascend) 13. break; 14. 15. arrayj=arrayj-1; 16. 17. 18. arrayj=toInsert; 19. 20. 21. )3. 冒泡排序冒泡排序可以算是最经典的排序算法了，记得小弟上学时最先接触的也就是这个算法了，因为实现方法最简单，两层 for 循环，里层循环中判断相邻两个元素是否逆序，是的话将两个元
11、素交换，外层循环一次，就能将数组中剩下的元素中最小的元素“浮”到最前面，所以称之为冒泡排序。照例举个简单的实例吧：1. 2. 3. 初始状态：24,19,26,39,36,7,31,29,38,23 4. 5. 内层第一趟：24,19,26,39,36,7,31,29,23,38（9th238th38） 6. 7. 内层第二趟：24,19,26,39,36,7,31,23,29,38（8th237th29） 8. 9. 内层第三趟：24,19,26,39,36,7,23,31,29,38（7th236th31） 10. 11. 内层第四趟：24,19,26,39,36,7,23,31,29,38（7、23都位于正确的顺序，无需交换） 12. 13. 内层第五趟：24,19,26,39,7,36,23,31,29,38（5th74th36） 14. 15. 内层第六趟：24,19,26,7,39,36,23,31,29,38（4th73rd39） 16. 17. 内层第七趟：24,19,7,26,39,36,23,31,29,38（3rd72nd26）
