Code666 (代码贴、代码片段)

[Java] java希尔排序算法 →→→→→进入此内容的聊天室

来自 , 2020-08-12, 写在 Java, 查看 169 次.
URL http://www.code666.cn/view/8e6b42f1
  1. /**
  2.  * 希尔排序：我们选择步长为：15,7,3,1 我们选择步长公式为：2^k-1,2^(k-1)-1,……,15,7,3,1
  3.  * (2^4-1,2^3-1,2^2-1,2^1-1) 注意所有排序都是从小到大排。
  4.  */
  5. public class ShellSort {
  6.  
  7.         /**
  8.          * 排序算法的实现，对数组中指定的元素进行排序
  9.          *
  10.          * @param array
  11.          *            待排序的数组
  12.          * @param from
  13.          *            从哪里开始排序
  14.          * @param end
  15.          *            排到哪里
  16.          * @param c
  17.          *            比较器
  18.          */
  19.         public void sort(Integer[] array, int from, int end) {
  20.                 // 初始步长，实质为每轮的分组数
  21.                 int step = initialStep(end - from + 1);
  22.  
  23.                 // 第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值
  24.                 for (; step >= 1; step = (step + 1) / 2 - 1) {
  25.                         // 对每轮里的每个分组进行循环
  26.                         for (int groupIndex = 0; groupIndex < step; groupIndex++) {
  27.  
  28.                                 // 对每组进行直接插入排序
  29.                                 insertSort(array, groupIndex, step, end);
  30.                         }
  31.                 }
  32.         }
  33.  
  34.         /**
  35.          * 直接插入排序实现
  36.          *
  37.          * @param array
  38.          *            待排序数组
  39.          * @param groupIndex
  40.          *            对每轮的哪一组进行排序
  41.          * @param step
  42.          *            步长
  43.          * @param end
  44.          *            整个数组要排哪个元素止
  45.          * @param c
  46.          *            比较器
  47.          */
  48.         public void insertSort(Integer[] array, int groupIndex, int step, int end) {
  49.                 int startIndex = groupIndex;// 从哪里开始排序
  50.                 int endIndex = startIndex;// 排到哪里
  51.                 /*
  52.                  * 排到哪里需要计算得到，从开始排序元素开始，以step步长，可求得下元素是否在数组范围内，
  53.                  * 如果在数组范围内，则继续循环，直到索引超现数组范围
  54.                  */
  55.                 while ((endIndex + step) <= end) {
  56.                         endIndex += step;
  57.                 }
  58.  
  59.                 // i为每小组里的第二个元素开始
  60.                 for (int i = groupIndex + step; i <= end; i += step) {
  61.                         for (int j = groupIndex; j < i; j += step) {
  62.                                 Integer insertedElem = array[i];
  63.                                 // 从有序数组中最一个元素开始查找第一个大于待插入的元素
  64.                                 if ((array[j].compareTo(insertedElem)) >= 0) {
  65.                                         // 找到插入点后，从插入点开始向后所有元素后移一位
  66.                                         move(array, j, i - step, step);
  67.                                         array[j] = insertedElem;
  68.                                         break;
  69.                                 }
  70.                         }
  71.                 }
  72.         }
  73.  
  74.         /**
  75.          * 根据数组长度求初始步长
  76.          *
  77.          * 我们选择步长的公式为：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 减一即为该步长序列，k 为排序轮次
  78.          *
  79.          * 初始步长：step = 2^k-1 初始步长约束条件：step < len - 1 初始步长的值要小于数组长度还要减一的值（因
  80.          * 为第一轮分组时尽量不要分为一组，除非数组本身的长度就小于等于4）
  81.          *
  82.          * 由上面两个关系试可以得知：2^k - 1 < len - 1 关系式，其中k为轮次，如果把 2^k 表 达式 转换成 step 表达式，则
  83.          * 2^k-1 可使用 (step + 1)*2-1 替换（因为 step+1 相当于第k-1 轮的步长，所以在 step+1 基础上乘以 2
  84.          * 就相当于 2^k 了），即步长与数组长度的关系不等式为 (step + 1)*2 - 1 < len -1
  85.          *
  86.          * @param len
  87.          *            数组长度
  88.          * @return
  89.          */
  90.         public static int initialStep(int len) {
  91.                 /*
  92.                  * 初始值设置为步长公式中的最小步长，从最小步长推导出最长初始步长值，即按照以下公式来推:
  93.                  * 1,3,7,15,...,2^(k-1)-1,2^k-1
  94.                  * 如果数组长度小于等于4时，步长为1，即长度小于等于4的数组不用分组，此时直接退化为直接插入排序
  95.                  */
  96.                 int step = 1;
  97.  
  98.                 // 试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长
  99.                 while ((step + 1) * 2 - 1 < len - 1) {
  100.                         step = (step + 1) * 2 - 1;
  101.                 }
  102.  
  103.                 System.out.println("初始步长 : " + step);
  104.                 return step;
  105.         }
  106.  
  107.         /**
  108.          * 以指定的步长将数组元素后移，步长指定每个元素间的间隔
  109.          *
  110.          * @param array
  111.          *            待排序数组
  112.          * @param startIndex
  113.          *            从哪里开始移
  114.          * @param endIndex
  115.          *            到哪个元素止
  116.          * @param step
  117.          *            步长
  118.          */
  119.         protected final void move(Integer[] array, int startIndex, int endIndex,
  120.                         int step) {
  121.                 for (int i = endIndex; i >= startIndex; i -= step) {
  122.                         array[i + step] = array[i];
  123.                 }
  124.         }
  125.  
  126.         /**
  127.          * 测试
  128.          *
  129.          * @param args
  130.          */
  131.         public static void main(String[] args) {
  132.                 Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 0 };
  133.                 ShellSort shellSort = new ShellSort();
  134.                 shellSort.sort(intgArr, 0, intgArr.length - 1);
  135.                 for (Integer intObj : intgArr) {
  136.                         System.out.print(intObj + " ");
  137.                 }
  138.         }
  139. }
  140.  

回复 "java希尔排序算法"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666