希尔排序

[Ir1d]

https://oi-wiki.org/basic/shell-sort/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[minghu6]

希尔排序明显是个原地算法呀，这个空间复杂度 O(n) 是疑似直接copy了中文维基中的错误。

包括内层的插入排序一般是用先右移，后插入的版本（稍微快一点）

看了这么多篇算法相关的中英维基比较，特别在算法基础部分（基本都是上世纪70、80年代流行的研究方向），中文短板还是很明显的。

[aizigao]

时间复杂度也不对，应该是中文维基的错误 英文版写的是 O(nlogn)

[dffxd-suntra]

希尔排序不稳定，间隙之类的不好算，复杂度又高，学明白搞搞初赛就行，复赛就算了

[by-legend]

1.稳定性几乎没用
2.复杂度高??你在搞笑,之前打过shell,统计了一下,速度跟系统不相上下,而且你看排序简介那一章,希尔几乎是最快的了
3复赛算了?这个很赞同,复赛谁不用标准库还去手写shell,quicksort啊?

[Cephascqs]

第九、十行是排序用的吗

[zhangjialin996]

复杂的公式就懒得看了，借用408王道的代码：

class Solution {
    public int[] sortArray(int[] nums){
    shellSort(nums);
    return nums;
  }

  public void shellSort(int[] nums){
        for(int step = nums.length >> 1; step >= 1; step = step >> 1){
            for(int start = step; start < nums.length; start++){
                for(int j = start - step; j >= 0 && nums[j + step] < nums[j]; j-=step){
                    swap(nums, j, j + step);
                }
            }
        }
    }

    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}