정렬 된 힐 정렬 삽입 (3)

힐 정렬: 힐 정렬 (Shell 's Sort) 은 정렬 을 삽입 하 는 일종 의' 축소 증 량 정렬 '(Diminishing Increment Sort) 으로 정렬 알고리즘 을 직접 삽입 하 는 더욱 효율 적 인 개선 버 전 입 니 다.힐 정렬 은 불안정 정렬 알고리즘 입 니 다.보폭 설정 을 통 해 그룹 을 나 누고 각 그룹 은 각각 정렬 을 직접 삽입 합 니 다.

思路：
1.根据数组确定步长，并根据步长分组
2.对按步长分组的数据分别进行直接插入排序，排完序后，进行合并，并确定下一个步长
3.重复步骤2，直至步长为1

코드 구현 은 다음 과 같 습 니 다.

package com.test.sort;

public class ShellSort {

    /**
     * 希尔排序
     * @param args
     */
    public static void main(String[] args) {
        insertSort();//折半插入排序
    }
    
    /**
     * 希尔排序
     * 思路：
     * 1.根据数组确定步长，并根据步长分组
     * 2.对按步长分组的数据分别进行直接插入排序，排完序后，进行合并，并确定下一个步长
     * 3.重复步骤2，直至步长为1
     * 本例步长选择数组长度1/2;
     * {12,123,23,1,32,45,32,34,0,23,348,1,2,323}
     * 第一次分组步长7：
     * 
     *  12                     34
     *     123                  0
     *            23                 23
     *            1                  348
     *              32                    1 
     *                  45                 2
     *                    32                 323
     * 第二次分组步长3：
     * (12,1,32,23,2),(123,32,34,348,323),(23,45,0,1)
     *  12        1       32      23       2
     *     123      32       34      348     323
     *         23       45      0         1                 
     * 第三次。。。。。                       
     */
    public static void insertSort(){
        int [] a = new int[]{12,123,23,1,32,45,32,34,0,23,348,1,2,323};
        int d = a.length/2;
        while(true){
            for (int i = 0; i < a.length/d; i++) {//按步长分若干组
                for (int j = i; j < a.length/d; j=j+d) {//每一个步长分若干组
                    int temp=a[j];
                    int m=j;
                    for (m = j; m > i; m--) {//对单个步长下的每组进行直接插入排序
                        if(temp]){
a[m] = a[m-1];
}else{
break;
}
}
a[m]=temp;
}
}
d = d/2;
if(d<1){
break;
}
}
for (int i = 0; i < a.length; i++) {
if(i==a.length-1){
System.out.print(a[i]);
}else{
System.out.print(a[i]+", ");
}
}
}
}

 
다음으로 전송:https://www.cnblogs.com/quyanhui/p/10256141.html