代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
希尔排序,也被称为递减增量排序,是简单插入排序的一种改进版本。
[2, 3, 4, 5, 6, 7, 8, 1, ...]
,我们要插入 1,就必须将 1 和前面的 2-8 每个值都比较一下,就是因为 1 附近非常无序,想象一下,如果待插入元素附近比较有序,那么在进行插入排序的时候就只需要比较非常少的几次就可以插入到正确位置。import java.util.Arrays;
public class ShellSort {
private static int[] shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > key) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = key;
}
}
return arr;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(shellSort(new int[]{1, 2, 7, 9, 5, 8})));
}
}
function shellSort(arr) {
var len = arr.length;
var gapSize = Math.floor(len / 2);
while (gapSize > 0) {
for (var i = gapSize; i < len; i++) {
var temp = arr[i];
var j = i;
while (j >= gapSize && arr[j - gapSize] > temp) {
arr[j] = arr[j - gapSize];
j -= gapSize;
}
arr[j] = temp;
}
gapSize = Math.floor(gapSize / 2);
}
return arr;
}
let arr = [6, 3, 2, 1, 5];
console.log(shellSort(arr));
package main
import "fmt"
func shellSort(nums []int) {
n := len(nums)
for gap := n / 2; gap > 0; gap /= 2 {
for i := gap; i < n; i++ {
j, num := i-gap, nums[i]
for ; j >= 0 && nums[j] > num; j -= gap {
nums[j+gap] = nums[j]
}
nums[j+gap] = num
}
}
}
func main() {
nums := []int{1, 2, 7, 9, 5, 8}
shellSort(nums)
fmt.Println(nums)
}
时间复杂度:
希尔排序的时间性能取决于所取“增量”序列的函数,这涉及到一些数学上尚未解决的难题。但是有人通过大量的实验,给出了较好的结果:当 n 较大时,比较和移动的次数约在 n^1.25
到 (1.6n)^1.25
之间。所以可以这样简单记忆:
空间复杂度:O(1)。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。