2022年常用排序算法分析与实现 .pdf

《2022年常用排序算法分析与实现 .pdf》由会员分享，可在线阅读，更多相关《2022年常用排序算法分析与实现 .pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、这篇排序文章从思想理解 到实现，然后到整理，花了我几天的时间，现把它记录于此，希望对大家有一定的帮助，写的不好的请不要见笑，写错了的，请指出来我更正。最后如果对你有一定的帮助，请回贴支持一下哦 _ ！申明： 排序算法思想来自互联网，代码自己实现，仅供参考。插入排序直接插入排序、希尔排序选择排序简单选择排序、堆排序交换排序冒泡排序、快速排序归并排序基数排序排序基类Java 代码1. package sort; 2.3. import java.util.Arrays; 4. import java.util.Comparator; 名师资料总结 - - -精品资料欢迎下载 - - - - - -

2、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - 5. import java.util.Random; 6.7. /* 8. * 排序接口，所有的排序算法都要继承该抽象类，并且要求数组中的9. * 元素要具有比较能力，即数组元素已实现了Comparable接口10. * 11. * author jzj 12. * date 2009-12-5 13. * 14. * param 15. */ 16.public abstract class SortE extends Comparabl

3、e 17. 18. public final Comparator DEFAULT_ORDER = new DefaultComparator(); 19. public final Comparator REVERSE_ORDER = new ReverseComparator(); 20. 21. /* 22. * 排序算法，需实现，对数组中指定的元素进行排序23. * param array 待排序数组24. * param from 从哪里25. * param end 排到哪里26. * param c 27. */ 28. public abstract void sort(E a

4、rray, int from, int end, Comparator c); 29. 30. /* 31. * 对数组中指定部分进行排序32. * param from 从哪里33. * param len 排到哪里34. * param array 待排序数组35. * param c 比较器36. */ 37. public void sort(int from, int len, E array, Comparator c) 38. sort(array, 0, array.length - 1, c); 39. 40. 41. /* 42. * 对整个数组进行排序，可以使用自己的排序

5、比较器，也可使用该类提供的两个比较器43. * param array 待排序数组名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - 44. * param c 比较器45. */ 46. public final void sort(E array, Comparator c) 47. sort(0, array.length, array, c); 48. 49. 50. /* 51. * 对整个数组进行排序，采用默认排序比较

6、器52. * param array 待排序数组53. */ 54. public final void sort(E array) 55. sort(0, array.length, array, this.DEFAULT_ORDER); 56. 57. 58. /默认比较器 （一般为升序， 但是否真真是升序还得看E是怎样实现Comparable接口的）59. private class DefaultComparator implements Comparator 60. public int compare(E o1, E o2) 61. return pareTo(o2); 62. 6

7、3. 64. 65. /反序比较器，排序刚好与默认比较器相反66. private class ReverseComparator implements Comparator 67. public int compare(E o1, E o2) 68. return pareTo(o1); 69. 70. 71. 72. /* 73. * 交换数组中的两个元素的位置74. * param array 待交换的数组75. * param i 第一个元素76. * param j 第二个元素77. */ 78. protected final void swap(E array, int i, i

8、nt j) 79. if (i != j) /只有不是同一位置时才需交换80. E tmp = arrayi; 81. arrayi = arrayj; 82. arrayj = tmp; 83. 84. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - 85. 86. /* 87. * 数组元素后移88. * param array 待移动的数组89. * param startIndex 从哪个开始移90. * param

9、endIndex 到哪个元素止91. */ 92. protected final void move(E array, int startIndex, int endIndex) 93. for (int i = endIndex; i = startIndex; i-) 94. arrayi + 1 = arrayi; 95. 96. 97. 98. /* 99. * 以指定的步长将数组元素后移，步长指定每个元素间的间隔100. * param array 待排序数组101. * param startIndex 从哪里开始移102. * param endIndex 到哪个元素止103.

10、 * param step 步长104. */ 105. protected final void move(E array, int startIndex, int endIndex, int step) 106. for (int i = endIndex; i = startIndex; i -= step) 107. arrayi + step = arrayi; 108. 109. 110.111. /测试方法112.SuppressWarnings (unchecked) 113. public static final E extends Comparable void test

11、Sort(Sort sorter, E array) 114.115. if (array = null) 116. array = randomArray(); 117. 118. /为了第二次排序，需拷贝一份119. E tmpArr = (E) new Comparablearray.length; 120. System.arraycopy(array, 0, tmpArr, 0, array.length); 121.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，

12、共 22 页 - - - - - - - - - 122. System.out.println(源 - + Arrays.toString(tmpArr); 123.124. sorter.sort(array, sorter.REVERSE_ORDER); 125. System.out.println(降 - + Arrays.toString(array); 126.127. sorter.sort(tmpArr, sorter.DEFAULT_ORDER); 128. System.out.println(升 - + Arrays.toString(tmpArr); 129. 130

13、.131. /生成随机数组132.SuppressWarnings (unchecked) 133. private static E extends Comparable E randomArray() 134. Random r = new Random(System.currentTimeMillis();135. Integer a = new Integerr.nextInt(30); 136. for (int i = 0; i a.length; i+) 137. ai = new Integer(r.nextInt(100); 138. 139. return (E) a; 1

14、40. 141. 插入排序直接插入排序一般直接插入排序的时间复杂度为O ( n2 ) ，但是当数列基本有序时，如果按照有数列顺序排时，时间复杂度将改善到O( n ) ，另外，因直接插入排序算法简单，如果待排序列规模不很大时效率也较高。在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。将数组分成两部分， 初始化时， 前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ；后部分数组的元素为除第一个元素的所有元素，为待名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

15、 - - - - - - 第 5 页，共 22 页 - - - - - - - - - 排序或待插入元素，我们这里叫 arr2 。排序时使用二层循环： 第一层对 arr2 进行循环， 每次取后部分数组 （待排序数组）里的第一个元素 （我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组） 从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素 （如果是降序排列）e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。 这样反复地对 arr2 进行循环，直到 arr2

16、 中所有的待插入的元素都插入到 arr1 中。Java 代码1. package sort; 2.3. import java.util.Comparator; 4.5. /* 6. * 直接插入排序算法7. * author jzj 8. * date 2009-12-5 9. * 10. * param 11. */ 12.public class InsertSortE extends Comparable extends Sort 13. 14. /* 15. * 排序算法的实现，对数组中指定的元素进行排序16. * param array 待排序的数组17. * param from

17、 从哪里开始排序18. * param end 排到哪里19. * param c 比较器名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - 20. */ 21. public void sort(E array, int from, int end, Comparator c) 22. 23. /* 24. * 第一层循环：对待插入（排序）的元素进行循环25. * 从待排序数组断的第二个元素开始循环，到最后一个元素（包括）止26

18、. */ 27. for (int i = from + 1; i = end; i+) 28. /* 29. * 第二层循环：对有序数组进行循环，且从有序数组最第一个元素开始向后循环30. * 找到第一个大于待插入的元素31. * 有序数组初始元素只有一个， 且为源数组的第一个元素，一个元素数组总是有序的32. */ 33. for (int j = 0; j 0) 37. /找到插入点后，从插入点开始向后所有元素后移一位38. move(array, j, i - 1); 39. /将待排序元素插入到有序数组中40. arrayj = insertedElem; 41. break; 42

19、. 43. 44. 45. 46. /=以下是 java.util.Arrays的插入排序算法的实现47. /* 48. * 该算法看起来比较简洁一j 点，有点像冒泡算法。49. * 将数组逻辑上分成前后两个集合，前面的集合是已经排序好序的元素，而后面集合为待排序的50. * 集合，每次内层循从后面集合中拿出一个元素，通过冒泡的形式，从前面集合最后一个元素开51. * 始往前比较，如果发现前面元素大于后面元素，则交换，否则循环退出52. * 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

20、 第 7 页，共 22 页 - - - - - - - - - 53. * 总感觉这种算术有点怪怪，既然是插入排序，应该是先找到插入点，而后再将待排序的元素插54. * 入到的插入点上，那么其他元素就必然向后移，感觉算法与排序名称不匹，但返过来与上面实55. * 现比，其实是一样的，只是上面先找插入点，待找到后一次性将大的元素向后移，而该算法却56. * 是走一步看一步，一步一步将待排序元素往前移57. */ 58. /* 59. for (int i = from; i from & pare(arrayj - 1, arrayj) 0; j-) 61. swap(array, j, j -

21、 1); 62. 63. 64. */ 65. 66. 67. /* 68. * 测试69. * param args 70. */ 71. public static void main(String args) 72. Integer intgArr = 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 ; 73. InsertSort insertSort = new InsertSort(); 74. Sort.testSort(insertSort, intgArr); 75. Sort.testSort(insertSort, null); 76. 77. 插入排序算

22、法对于大数组， 这种算法非常慢。但是对于小数组，它比其他算法快。其他算法因为待的数组元素很少，反而使得效率降低。在Java 集合框架中，排序都是借助于 java.util.Arrays来完成的，其中排序算法用到了插入排序、快速排序、归并排序。 插入排序用于元素个数小于7 的子数组排序， 通常比插入排序快的其他排序方法， 由于它们强大的算法是针对大数量数组设计的，所以元素个数少时速度反而慢。希尔排序希尔思想介绍名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 22 页 - -

23、 - - - - - - - 希尔算法的本质是缩小增量排序，是对直接插入排序算法的改进。一般直接插入排序的时间复杂度为O ( n2 ) ，但是当数列基本有序时，如果按照有数列顺序排时，时间复杂度将改善到O( n ) ，另外 , 因直接插入排序算法简单, 如果待排序列规模不很大时效率也较高，Shell 根据这两点分析结果进行了改进，将待排记录序列以一定的增量间隔h 分割成多个子序列，对每个子序列分别进行一趟直接插入排序 , 然后逐步减小分组的步长h ，对于每一个步长h 下的各个子序列进行同样方法的排序, 直到步长为 1 时再进行一次整体排序。因为不管记录序列多么庞大, 关键字多么混乱 , 在先前

24、较大的分组步长h 下每个子序列的规模都不大，用直接插入排序效率都较高。尽管在随后的步长h 递减分组中子序列越来越大， 但由于整个序列的有序性也越来越明显，则排序效率依然较高。这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。希尔增量研究综上所述：(1) 希尔排序的核心是以某个增量h 为步长跳跃分组进行插入排序，由于分组的步长 h 逐步缩小，所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列 ht ,. . . , hk ,. . . , h1 , h0 才能使得希尔方法的时间效率最高；(2) 待排序列记录的个数n 、跳跃分组步长逐步减小直到为1 时所进行的扫描次数 T

25、、增量的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔算法的时间复杂度：其中记录关键字比较的次数是重要因素，它主要取决于分组步长序列的选择；(3) 希尔方法是一种不稳定排序算法，因为其排序过程中各趟的步长不同，在第k 遍用 hk 作为步长排序之后，第k +1 遍排序时可能会遇到多个逆序存在，影响排序的稳定性。试验结果表明 ,SHELL 算法的时间复杂度受增量序列的影响明显大于其他因素，选取恰当的增量序列能明显提高排序的时间效率，我们认为第k 趟排序扫描的增量步长为 2k - 1 ,即增量序列为 . . . 2k - 1 ,. . . ,15 ,7 ,3 ,1时较

26、为理想，但它并不是唯一的最佳增量序列，这与其关联函数目前尚无确定解的理论结果是一致的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 22 页 - - - - - - - - - Java 代码1. package sort; 2.3. import java.util.Comparator; 4.5. /* 6. * 希尔排序算法7. * author jzj 8. * date 2009-12-5 9. * 10. * param 11. */ 12.public c

27、lass ShelltSortE extends Comparable extends Sort 13. 14. /* 15. * 排序算法的实现，对数组中指定的元素进行排序16. * param array 待排序的数组17. * param from 从哪里开始排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 22 页 - - - - - - - - - 18. * param end 排到哪里19. * param c 比较器20. */ 21. public

28、void sort(E array, int from, int end, Comparator c) 22. /初始步长，实质为每轮的分组数23. int step = initialStep(end - from + 1); 24. 25. /第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值26. for (; step = 1; step = (step + 1) / 2 - 1) 27. /对每轮里的每个分组进行循环28. for (int groupIndex = 0; groupIndex step; groupIndex+) 29. 30. /

29、对每组进行直接插入排序31. insertSort(array, groupIndex, step, end, c); 32. 33. 34. 35. 36. /* 37. * 直接插入排序实现38. * param array 待排序数组39. * param groupIndex 对每轮的哪一组进行排序40. * param step 步长41. * param end 整个数组要排哪个元素止42. * param c 比较器43. */ 44. private void insertSort(E array, int groupIndex, int step, int end, Comp

30、arator c) 45. int startIndex = groupIndex;/从哪里开始排序46. int endIndex = startIndex;/排到哪里47. /* 48. * 排到哪里需要计算得到， 从开始排序元素开始， 以 step 步长，可求得下元素是否在数组范围内，49. * 如果在数组范围内，则继续循环，直到索引超现数组范围50. */ 51. while (endIndex + step) = end) 52. endIndex += step; 53. 54. 55. / i为每小组里的第二个元素开始名师资料总结 - - -精品资料欢迎下载 - - - - -

31、- - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - 56. for (int i = groupIndex + step; i = end; i += step) 57. for (int j = groupIndex; j = 0) 61. /找到插入点后，从插入点开始向后所有元素后移一位62. move(array, j, i - step, step); 63. arrayj = insertedElem; 64. break; 65. 66. 67. 68. 69. 70. /*

32、71. * 根据数组长度求初始步长72. * 73. * 我们选择步长的公式为： 2k-1,2(k-1)-1,.,15,7,3,1 ，其中2k 减一即为该步长序列， k 74. * 为排序轮次75. * 76. * 初始步长： step = 2k-1 77. * 初始步长约束条件： step len - 1 初始步长的值要小于数组长度还要减一的值（因78. * 为第一轮分组时尽量不要分为一组，除非数组本身的长度就小于等于 4）79. * 80. * 由上面两个关系试可以得知：2k - 1 len - 1 关系式，其中k 为轮次，如果把 2k 表 达式81. * 转换成 step 表达式，则 2

33、k-1 可使用 (step + 1)*2-1 替换（因为 step+1 相当于第 k-1 82. * 轮的步长，所以在 step+1 基础上乘以 2 就相当于 2k 了），即步长与数组长度的关系不等式为83. * (step + 1)*2 - 1 len -1 84. * 85. * param len 数组长度86. * return 87. */ 88. private static int initialStep(int len) 89. /* 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

34、- - - 第 12 页，共 22 页 - - - - - - - - - 90. * 初始值设置为步长公式中的最小步长，从最小步长推导出最长初始步长值，即按照以下公式来推: 91. * 1,3,7,15,.,2(k-1)-1,2k-1 92. * 如果数组长度小于等于4 时，步长为 1，即长度小于等于4的数组不且分组，此时直接退化为直接插93. * 入排序94. */ 95. int step = 1; 96. 97. /试探下一个步长是否满足条件，如果满足条件， 则步长置为下一步长98. while (step + 1) * 2 - 1 len - 1) 99. step = (step

35、+ 1) * 2 - 1; 100. 101.102. System.out.println(初始步长 - + step); 103. return step; 104. 105.106. /* 107. * 测试108. * param args 109. */ 110. public static void main(String args) 111. Integer intgArr = 5, 9, 1, 4, 8, 2, 6, 3, 7, 10 ; 112. ShelltSort shellSort = new ShelltSort(); 113. Sort.testSort(shell

36、Sort, intgArr); 114. Sort.testSort(shellSort, null); 115. 116. 选择排序简单选择排序每一趟从待排序的数据元素中选出最小（或最大） 的一个元素， 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从arrayk开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比arrayk-1更小的元素，则把arrayminlIndex和 ak-1 对调， 这时 arrayk到最后一个元素中最小的元素就换到了arrayk-1名师资料

37、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 22 页 - - - - - - - - - 的位置。如此反复进行第二轮、第三轮, 直到循环至最后一元素Java 代码1. package sort; 2.3. import java.util.Comparator; 4.5. /* 6. * 简单选择排序算法7. * author jzj 8. * date 2009-12-5 9. * 10. * param 11. */ 12.public class SelectSort

38、E extends Comparable extends Sort 13. 14. /* 15. * 排序算法的实现，对数组中指定的元素进行排序16. * param array 待排序的数组17. * param from 从哪里开始排序18. * param end 排到哪里19. * param c 比较器20. */ 21. public void sort(E array, int from, int end, Comparator c) 22. int minlIndex;/最小索引23. /* 24. * 循环整个数组（其实这里的上界为 array.length - 1 即可，因

39、为当 i= array.length-1 25. * 时，最后一个元素就已是最大的了，如果为array.length时，内层循环将不再循环），每轮假设26. * 第一个元素为最小元素，如果从第一元素后能选出比第一个元素更小元素，则让让最小元素与第一名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 22 页 - - - - - - - - - 27. * 个元素交换28. */ 29. for (int i = from; i = end; i+) 30. minlInde

40、x = i;/假设每轮第一个元素为最小元素31. /从假设的最小元素的下一元素开始循环32. for (int j = i + 1; j = end; j+) 33. /如果发现有比当前arraysmallIndex更小元素， 则记下该元素的索引于smallIndex中34. if (pare(arrayj, arrayminlIndex) 0) 35. minlIndex = j; 36. 37. 38. 39. /先前只是记录最小元素索引， 当最小元素索引确定后， 再与每轮的第一个元素交换40. swap(array, i, minlIndex); 41. 42. 43. 44. /* 4

41、5. * 测试46. * param args 47. */ 48. public static void main(String args) 49. Integer intgArr = 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 ; 50. SelectSort insertSort = new SelectSort(); 51. Sort.testSort(insertSort, intgArr); 52. Sort.testSort(insertSort, null); 53. 54. 堆排序堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于( 或不

42、小于 ) 其左右孩子 ( 若存在 ) 结点的关键字。【例】关键字序列 (10，15，56，25，30，70)和(70，56，30，25，15，10) 分别满足堆性质 (1) 和(2) ，故它们均是堆， 其对应的完全二叉树分别如小根堆示例和名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 22 页 - - - - - - - - - 大根堆示例所示：根结点 ( 亦称为堆顶 ) 的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。根结点 ( 亦称为堆顶 ) 的关键字是堆里所有

43、结点关键字中最大者，称为大顶堆。堆是一种完全二叉树， 一般使用数组来实现。 堆排序也是一种选择性的排序，每次选择第 i 大的元素。另外排序过程中借助了堆结构，堆就是一种完全二叉树， 所以这里先要熟悉要用的二叉树几个性质：N （N1 ）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点 （非叶子节点）的编号为 N/2 取整。且对于编号 i （1=iN，则节点 i 没有左孩子，否则其左孩子为 2i ； 若 2i+1N， 则没有右孩子，否则其右孩子为 2i+1。注，这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构， 真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以

44、使用数组来存储。算法描述：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 22 页 - - - - - - - - - 堆排序其实最主要的两个过程：第一步，创建初始堆； 第二步， 交换根节点与最后一个非叶子节第一步实现：从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉， 直到没有子节点或比左右子节点都大为

45、止，调用过程可通过递归完成。 当某个非叶子节点调整完毕后，再处理下一个非叶子节点， 直到根节点也调整完成， 这里初始堆就创建好了， 这里我们创建的是大顶堆， 即大的元素向树的根浮， 这样排序最后得到的结果为升序，因为最大的从树中去掉， 并从数组最后往前存放。第二步实现：将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 22 页 - - - - -

46、- - - - 个节点为止。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 22 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 22 页 - - - - - - - - - Java 代码1. package sort; 2.3. import java.util.Comparator; 4.5. pub

47、lic class HeapSortE extends Comparable extends Sort 6.7. /* 8. * 排序算法的实现，对数组中指定的元素进行排序9. * param array 待排序的数组10. * param from 从哪里开始排序11. * param end 排到哪里12. * param c 比较器13. */ 14. public void sort(E array, int from, int end, Comparator c) 15. /创建初始堆16. initialHeap(array, from, end, c); 17. 18. /* 1

48、9. * 对初始堆进行循环，且从最后一个节点开始，直接树只有两个节点止20. * 每轮循环后丢弃最后一个叶子节点，再看作一个新的树21. */ 22. for (int i = end - from + 1; i = 2; i-) 23. /根节点与最后一个叶子节点交换位置，即数组中的第一个元素与最后一个元素互换24. swap(array, from, i - 1); 25. /交换后需要重新调整堆26. adjustNote(array, 1, i - 1, c); 27. 28. 29. 30. 31. /* 32. * 初始化堆33. * 比如原序列为： 7,2,4,3,12,1,9,

49、6,8,5,10,11 34. * 则初始堆为： 1,2,4,3,5,7,9,6,8,12,10,11 35. * param arr 排序数组36. * param from 从哪名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 22 页 - - - - - - - - - 37. * param end 到哪38. * param c 比较器39. */ 40. private void initialHeap(E arr, int from, int end, Co

50、mparator c) 41. int lastBranchIndex = (end - from + 1) / 2;/ 最后一个非叶子节点42. /对所有的非叶子节点进行循环，且从最一个非叶子节点开始43. for (int i = lastBranchIndex; i = 1; i-) 44. adjustNote(arr, i, end - from + 1, c); 45. 46. 47. 48. /* 49. * 调整节点顺序，从父、左右子节点三个节点中选择一个最大节点与父节点转换50. * param arr 待排序数组51. * param parentNodeIndex 要调整