92 lines
2.0 KiB
JavaScript
92 lines
2.0 KiB
JavaScript
/*
|
||
希尔排序的性能与所选的间隔序列（shell序列）有关。以下是几种常见的希尔排序序列：
|
||
Hibbard 序列:
|
||
H(k) = 2^k - 1
|
||
如：1, 3, 7, 15, 31, ...
|
||
|
||
Sedgewick 序列:
|
||
H(k) = 9 * 4^k - 9 * 2^k + 1 或 4^k - 3 * 2^k + 1
|
||
如：1, 5, 19, 41, 109, ...
|
||
|
||
Knuth 序列:
|
||
H(k) = 3^k + 1
|
||
如：1, 4, 13, 40, 121, ...
|
||
|
||
这些序列在实际应用中可能产生不同的性能效果，最佳序列可能取决于特定问题或数据集的性质。
|
||
|
||
*/
|
||
|
||
/**
|
||
*
|
||
* @param {number[]} arr
|
||
*/
|
||
export function shellSort(arr) {
|
||
const n = arr.length;
|
||
// 创建希尔序列,以克努特序列为例
|
||
let gap = 1;
|
||
while (gap < n / 3) {
|
||
gap = gap * 3 + 1;
|
||
}
|
||
|
||
while (gap >= 1) {
|
||
// 正常插入排序
|
||
for (let i = 0; i < gap; i++) {
|
||
for (let j = i + gap; j < n; j += gap) {
|
||
const temp = arr[j];
|
||
while (j > 0 && arr[j - gap] > temp) {
|
||
arr[j] = arr[j - gap];
|
||
j -= gap;
|
||
}
|
||
arr[j] = temp;
|
||
}
|
||
}
|
||
// 正常插入排序
|
||
|
||
gap = Math.floor(gap / 3);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* @description 使用希尔序列排序
|
||
* @param {number[]} arr
|
||
*/
|
||
export function shellSort2(arr) {
|
||
const n = arr.length;
|
||
let gap = Math.floor(n / 2);
|
||
while (gap > 0) {
|
||
for (let i = 0; i < gap; i++) {
|
||
for (let j = i + gap; j < n; j += gap) {
|
||
const temp = arr[j];
|
||
while (j > 0 && arr[j - gap] > temp) { // 插入过程s
|
||
arr[j] = arr[j - gap];
|
||
j -= gap;
|
||
}
|
||
arr[j] = temp;
|
||
}
|
||
}
|
||
gap = Math.floor(gap / 2);
|
||
}
|
||
}
|
||
|
||
/**
|
||
* 优化版本
|
||
* @param {number[]} arr
|
||
*/
|
||
export function shellSort3(arr) {
|
||
const n = arr.length;
|
||
let gap = Math.floor(n / 2);
|
||
while (gap > 0) { // 使用不同的gap对子数组排序
|
||
for (let i = gap; i < n; i++) {
|
||
// 插入过程
|
||
const temp = arr[i];
|
||
let j = i;
|
||
while (j > 0 && arr[j - gap] > temp) {
|
||
arr[j] = arr[j - gap];
|
||
j -= gap;
|
||
}
|
||
arr[j] = temp;
|
||
}
|
||
gap = Math.floor(gap / 2);
|
||
}
|
||
}
|