AP计算机教程11-5：插入排序

插入排序从索引1开始，试图将之后的每一个元素都插入到已排好序部分（即外层循环当前位置的左侧部分）的正确位置。算法会通过将之后元素右移一位的办法把待插入值的位置空出来。右移的操作会一直进行，直到找到了正确位置或已经到了数组开头（证明待插入值其实是已排序部分的最小值）。

插入排序的算法有如下特征：

• 外层循环从索引1开始，遍历整个数组（第7行）
• 将外层循环当前元素储存在临时变量里（第9行）
• 设置目标位置索引为外层循环的当前索引（第10行）
• 内层循环从外层循环的当前位置往数组开头进行，将元素右移直到待移动元素比临时变量小为止（第11-15行）
• 内层循环结束后，将临时变量的内容替换到空出的正确位置（第16行）

以下是一个AP计算机插入排序的示例代码。

import java.util.Arrays;

public class SortTest
{
   public static void insertionSort(int[] elements)
   {
      for (int j = 1; j < elements.length; j++)
      {
         int temp = elements[j];
         int possibleIndex = j;
         while (possibleIndex > 0 && temp < elements[possibleIndex - 1])
         {
            elements[possibleIndex] = elements[possibleIndex - 1];
            possibleIndex--;
         }
         elements[possibleIndex] = temp;
      }
  }

   public static void main(String[] args)
   {
      int[] arr1 = {3, 86, -20, 14, 40};
      System.out.println(Arrays.toString(arr1));
      insertionSort(arr1);
      System.out.println(Arrays.toString(arr1));
   }
}

Under what condition will an insertion sort execute faster?

This method should sort the numbers in the passed array into ascending order. But, it does not work. Which of the following lines is wrong?

public static void insertionSort(int[] elements)
{
  for (int j = 1; j < elements.length - 1; j++)                       // line 1
  {
     int temp = elements[j];                                          // line 2
     int possibleIndex = j;                                           // line 3
     while (possibleIndex > 0 && temp < elements[possibleIndex - 1])  // line 4
     {
        elements[possibleIndex] = elements[possibleIndex - 1];        // line 5
        possibleIndex--;
     }
     elements[possibleIndex] = temp;
  }
}