希爾排序移步法：分組+直接插入排序組合

一、測(cè)試類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> 希爾排序移步法，先分組，然后進(jìn)行插入排序
　　* </ul>
　　* @param arr the array
　　* @author linzm
　　* @since 1.8
　　*
　　*/
public void ShellSort2(int[] arr) {
　　int sep = arr.length/2;
　　while(sep >= 1) {
　　/*
　　*假設(shè)length=8，第一次分組8/2 = 4 組
　　*第二次分組，4/2 = 2組 假設(shè)第一組為 3 8 0 -1 2
　　*第二次分組的第一組{3, 8, 0, -1, 2}下標(biāo)分別為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++) {
　　　　// 標(biāo)記待插入變量，右邊往左邊插入
　　　　// 移位法
　　　　// 假設(shè)i=2,j=2
　　　　　　int j = i - sep;// 被插入位置
　　　　　　int insertVal = arr[i]; // 待插入數(shù)
　　　　　　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;
　　}
}

僅供參考，有錯(cuò)誤還請(qǐng)指出！