Java排序算法(四)希尔排序2

希尔排序移步法:分组+直接插入排序组合

一、测试类SortTest

import java.util.Arrays;

public class SortTest {

  private static final int L = 20;
  public static void main(String[] args) {

  int [] arr = new int[6];
  for (int i = 0; i < arr.length; i++) {
  arr[i] = (int)((Math.random()+1)*L);
  }
  System.out.println(Arrays.toString(arr));
  // new Sort().BubbleSort(arr);
  // new Sort().SelectionSort(arr);
  // new Sort().InsertSort(arr);

  // new Sort().ShellSort1(arr);
  new Sort().ShellSort2(arr);

  System.out.println(Arrays.toString(arr));
  }  
}

二、排序类Sort

  /**
  *
  * <h1>希尔排序-移步法</h1>
  * <ul>
  * <li> 希尔排序移步法,先分组,然后进行插入排序
  * </ul>
  * @param arr the array
  * @author linzm
  * @since 1.8
  *
  */
public void ShellSort2(int[] arr) {
  int sep = arr.length/2;
  while(sep >= 1) {
  /*
  *假设length=8,第一次分组8/2 = 4 组
  *第二次分组,4/2 = 2组 假设第一组为 3 8 0 -1 2
  *第二次分组的第一组{3, 8, 0, -1, 2}下标分别为0, 2, 4, 6
  *first:3 8 0 -1 2
  * second:0 3 8 -1 2(直接插入)3 8 8 -1 2
  * 3 3 8 -1 2
  * 0 2 8 -1 2
  *third:-1 0 3 8 2(直接插入)
  * fourth:-1 0 2 3 8
  *
  */
    for (int i = sep; i < arr.length; i++) {
    // 标记待插入变量,右边往左边插入
    // 移位法
    // 假设i=2,j=2
      int j = i - sep;// 被插入位置
      int insertVal = arr[i]; // 待插入数
      if(arr[j] > arr[j+sep]) {
        while(j >= 0 && insertVal < arr[j]) {
          arr[j+sep] = arr[j];
          j -= sep;
          }
      }
    arr[j+sep] = insertVal;
    }
  sep /= 2;
  }
}

仅供参考,有错误还请指出!

2021-05-10 原文

Java排序算法(四)希尔排序2的相关文章

十种排序算法总结(冒泡、插入、选择、希尔、归并、堆、快速,计数,桶,基数)

#include<iostream> using  namespace std; void swap1( int *left,  int *right) {      int temp = ...

七大排序算法总结

以下所有动图均来源于一像素博客园 以下代码均使用C 编写 完整代码请到这里下载 稳定排序算法:冒泡排序.插入排序.归并排序 时间复杂度不受数据影响:选择排序.归并排序.堆排序 时间复杂度基本小于n2: ...

图解七大排序算法

"排序是计算机的核心内容.事实上,从很多方面看,如果没有排序,计算机就不会变成现实." <算法之美:指导工作与生活的算法> 排序算法,或许是我们日常最常见也是使用频率最 ...

冒泡排序、插入排序、选择排序、希尔排序

排序是一个非常经典的问题,它以一定的顺序对一个数组(或一个列表)中的项进行重新排序(可以进行比较,例如整数,浮点数,字符串等)(增加,非递减,递减, 增加,词典等). 有许多不同的排序算法,每个都有其 ...

十大经典排序算法(动图演示)

0.算法概述 0.1 算法分类 十种常见排序算法可以分为两大类: 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序. 非比较类排序: ...

关于排序算法,看这一篇就够了!这篇看不懂麻烦找我拿红包

排序算法是<数据结构与算法>中最基本的算法之一. 排序算法可以分为内部排序和外部排序. 内部排序是数据记录在内存中进行排序. 而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排 ...

浅析唐太宗凌烟阁二十四功臣排序规律

贞观十七年(643)二月戊申(二十八日),唐太宗李世民下令在凌烟阁给二十四名功臣画像,这就是著名的"凌烟阁二十四功臣". 关于凌烟阁二十四功臣的排序规律,一直存在争论,有说按照功绩 ...

十大排序算法详解,基本思想+动画演示+C语言实现,太肝了!

下面的99%的代码都是手动敲出来的,参考了诸多资料,已经经过测试,可以放心食用. 1.冒泡排序 基本思想 冒泡排序基本思想是依次比较两个相邻的元素,如果顺序(如从大到小.首字母从Z到A)错误就把他们交 ...

c语言必会排序算法集(含代码解析)

  一.冒泡排序 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法. 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小.首字母从A到Z)错误就 ...