基本算法(04)

希尔排序（Shell's Sort）

1959年Shell发明，第一个突破O($n^2$)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

Demo(Scala)

def shellSort(array: Array[Int]):Array[Int] = {
   // 如果长度不足，不需要排序
   if (array.length <= 1) {
     array
   } else {
     // 初始间隔为序列中所有数据的一半
     var gap = array.length / 2

     // 逐渐减少增量，每次钆喷值减半，向下取整
     while (gap > 0){
       // 依次获取增量序列
       for ( begin <- 0 until gap){
         var nextIndex = begin + gap
         // 获取所有分组序列的指
         while ( nextIndex < array.length){
           val nextValue = array(nextIndex) // 下一个值
           var k = nextIndex - gap // 上一个下标
           // 对分组序列进行插入排序
           while ( k >= 0 && array(k) >= nextValue){
             array(k+gap) = array(k) // 将小的数向前移动
             k -= gap // 向前移动间隔位数
           }
           array(k + gap) = nextValue
           nextIndex += gap
         }
       }
       gap = gap / 2
     }
   }
   array
 }