高级排序---希尔排序

2019-02-17 01:50:51来源：博客园阅读 ()

希尔排序对于多达几千个数据的中大小规模的数组排序表现良好。希尔排序不像快速排序和其他时间复杂度为O(N*logN)的排序那么快，因此对非常大的文件排序，它不是最优选择。但是希尔排序比选择排序和插入排序这种时间复杂度为O(N*N)排序算法快的多，并且它非常容易实现：希尔排序算法代码ji即短又简单。

希尔排序是基于插入排序的，但是插入排序的缺点是复制次数太多，当一个很小的数在数组最右边时，效率低

n-增量排序

　　希尔排序通过加大插入排序元素中的间隔，并在这些有间隔的元素中进行插入排序，从而是数据项能大跨度的移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去。进行这些排序的数据间隔被称为增量。当数组全部增量排序完后再减小间隔继续排序

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class ArraySh {

    @Test
    public void shTest(){
        int[] arr = new int[30];
        Random random = new Random();
        for(int i = 0;i < arr.length;i++){
            arr[i] = random.nextInt(1000);
        }
        System.out.println("未排序前数组：" + Arrays.toString(arr));

        arr = shellSort(arr);

        System.out.println("排序后数组：" + Arrays.toString(arr));
    }

    public int[] shellSort(int[] arr){
        int inner,outer,temp;
        int h = 1;
        while (h <= arr.length/3){
            h = h*3 +1;
        }
        while (h > 0){
            for(outer = h;outer < arr.length; outer++){
                temp = arr[outer];
                inner = outer;
                while (inner > h -1 && arr[inner - h] >= temp){
                    arr[inner] = arr[inner - h];
                    inner -= h;
                }
                arr[inner] = temp;
            }
            h = (h-1) /3;
        }
        return arr;

    }
}