2.7希尔排序

2.7希尔排序
时间复杂度o(n*logn)

希尔排序习题.png

思路：0~N-1 个数
1.当步长为3的时候，从第四位的数字开始，向前跳三位，和第一位的数字比较，如果比位置1的数小，就换到位置1跳向前3位进行比较，但已经越界了，交换过程停止
2.如果比向前跳3位的数值比较大，则 直接停止交换的过程，进行下一个数的调整
......
3.当步长为3的最后一个数调整后，可能进入步长为2的调整，但最后都以步长为1结束

希尔排序越劣的话，越 接近于o(n*2)

package chenzp;

//希尔排序
import java.util.*;

public class barrier2_8 {

public int[] barrier(int[] A, int n) {
    if(A==null||A.length<2) return A;
    
    int feet=A.length/2;
    int index=0;
    while(feet>0){
        for (int i = feet; i < A.length; i++) { 
            index=i;
            for (int j = i-feet; j>=0; j=j-feet) {
                if(A[j+feet]<A[j])swap(A,j+feet,j);
                else break;
            }           
        }   
        feet=feet/2;
    }   
    return A;
}

public static void swap(int[] arr,int index1,int index2){
    int temp=arr[index1];
    arr[index1]=arr[index2];
    arr[index2]=temp;
}


public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a[] = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = sc.nextInt();
    }

    barrier2_5.barrier(a, n);

    for (int i : a) {
        System.out.println(i);
    }
}

}}