希尔排序（插排改造优化）希尔排序（插排改造优化）

function insertionSort4Gap(arr, gap) { var len = arr.length; gap = typeof gap === 'number' && gap > 0 ? gap : 1; // for(let i = gap; i < len; i += gap) { for(let i = gap; i < len; i++) { var cur = arr[i]; var j = i - gap; while(j >= 0 && arr[j] > cur) {// 这一步，由于 gap 变大（再由大递减），节约时间 arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = cur; }return arr; } function shellSort(arr) { var len = arr.length; var gap = 1; while(gap < len / 3) { gap = gap * 3 + 1; } for(gap; gap > 0; gap = Math.floor(gap / 3)) { insertionSort4Gap(arr, gap); }return arr; }console.log(new Date().getTime()); shellSort(arr); console.log(new Date().getTime()); console.log(arr);

文章图片
Sorting_shellsort_anim.gif

var arr = [4321, 34, 5643, 4321, 654, 2, 4389, 34, 564, 389, 3, 10, 23, 34, 89, 10, 2, 543, 4813, 89324, 765, 3, 2, 2, 4321, 34, 5643, 4321, 654, 2, 4389, 34, 564, 389, 3, 10, 23, 34, 89, 10, 2, 543, 4813, 89324, 765, 3, 2, 2, 4321, 34, 5643, 4321, 654, 2, 4389, 34, 564, 389, 3, 10, 23, 34, 89, 10, 2, 543, 4813, 89324, 765, 3, 2, 2]; console.log(new Date().getTime()); insertionSort(arr); console.log(new Date().getTime());