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 ShelltSort> 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. //初始步长，实质为每轮的分组数 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. //对每组进行直接插入排序
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,
Comparator 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为每小组里的第二个元素开始
56. for (int i = groupIndex + step; i <= end; i += step) { 57. for (int j = groupIndex; j < i; j += step) { 58. E insertedElem = array[i];
59. //从有序数组中最一个元素开始查找第一个大于待插入的元素 60. if (c.compare(array[j], insertedElem) >= 0) {
61. //找到插入点后，从插入点开始向后所有元素后移一位 62. move(array, j, i - step, step); 63. array[j] = insertedElem; 64. break; 65. } 66. } 67. } 68. } 69. 70. /**
71. * 根据数组长度求初始步长 72. *
73. * 我们选择步长的公式为：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 减
一即为该步长序列，k
74. * 为排序轮次 75. *
76. * 初始步长：step = 2^k-1
77. * 初始步长约束条件：step < len - 1 初始步长的值要小于数组长度还
要减一的值（因
78. * 为第一轮分组时尽量不要分为一组，除非数组本身的长度就小于等
于4）
79. *
80. * 由上面两个关系试可以得知：2^k - 1 < len - 1 关系式，其中k为轮
次，如果把 2^k 表 达式
81. * 转换成 step 表达式，则 2^k-1 可使用 (step + 1)*2-1 替换（因为
step+1 相当于第k-1
82. * 轮的步长，所以在 step+1 基础上乘以 2 就相当于 2^k 了），即
步长与数组长度的关系不等式为
83. * (step + 1)*2 - 1 < len -1 84. *
85. * @param len 数组长度 86. * @return 87. */
88. private static int initialStep(int len) { 89. /*
90. * 初始值设置为步长公式中的最小步长，从最小步长推导出最长初
始步长值，即按照以下公式来推:
91. * 1,3,7,15,...,2^(k-1)-1,2^k-1
92. * 如果数组长度小于等于4时，步长为1，即长度小于等于4的数
组不且分组，此时直接退化为直接插
93. * 入排序 94. */ 95. int step = 1; 96.
97. //试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长 98. while ((step + 1) * 2 - 1 < len - 1) { 99. step = (step + 1) * 2 - 1; 100. } 101.
102. System.out.println(\初始步长 - \ 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(shellSort, intgArr); 114. Sort.testSort(shellSort, null); 115. } 116. }
选择排序
简单选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从array[k]开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比array[k-1]更小的元素，则把array[minlIndex]和a[k-1]对调，这时array[k]到最后一个元素中最小的元素就换到了array[k-1]的位置。 如此反复进行第二轮、第三轮…直到循环至最后一元素
Java代码
1. package sort; 2.
3. import java.util.Comparator;