logo

排序算法之直接插入排序,二分插入排序,希尔排序

直接插入排序(Insertion Sort)

直接插入排序

步骤(升序)

1.将以第一个元素看作已排序元素,剩下的看作未排序元素
2.选择第一个未排序元素作为当前排序元素与从最后一个已排序所有元素开始倒序比较大小
 2.1 当前排序元素相同或大于比较元素,或已排序全部比较完成,则停止遍历比较,执行步骤三
 2.2 小于则交换位置
3.重复步骤 2 直到所有元素都为已排序元素

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function insertionSort(arr) {
for (let i = 1, len = arr.length; i < len; i++) {
// for (let j = i; j > 0; j--) {
// if (arr[j] >= arr[j - 1]) {
// break;
// } else {
// let temp = arr[j]
// arr[j] = arr[j - 1];
// arr[j - 1] = temp
// }
// }
let j = i;
while (arr[j] < arr[j - 1] && j > 0) {
let temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
return arr;
}

分析

排序方式为 In-Place(原地)排序,因此空间复杂度为 $O(1)$

  • 最佳情况:序列升序,长度为 $n$ 的序列比较 $n-1$ 次,赋值 $0$ 次,时间复杂度为 $O(n)$
  • 最差情况:序列倒序,长度为 $n$ 的序列比较 $\sum_{i=1}^{n-1}{i}\Longrightarrow\frac{n(n-1)}{2}$ 次,赋值$\sum_{i=1}^{n-1}{i}-(n-1)\Longrightarrow\frac{(n-2)(n-1)}{2}$次,时间复杂度为$O(n^2)$

平均时间复杂度为$O(n^2)$,相等元素排序位置固定,稳定排序,用于少量元素排序或大量元素大致有序排序,不适合大量随机元素排序。

折半/二分插入排序(Binary Insertion Sort)

直接插入排序的优化版本,与直接插入排序算法不同点是,查找插入位置时使用二分查找,再统一移动位置,从而减少比较次数。

步骤(升序)

1.将以第一个元素看作已排序元素,剩下的看作未排序元素
2.选择第一个未排序元素作为当前排序元素与从最后一个已排序所有元素开始倒序比较大小
 2.1 使用二分查找找到插入位置
 2.2 插入位置之后的所有已排序元素向后移动一位
 2.3 将当前排序元素插入查找到的位置
3.重复步骤 2 直到所有元素都为已排序元素

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function binaryInsertionSort(arr) {
for (let i = 1, len = arr.length; i < len; i++) {
var current = arr[i];
var low = 0,
high = i - 1,
mid;
while (low <= high) {
/*等效 mid = (high + low) >> 1*/
mid = Math.floor((high + low) / 2;
if (current >= arr[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
for (let j = i; j > low; j--) {
arr[j] = arr[j - 1];
}
arr[low] = current;
}
return arr;
}

分析

与直接插入排序相同,排序方式为 In-Place(原地)排序,因此空间复杂度为 $O(1)$

  • 最佳情况:序列升序,长度为 $n$ 的序列比较 $\log_{2}{n}$ 次,赋值 0 次,时间复杂度为 $O(\log{n})$
  • 最差情况:序列倒序,长度为 n 的序列比较 $\log_{2}{n}$ 次,赋值赋值 $\sum_{i=1}^{n-1}{i}\Longrightarrow{n(n-1)/2}$ 次,时间复杂度为$O(n^2)$ 次,时间复杂度为 $O(n^2)$

平均时间复杂度为 $O(n^2)$ ,相等元素排序位置固定,稳定排序,少量元素略差于直接插入排序(比较次数固定),大量下优于直接插入排序排序。

希尔/递减增量排序(Shell Sort)

希尔排序是一种更高效的插入排序,根据步长将全部元素分组,并对每组列排序,逐步缩小步长直到 1,步长为 1 时视作直接插入排序,此时序列已经大致有序,元素能够一次向目标位置移动更多,能够减少比较赋值次数。

希尔排序

在不同的步长序列下最坏时间复杂度也随之不同。这里我们以 ${n/2^i}$ 取步长。
|步长序列 | 最坏复杂度 |
|:–:|:–:|
| $n/2^i$ |$O(n^2)$ |
|$2^i-1$|$O(n^{3/2})$|
|$2^i3^j$|$O(n\log^2{n})$|

步骤(升序)

  1. 取步长为 $n/2^i$ 向下取整,$i$ 取步长的次数
  2. 根据步长对元素分组并按列进行普通插入排序
  3. 重复步骤 1 直到步长为 0

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function shellSort(arr) {
let len = arr.length;
for (let gap = len >> 1; gap > 0; gap >>= 1) {
for (let i = gap; i < len; i++) {
let current = arr[i];
let j = i - gap;
while (j >= 0 && arr[j] > current) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = current;
}
}
return arr;
}

分析

与直接插入排序相同,排序方式为 In-Place(原地)排序,因此空间复杂度为 $O(1)$

  • 最佳情况:序列正序,比较$n-1$次,赋值 0 次,时间复杂度为$O(n)$
  • 最差情况:序列倒序,比较次数趋近于 n,时间复杂度为$O(n^2)$

平均时间复杂度为 $O(n\log^2{n})$ ,相等元素排序位置由于分组比较可能不固定,不稳定排序,大量随机元素排序优于插入排序,二分插入排序。

插入排序总结

Chorme72 性能测试

10000 个数测试代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function test(time) {
let tempTime = time;
let result = [];
while (time > 0) {
var n = 10000;
var arr = Array.from({
length: n
}).map(() => Math.round(Math.random() * n));

var start, end;
start = performance.now();

SortMethod(arr);

end = performance.now();
result.push(end - start);
time--;
}
return result.reduce((a, b) => a + b) / tempTime;
}
test(10);
排序方法10 次平均时间(ms)
插入排序284.133ms
二分插入排序23.980ms
希尔排序1.723ms

我们可以看出,再大量元素下出入排序性能提升明显。

综合比较

排序方法平均时间复杂度最佳时间复杂度最差时间复杂度空间复杂度稳定性排序方式
插入排序$O(n^2)$$O(n)$$O(n^2)$$O(1)$稳定In-Place
二分插入排序$O(n^2)$$O(\log{n})$$O(n^2)$$O(1)$稳定In-Place
希尔排序$O(n\log^2{n})$$O(n)$$O(n^2)$$O(1)$不稳定In-Place

参考链接