每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
2. JavaScript 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
functionshellSort(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; }
3. Python 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
defshellSort(arr): import math gap=1 while(gap < len(arr)/3): gap = gap*3+1 while gap > 0: for i in range(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 }
funcshellSort(arr []int) []int { length := len(arr) gap := 1 for gap < gap/3 { gap = gap*3 + 1 } for gap > 0 { for i := 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 }