希尔排序(shell sort)

10大排序算法.png

希尔排序在1959年由唐纳德-希尔提出
希尔排序把序列看作是一个矩阵，分成m列逐列进行排序

• m从某个整数逐渐减为1
• 当m为1时，整个序列将完全有序
  因此希尔排序也被称之为递减增量排序(Diminishing Increment Sort)
  矩阵的列数取决于步长序列
• 比如 步序列为{1,5,19,41,109...} 就代表依次分成109列、41列、19列、5列、1列
• 不同的步长序列，执行效率也不同

希尔排序也可看做是对快速排序的一种改进

//步长序列数组
List<Integer> stepSequence = shellStepSequence();
for(Integer step: stepSequence) {
 //取出步长序列进行排序
  sort(step);
}

//分成step列进行排序
private void sort(int step) {
     //col:第几列 column的简称
    for(int col = 0;col < step;col++) {//对第col列进行排序
        //col 、col+step、 col+2*step..
       for(int begin = col+step;begin < list.length;begin+=step) {//快排逻辑
              int cur = begin;
              while(cur > col && cmp(cur,cur-step) < 0) {//当前元素小于前一个，就交换
                  swap(cur,cur-step);
                  cur -= step;
              }
       }

    }

}

//计算步长  希尔给出的公式：n/2^k 
private List<Integer> shellStepSequence() {
     List<Integer> stepSequence = new ArrayList();
     int step = array.length;
     while((step>>=1) > 0) {
        stepSequence.add(step);
     }
     return stepSequence;
}

希尔本人会给出的步长序列，最坏情况时间复杂度是:O(n^2)

//计算步长  希尔给出的公式：n/2^k 
private List<Integer> shellStepSequence() {
     List<Integer> stepSequence = new ArrayList();
     int step = array.length;
     while((step>>=1) > 0) {
        stepSequence.add(step);
     }
     return stepSequence;
}

目前已知的最好步长序列，最坏情况时间复杂度是O(n^4/3),1986年由Robert Sedgewick提出

新的步长序列公式.png

• k even: 当k为偶数时
• k odd: 当k为奇数时

//计算步长序列 

private List<Integer> sedgewickStepSequence() {

       List<Integer> stepSequence = new LinkedList():
       int k = 0, step = 0;
       while(true) {
            if(k%2==0) { //偶数
                int pow = (int)Math.pow(2,k>>1);
                step = 1+9*(pow*pow-pow);
            }else {//奇数
                 int pow1 = (int)Math.pow(2,(k-1)>>1);
                 int pow2 = (int)Math.pow(2,(k+1)>>1);
                 step = 1 + 8*pow1*pow2 - 6*pow2;
             }
             //超出就结束循环
             if(step >= list.length) break;
             //由于要倒序存储，所以每次加到0的位置
             stepSequence.add(0,step;);
             k++;
      }
    return stepSequence;
}