每趟排序,根据对应的增量 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; } } }