内排序4：谢尔排序

谢尔排序又称缩小增量排序，是对直接插入排序的一种改进。
核心思想：首先确定一个时间间隔数gap，然后将参加排序的序列按此间隔数从第1个元素开始依次分为若干个子序列，即分别将所有位置相隔为gap的元素视为一个子序列，在各个子序列中采用某种排序方法进行排序（这里不妨使用泡排序法）；然后缩小间隔数，并重新将整个序列按新的间隔数分成若干个子序列，再分别对各个子序列进行排序，如此下去，直到间隔数gap=1。
算法如下：

function shellSort(arr) {
    let n = arr.length
    let i, j, temp, flag, gap = n
    while ( gap>1 ) {
        gap = Math.floor(gap/2)
        do {
            flag = 0
            for( i=0; i<n-gap; i++) {
                j = i+gap
                if ( arr[i] > arr[j] ) {
                    temp = arr[j]
                    arr[j] = arr[i]
                    arr[i] = temp
                    flag = 1
                }
            }
        } while ( flag!=0 );
    }
    return arr
}

let arr = [5,3,8,1,9,2,7,4,6,10]
shellSort(arr)

性能：
谢尔排序的速度是一系列间隔数gapi的函数，因而对其进行算法分析不是一件容易的事情，尤其是如何选择最合适的间隔数序列才能产生最好的排序效果，至今也没有得到较好的解决。
时间复杂度：稍大于O(nlog2n)接近于O(n1.23)。是不稳定排序法。