? ? ? ?
常用排序算法分析与实现（一）（Java版）
插入排序
直接插入排序、希尔排序
? ?
选择排序
简单选择排序、堆排序
? ?
交换排序
冒泡排序、快速排序
? ? ? ?
归并排序
基数排序
排序基类 Java代码
1. package sort; 2.
3. import java.util.Arrays; 4. import java.util.Comparator; 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 Sort> { 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[] array, 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. * 对整个数组进行排序，可以使用自己的排序比较器，也可使用该类
提供的两个比较器
43. * @param array 待排序数组
44. * @param c 比较器 45. */
46. public final void sort(E[] array, Comparator c) { 47. sort(0, array.length, array, c); 48. } 49. 50. /**
51. * 对整个数组进行排序，采用默认排序比较器 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 o1.compareTo(o2); 62. } 63. } 64.
65. //反序比较器，排序刚好与默认比较器相反
66. private class ReverseComparator implements Comparator { 67. public int compare(E o1, E o2) { 68. return o2.compareTo(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, int j) { 79. if (i != j) {//只有不是同一位置时才需交换 80. E tmp = array[i]; 81. array[i] = array[j]; 82. array[j] = tmp; 83. } 84. } 85. 86. /**
87. * 数组元素后移
88. * @param array 待移动的数组 89. * @param startIndex 从哪个开始移 90. * @param endIndex 到哪个元素止 91. */
92. protected final void move(E[] array, int startIndex, int endIndex) { 93. for (int i = endIndex; i >= startIndex; i--) { 94. array[i + 1] = array[i]; 95. } 96. } 97. 98. /**
99. * 以指定的步长将数组元素后移，步长指定每个元素间的间隔 100. * @param array 待排序数组 101. * @param startIndex 从哪里开始移 102. * @param endIndex 到哪个元素止 103. * @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. array[i + step] = array[i]; 108. } 109. } 110.
111. //测试方法
112. @SuppressWarnings(\
113. public static final > void testSort(Sort sorter, E[] array) { 114.
115. if (array == null) {
116. array = randomArray(); 117. }
118. //为了第二次排序，需拷贝一份
119. E[] tmpArr = (E[]) new Comparable[array.length]; 120. System.arraycopy(array, 0, tmpArr, 0, array.length); 121.
122. System.out.println(\源 - \ 123.
124. sorter.sort(array, sorter.REVERSE_ORDER); 125. System.out.println(\降 - \ 126.
127. sorter.sort(tmpArr, sorter.DEFAULT_ORDER); 128. System.out.println(\升 - \ 129. } 130.
131. //生成随机数组
132. @SuppressWarnings(\ 133. private static > E[] randomArray() {
134. Random r = new Random(System.currentTimeMillis()); 135. Integer[] a = new Integer[r.nextInt(30)]; 136. for (int i = 0; i < a.length; i++) {
137. a[i] = new Integer(r.nextInt(100)); 138. } 139. return (E[]) a; 140. } 141. }
插入排序
直接插入排序