插入排序算法简介

插入排序是一种技术,它利用已排序的子列表并从未排序的列表中不断向其添加一个值,直到整个列表都已排序。

该算法从第一个列表项作为排序的子列表开始。然后它将下一个数字与第一个数字进行比较。如果它更大,那么它被插入到第一个索引中。否则,它会留在它的索引中。

然后将第三个值与其他两个值进行比较,然后插入到正确的索引中。这个过程一直持续到整个列表被排序。

深入了解插入排序

上面的描述对你来说可能没有意义。一个例子应该可以帮助你更好地理解。

假设您有一个列表:[39, 6, 2, 51, 30, 42, 7]。

该算法将 39 标识为已排序子列表的第一个值。评估然后移动到第二个位置。

相关:动态规划:示例、常见问题和解决方案

然后将 6 与 39 进行比较。由于 6 小于 39,因此将 6 插入到第一个位置,将 39 插入到第二个位置。新的列表顺序是在第一次通过之后:

[6, 39, 2, 51, 30, 42, 7]

评估现在转移到第三位。 2 与最后两个数字进行比较,然后插入到正确的位置。新的列表顺序是在第二遍之后:

[2, 6, 39, 51, 30, 42, 7]

对于第三遍,列表顺序是:

[2, 6, 39, 51, 30, 42, 7]

该过程重复进行,直到整个列表被排序。

请参阅下图总结了这些操作:

算法分析

插入排序的时间复杂度是 O(n 2 ),就像冒泡排序一样。最坏情况下的比较次数是从 1 到 (n-1) 的所有整数的总和,给出二次和。

代码实现

下面的 Python 和 Java 代码显示了如何实现插入排序方法。

Python:

 def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_element

爪哇:

 void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x < n; x++) {
int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
}

使用伪代码更好地编码

上面给出的代码示例没有任何伪代码,您可以参考这些伪代码用其他语言编写此算法。大多数程序员(包括作者)喜欢在被告知有关程序如何工作的“耳语”后跑到他们的键盘上。

不幸的是,随着程序逻辑变得更加复杂,这种方法很容易出错。您希望如何通过学习如何使用伪代码来提升您的编程水平?