Fork me on GitHub

排序算法-插入排序

插入排序算法定义(Insertion Sort)

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,
这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序
数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。
是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,
但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。
在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,
直到全部插入完为止。

插入排序的分类

包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。
属于稳定排序的一种(通俗地讲,就是两个相等的数不会交换位置) 。

直接插入排序

实现思路

直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个
已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。
例如,已知待排序的一组记录是:60,71,49,11,24,3,66
假设在排序过程中,前3个记录已按关键码值递增的次序重新排列,构成一个有序序列:49,60,71
将待排序记录中的第4个记录(即11)插入上述有序序列,以得到一个新的含4个记录的有序序列。
首先,应找到11的插入位置,再进行插入。可以讲11放入数组的第一个单元r[0]中,这个单元称为监视哨,
然后从71起从右到左查找,11小于71,将71右移一个位置,11小于60,又将60右移一个位置,11小于49,
又再将49右移一个位置,这时再将11与r[0]的值比较,11≥r[0],它的插入位置就是r[1]。
假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间,由于60已经右移了,留出来的位置正好留给11.
后面的记录依照同样的方法逐个插入到该有序序列中。若记录数n,续进行n-1趟排序,才能完成。
直接插入排序的算法思路:
(1) 设置监视哨r[0],将待插入记录的值赋值给r[0];
(2) 设置开始查找的位置j;
(3) 在数组中进行搜索,搜索中将第j个记录后移,直至r[0].key≥r[j].key为止;
(4) 将r[0]插入r[j+1]的位置上。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function insertSort(array){  
let i,
j,
temp,
arr = array.slice(), // 这里对原数组拷贝
n = arr.length;

for(i = 1;i < n;i++){
j = i-1;
temp = arr[i]; // 第i项为待插入的项

while(j < i && arr[j] > temp){
arr[j+1] = arr[j];
j--;
}

arr[j+1] = temp;
}

return arr;
}
var arrayA = [1 , 3, 2, 6, 4, 5];
let demo = insertSort(arrayA);
console.log(arrayA); // [1, 3, 2, 6, 4, 5]
console.log(demo); // [1, 2, 3, 4, 5, 6]

直接插入排序
最佳情况:输入数组按升序排列。T(n) = O(n)
最坏情况:输入数组按降序排列。T(n) = O(n2)
平均情况:T(n) = O(n2)

折半插入排序(二分插入排序)

定义

将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法。
在处理A[i]时,A[0]……A[i-1]已经按关键码值排好序。所谓折半比较,就是在插入A[i]时,
取A[i-1/2]的关键码值与A[i]的关键码值进行比较,如果A[i]的关键码值小于A[i-1/2]的关键码值,
则说明A[i]只能插入A[0]到A[i-1/2]之间,故可以在A[0]到A[i-1/2-1]之间继续使用折半比较;
否则只能插入A[i-1/2]到A[i-1]之间,故可以在A[i-1/2+1]到A[i-1]之间继续使用折半比较。
如此担负,直到最后能够确定插入的位置为止。一般在A[k]和A[r]之间采用折半,其中间结点为A[k+r/2],
经过一次比较即可排除一半记录,把可能插入的区间减小了一半,故称为折半。
执行折半插入排序的前提是文件记录必须按顺序存储。

实现思路

(1)计算 0 ~ i-1 的中间点,用 i 索引处的元素与中间值进行比较,如果 i 索引处的元素大,
说明要插入的这个元素应该在中间值和刚加入i索引之间,反之,就是在刚开始的位置 到中间值的位置,这样很简单的完成了折半;
(2)在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,
范围依次缩小为 1/2 1/4 1/8 …….快速的确定出第 i 个元素要插在什么地方;
(3)确定位置之后,将整个序列后移,并将元素插入到相应位置。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function binaryInsertSort(array){
let arr = array.slice();
for (let i = 1; i < arr.length; i++) {
let key = arr[i],
left = 0,
right = i - 1;

while (left <= right) {
let middle = parseInt((left + right) / 2);

if (key < arr[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}

}

for (var j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}

arr[left] = key;
}

return arr;
}

var arrayA = [1 , 3, 2, 6, 4, 5];
let demo = binaryInsertSort(arrayA);
console.log(arrayA); // [1, 3, 2, 6, 4, 5]
console.log(demo); // [1, 2, 3, 4, 5, 6]

二分插入排序
最佳情况:T(n) = O(nlogn)
最差情况:T(n) = O(n2)
平均情况:T(n) = O(n2)

参考文档:
数据结构复习:直接插入排序与二分插入排序的C++实现
插入排序
十大经典排序算法

-------------本文结束感谢您的阅读,如果本文对你有帮助就记得给个star-------------
Donate comment here