插入排序
插入排序是一种简单的基于比较的排序算法。在这个算法中,我们维护两个子数组:一个已排序子数组和一个未排序子数组。未排序子数组中的一个元素在排序子数组中找到它的正确位置,并被插入其中。这类似于人们对手中的一副牌进行排序的方式。它被命名为插入排序,因为它的工作原理是在正确的位置插入一个元素。这种算法对小数据集很有效,但不适合大数据集。
插入排序算法
假设我们有一个包含 n 个元素的无排序数组 A[]
,第一个元素 A[0]
已经被排序并在排序后的子数组中。第一个元素 A[0]
已经被排序,并且在排序子数组中。
-
我们将未排序子数组
A[1]
中的第一个元素标记为键。 -
然后将键与排序子数组中的元素进行比较,这里我们只有一个元素,
A[0]
。 -
如果键大于
A[0]
,我们将其插入A[0]
之后。 -
否则,如果它小于
A[0]
,我们再比较一下,把它插入到A[0]
之前的正确位置。(在A[0]
的情况下,只有一个位置) -
将下一个元素
A[2]
作为键。将其与排序后的子数组元素进行比较,并在比A[2]
小的元素后插入。如果没有小元素,则将其插入到排序子数组的开头。 -
对未排序子数组中的所有元素重复上述步骤。
插入排序示例
假设我们有数组:(5,3,4,2,1)
. 我们将使用插入排序算法对其进行排序。
排序子数组 | 未排序子数组 | 数组 |
---|---|---|
( 5 ) | ( 3, 4, 2, 1) | (5, 3, 4, 2, 1) |
- 第一次迭代
键:A[1]
=3。
排序子数组 | 未排序子数组 | 数组 |
---|---|---|
( 3 , 5) | (4, 2, 1) | (3, 5, 4, 2, 1) |
- 第二次迭代
键:A[2]
=4。
排序子数组 | 未排序子数组 | 数组 |
---|---|---|
( 3, 4, 5) | (2, 1) | (3, 4, 5, 2, 1) |
- 第三次迭代
键:A[3]
=2。
排序子数组 | 未排序子数组 | 数组 |
---|---|---|
( 2, 3, 4, 5) | (1) | (2, 3, 4, 5, 1) |
- 第四次迭代
键:A[4]
=1。
排序子数组 | 未排序子数组 | 数组 |
---|---|---|
( 1, 2, 3, 4, 5) | () | (1, 2, 3, 4, 5) |
插入排序算法的实现
#include<iostream>
using namespace std;
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++)
{
int j = i;
while (j > 0 && arr[j - 1] > arr[j])
{
int key = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = key;
j--;
}
}
}
int main() {
int n = 5;
int arr[5] = {5, 3, 4, 2, 1};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
insertion_sort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
插入排序算法复杂度
时间复杂度
- 平均情况
平均来说,在插入排序的第 i 次传递中,会进行 i
次比较。所以,如果有 n 次迭代,那么平均时间复杂度可以在下面给出。
1 + 2 + 3 + ... + (n-1) = n*(n-1)/2
因此时间复杂度为 [Big Theta]:O(n2)。
- 最坏情况
最坏的情况发生在数组反向排序的时候,必须进行最大数量的比较和交换。
最坏情况下的时间复杂度为 [Big O]:O(n2)。
- 最佳情况
最好的情况发生在数组已经排序的情况下,然后只执行外循环 n 次。
最佳情况下的时间复杂度为 [Big Omega]:O(n)
。
空间复杂度
插入排序算法的空间复杂度为 O(n)
,因为除了一个临时变量外,不需要额外的内存。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn