JAVA,Python
安樂窩

算法-JAVA經典排序算法希爾排序(縮小增量排序)

算法-JAVA經典排序算法希爾排序(縮小增量排序)

1959年Shell發明,第一個突破O(n2)的排序算法,是簡單插入排序的改進版。它與插入排序的不同之處在于,它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序

1 算法步驟

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序,具體算法描述:

  • 選擇一個增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
  • 按增量序列個數 k,對序列進行 k 趟排序;
  • 每趟排序,根據對應的增量 ti,將待排序列分割成若干長度為 m 的子序列,分別對各子表進行直接插入排序。僅增量因子為 1 時,整個序列作為一個表來處理,表長度即為整個序列的長度。

2 動圖演示

2 JAVA代碼實現:

function shellSort(arr) {
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 注意:這里和動圖演示的不一樣,動圖是分組執行,實際操作是多個分組交替執行
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

 

贊(0) 打賞
未經允許不得轉載:藍騎兵JAVA,Python安樂窩 » 算法-JAVA經典排序算法希爾排序(縮小增量排序)
分享到: 更多 (0)

評論 搶沙發

  • 昵稱 (必填)
  • 郵箱 (必填)
  • 網址

藍騎兵 Java,Python的安樂窩

聯系我們聯系我們
福利彩票25选5走势图