排序算法 希尔排序

插入排序的优解, 在数据量大时优势更为明显

算法步骤

隔段对比, 完成排序后, 缩小隔断间隔

可参考: 希尔排序

时间复杂度: O(n log n) ~ O(n log^2 n)

空间复杂度: O(1)

稳定性: 不稳定

• 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

代码

C++

 template<typename T>
 void shell_sort(T array[], int length) {
     for(int gap = length/2; gap > 0; gap = gap/2){
         //插入排序
         for(int i = gap; i < length; i++){
             int value = array[i];
             int p = i;
             while(p-gap > 0 && array[p-gap] > value) {
                 array[p] = array[p-gap];
                 p = p - gap;
             }
             array[p] = value;
         }
     }
 }

引自: 希尔排序代码

JavaScript

 function shellSort(arr) {
     var len = arr.length,
         temp,
         gap = 1;
     while(gap < len/3) {          //动态定义间隔序列
         gap =gap*3+1;
     }
     for (gap; gap > 0; gap = Math.floor(gap/3)) {
         for (var i = gap; i < len; i++) {
             temp = arr[i];
             for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                 arr[j+gap] = arr[j];
             }
             arr[j+gap] = temp;
         }
     }
     return arr;
 }

引自: 十大经典排序算法 | 菜鸟教程