每趟排序,根據對應的增量 ti,將待排序列分割成若干長度爲 m 的子序列,分別對各子表進行直接插入排序。僅增量因子爲 1 時,整個序列作爲一個表來處理,表長度即爲整個序列的長度。
2. 動圖演示
代碼實現
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; }
Python
實例
def shellSort(arr): importmath gap=1 while(gap <len(arr)/3): gap = gap*3+1 while gap >0: for i inrange(gap,len(arr)): temp = arr[i] j = i-gap while j >=0and arr[j]> temp: arr[j+gap]=arr[j] j-=gap arr[j+gap]= temp gap =math.floor(gap/3) return arr
Go
實例
func shellSort(arr []int)[]int{ length :=len(arr) gap :=1 for gap < length/3{ gap = gap*3+1 } for gap > 0{ fori:= gap;i < length;i++{ temp := arr[i] j :=i- gap for j >=0 && arr[j] > temp { arr[j+gap]= arr[j] j -= gap } arr[j+gap]= temp } gap = gap /3 } return arr }
Java
實例
publicstaticvoid shellSort(int[] arr){ int length = arr.length; int temp; for(int step = length /2; step >=1; step /=2){ for(int i = step; i < length; i++){ temp = arr[i]; int j = i - step; while(j >=0&& arr[j]> temp){ arr[j + step]= arr[j]; j -= step; } arr[j + step]= temp; } } }