Data Structures Algorithms 简明教程

Insertion Sort Algorithm

插入排序是一种非常简单的方法，按升序或降序对数字进行排序。此方法遵循增量方法。可以将它与在玩游戏时对卡片进行排序技术进行比较。

Insertion sort is a very simple method to sort numbers in an ascending or descending order. This method follows the incremental method. It can be compared with the technique how cards are sorted at the time of playing a game.

这是一个基于比较的就地排序算法。在这里，始终维护一个已排序的子列表。例如，数组的下半部分被维护为已排序。一个要“插入”到此已排序子列表中的元素，必须找到它合适的位置，然后必须在那里插入。因此得名， insertion sort 。

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'inserted' in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

对数组进行顺序搜索，将未排序的项目移动并插入到已排序的子列表中（在同一数组中）。此算法不适用于大数据集，因为它的平均和最坏情况复杂度为 Ο(n2)，其中 n 是项目数。

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2), where n is the number of items.

Insertion Sort Algorithm

现在，我们对这种排序技术如何工作有了更大的了解，因此我们可以得出可以实现插入排序的简单步骤。

Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by which we can achieve insertion sort.

*步骤 1 *− 如果它是第一个元素，则它已经排序。返回 1；

*Step 1 *− If it is the first element, it is already sorted. return 1;

*步骤 2 *− 挑选下一个元素

*Step 2 *− Pick next element

*步骤 3 *− 在已排序的子列表中与所有元素进行比较

*Step 3 *− Compare with all elements in the sorted sub-list

步骤 4 − 移动已排序子列表中大于待排序值的所有元素

*Step 4 *− Shift all the elements in the sorted sub-list that is greater than the value to be sorted

步骤 5 − 插入值

*Step 5 *− Insert the value

步骤 6 − 重复执行，直到列表排序完成

*Step 6 *− Repeat until list is sorted

Pseudocode

Algorithm: Insertion-Sort(A)
for j = 2 to A.length
   key = A[j]
   i = j – 1
   while i > 0 and A[i] > key
      A[i + 1] = A[i]
      i = i -1
   A[i + 1] = key

Analysis

此算法的运行时间极大地依赖于给定的输入。

Run time of this algorithm is very much dependent on the given input.

如果给定的数字已排序，此算法将在 O(n) 时间内运行。如果给定的数字相反顺序排列，此算法将在 O(n2) 时间内运行。

If the given numbers are sorted, this algorithm runs in O(n) time. If the given numbers are in reverse order, the algorithm runs in O(n2) time.

Example

我们对示例采用了未排序的数组。

We take an unsorted array for our example.

unsorted array example

插入排序将前两个元素进行比较。

Insertion sort compares the first two elements.

compares first two elements

它发现 14 和 33 已按升序排列。现在，14 在已排序子列表中。

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.

sorted sub list

插入排序继续并比较 33 和 27。

Insertion sort moves ahead and compares 33 with 27.

Insertion sort moves

并发现 33 未处于正确位置。它将 33 与 27 交换。它还将已排序子列表的所有元素进行检查。在此，我们看到已排序子列表仅包含一个元素 14，而 27 大于 14。因此，已排序子列表在交换后仍保持已排序状态。

And finds that 33 is not in the correct position. It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping.

swaps 33 with 27

现在已排序子列表中包含 14 和 27。接下来，它将 33 与 10 进行比较。这些值未按排序顺序排列。

By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10. These values are not in a sorted order.

compares 33 with 10

因此它们被交换。

So they are swapped.

swapped 33 with 10

但是，交换会使 27 和 10 无序。

However, swapping makes 27 and 10 unsorted.

swapping makes 27 10

因此，我们也对它们进行交换。

Hence, we swap them too.

swapped 27 and 10

我们再次发现 14 和 10 未按排序顺序排列。

Again we find 14 and 10 in an unsorted order.

14 and 10 unsorted order

我们再次对它们进行交换。

We swap them again.

swap 14 and 10

在第三次迭代结束时，我们得到了包含 4 个条目的已排序子列表。

By the end of third iteration, we have a sorted sub-list of 4 items.

sub list of 4 items

此过程将一直持续到已排序子列表中包含所有未排序值为止。现在，我们将看到插入排序的一些编程方面的知识。

This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall see some programming aspects of insertion sort.

Implementation

由于插入排序是一种就地排序算法，因此此算法是以一种方式实现的，其中关键元素（迭代地作为数组中的每个元素选择）与连续元素进行比较以检查其位置。如果关键元素小于连续元素，则不进行交换。否则，将交换比较的两个元素，并选择下一个元素作为关键元素。

Since insertion sort is an in-place sorting algorithm, the algorithm is implemented in a way where the key element – which is iteratively chosen as every element in the array – is compared with it consequent elements to check its position. If the key element is less than its successive element, the swapping is not done. Otherwise, the two elements compared will be swapped and the next element is chosen as the key element.

插入排序在四种编程语言中实现，分别是 C、C++、Java 和 Python -

Insertion sort is implemented in four programming languages, C, C++, Java, and Python −