排序算法系列文章

希尔排序（Shell Sort）

希尔序列步长序列待优化

基本思想

希尔排序是插入排序的一种改进，主要是为了解决当较小的数据大都出现在数组后面时导致的移动次数明显增多的问题，思想是使用一个不断缩小的增量gap将数组元素分组，在每个分组内部先进行插入排序，当gap减少到1时整个数组元素分在一组，最后进行一次插入排序，整个排序过程结束。

复杂度

最好情况：当数据已经排好序的情况下：O(n^1.3)； 最坏情况：O(n^2)； 平均情况：O(nlogn) 算法空间复杂度：O(1) 算法稳定性：不稳定

代码实现

下面代码没有步长序列优化

public class ShellSort {
          
   
    public static void main(String[] args) {
          
   
        int[] array = {
          
   5,3,2,0,6,9,1};
        sort(array);

        for (int i = 0; i < array.length; i++) {
          
   
            System.out.println(array[i] + "_");
        }
    }

    private static void sort(int[] arr){
          
   
        if (arr == null || arr.length < 2) {
          
   
            return;
        }
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
          
   
            for (int i = gap; i < arr.length; i++) {
          
   
                int j = i;
                int tmp = arr[j];
                if (arr[j] < arr[j - gap]) {
          
   
                    while (j - gap >= 0 && tmp < arr[j - gap]) {
          
   
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                }
                arr[j] = tmp;
            }
        }
    }
}