1. Overview
1.概述
In this tutorial, we’re going to discuss the Insertion Sort algorithm and have a look at its Java implementation.
在本教程中，我们将讨论插入式排序算法，并看一下它的Java实现。
Insertion Sort is an efficient algorithm for ordering a small number of items. This method is based on the way card players sort a hand of playing cards.
插入式排序是一种对少量项目进行排序的有效算法。这种方法是基于玩牌者对一手扑克牌的排序方式。
We start with an empty left hand and the cards laid down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a new card, we compare it with the already sorted set of cards in the hand, from right to left.
我们开始时左手是空的，牌放在桌子上。然后我们每次从桌子上抽出一张牌，把它插入左手的正确位置。为了找到新牌的正确位置，我们将其与手中已经分类的牌组进行比较，从右到左。
Let’s start by understanding the algorithm steps in pseudocode form.
让我们先来了解一下伪代码形式的算法步骤。
2. Pseudocode
2.伪代码
We’re going to present our pseudocode for insertion sort as a procedure called INSERTION-SORT, taking as parameter an array A[1 .. n] of n items to be sorted. The algorithm sorts the input array in-place (by rearranging the items within the array A).
我们将以一个名为INSERTION-SORT的过程来展示我们的插入排序的伪码，将一个包含n个待排序项的数组A[1 … n]作为参数。该算法对输入数组进行就地排序（通过重新排列数组A中的项目）。
After the procedure has finished, the input array A contains a permutation of the input sequence but in sorted order:
程序结束后，输入数组A包含了输入序列的排列组合，但是是按排序的。
INSERTION-SORT(A)
for i=2 to A.length
key = A[i]
j = i - 1
while j > 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j + 1] = keyLet’s briefly go over the algorithm above.
让我们简单地回顾一下上面的算法。
The index i indicates the position of the current item in the array to process.
索引i表示要处理的数组中当前项的位置。
We begin from the second item as by definition an array with one item is considered to be sorted. The item at index i is called a key. Once having the key, the second part of the algorithm deals with finding its correct index. If the key is smaller than the value of the item at index j, then the key moves one position to the left. The process continues until the case when we reach an element being smaller than the key.
我们从第二个项目开始，因为根据定义，一个有一个项目的数组被认为是被排序的。索引i处的项被称为key。一旦有了key，算法的第二部分就涉及到寻找其正确的索引。如果key小于索引j处的项目的值，那么键就向左移动一个位置。这个过程一直持续到我们到达一个比键小的元素为止。
It’s important to note that before starting the iteration for finding the correct position of the key at index i, the array A[1 .. j – 1] is already sorted.
需要注意的是，在开始迭代寻找索引i处的键的正确位置之前，数组A[1 … j – 1]已经被排序。
3. Imperative Implementation
3.强制性执行
For the imperative case, we’re going to write a function called insertionSortImperative, taking as a parameter an array of integers. The function starts iterating over the array from the second item.
对于命令式的情况，我们要写一个名为insertionSortImperative的函数，把一个整数数组作为参数。该函数从第二项开始对数组进行迭代。
At any given time during the iteration, we could think of this array as being logically divided into two portions; the left side being the sorted one and right side containing the items not yet sorted.
在迭代过程中的任何时候，我们可以认为这个数组在逻辑上被分为两部分；左边是已排序的，右边包含尚未排序的项目。
An important note here is that after finding the correct position at which we’ll insert the new item, we shift (and not swap) the items to the right to free a space for it.
这里需要注意的是，在找到插入新项目的正确位置后，我们将项目向右移动（而不是交换），以便为其腾出空间。
public static void insertionSortImperative(int[] input) {
for (int i = 1; i < input.length; i++) {
int key = input[i];
int j = i - 1;
while (j >= 0 && input[j] > key) {
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = key;
}
}Next, let’s create a test for the method above:
接下来，让我们为上面的方法创建一个测试。
@Test
public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() {
int[] input = {6, 2, 3, 4, 5, 1};
InsertionSort.insertionSortImperative(input);
int[] expected = {1, 2, 3, 4, 5, 6};
assertArrayEquals("the two arrays are not equal", expected, input);
}The test above proves that the algorithm sorts correctly in ascending order the input array <6, 2, 3, 4, 5, 1>.
上面的测试证明，该算法对输入数组<6, 2, 3, 4, 5, 1>进行了正确的升序排序。
4. Recursive Implementation
4.递归实施
The function for the recursive case is called insertionSortRecursive and accepts as input an array of integers (same as for the imperative case).
递归情况下的函数被称为insertionSortRecursive，接受一个整数数组作为输入（与命令式情况相同）。
The difference here from the imperative case (despite the fact that it’s recursive) is that it calls an overloaded function with a second argument that equals the number of items to sort.
这里与命令式案例的区别（尽管它是递归的）是，它调用了一个重载函数，其第二个参数等于要排序的项目数。
As we want to sort the complete array, we’ll pass a number of items equal to its length:
由于我们想对整个数组进行排序，我们将传递一个与数组长度相等的项目数。
public static void insertionSortRecursive(int[] input) {
insertionSortRecursive(input, input.length);
}The recursive case is a little bit more challenging. The base case occurs when we attempt to sort an array with one item. In this case, we do nothing.
递归的情况就有点挑战性了。当我们试图对一个数组中的一个项目进行排序时，基本情况会发生。
All the subsequent recursive calls sort a predefined portion of the input array – starting from the second item till we reach the end of the array:
所有后续的递归调用都是对输入数组的预定义部分进行排序–从第二项开始，直到到达数组的末端。
private static void insertionSortRecursive(int[] input, int i) {
if (i <= 1) {
return;
}
insertionSortRecursive(input, i - 1);
int key = input[i - 1];
int j = i - 2;
while (j >= 0 && input[j] > key) {
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = key;
}And this is what the call stack looks like for an input array of 6 items:
这就是输入6个项目的数组的调用堆栈的样子。
insertionSortRecursive(input, 6)
insertionSortRecursive(input, 5) and insert the 6th item into the sorted array
insertionSortRecursive(input, 4) and insert the 5th item into the sorted array
insertionSortRecursive(input, 3) and insert the 4th item into the sorted array
insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array
insertionSortRecursive(input, 1) and insert the 2nd item into the sorted arrayLet’s also see the test for it:
让我们也来看看它的测试。
@Test
public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() {
int[] input = {6, 4, 5, 2, 3, 1};
InsertionSort.insertionSortRecursive(input);
int[] expected = {1, 2, 3, 4, 5, 6};
assertArrayEquals("the two arrays are not equal", expected, input);
}The test above proves that the algorithm sorts correctly in ascending order the input array <6, 2, 3, 4, 5, 1>.
上面的测试证明，该算法对输入数组<6, 2, 3, 4, 5, 1>进行了正确的升序排序。
5. Time and Space Complexity
5.时间和空间的复杂性
The time taken by the INSERTION-SORT procedure to run is O(n^2). For each new item, we iterate from right to left over the already sorted portion of the array to find its correct position. Then we insert it by shifting the items one position to the right.
INSERTION-SORT程序运行的时间为O(n^2)。对于每个新的项目，我们从右到左遍历数组中已经排序的部分，以找到它的正确位置。然后我们通过将项目向右移动一个位置来插入它。
The algorithm sorts in place so its space complexity is O(1) for the imperative implementation and O(n) for the recursive implementation.
该算法在原地排序，因此其空间复杂度对于命令式实现来说是O(1)，对于递归式实现来说是O(n)。
6. Conclusion
6.结语
In this tutorial, we saw how to implement insertion sort.
在本教程中，我们看到了如何实现插入式排序。
This algorithm is useful for sorting a small number of items. It becomes inefficient when sorting input sequences having more than 100 items.
这种算法对少量项目的排序很有用。当对超过100个项目的输入序列进行排序时，它的效率变得很低。
Keep in mind that despite its quadratic complexity it sorts in place without the need of auxiliary space as is the case for merge sort.
请记住，尽管它具有二次复杂性，但它是就地排序的，不需要像合并排序那样的辅助空间。
The entire code could be found over on GitHub.
整个代码可以在GitHub上找到over。