插入排序从索引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));
   }
}


0:00

Under what condition will an insertion sort execute faster?

当数组已经是升序排列时,所有的内层循环都不会执行,此时耗时最少。
1

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;
  }
}
外层循环不能忽略数组的最后一位。
1


陈 欣

AADPS创始人

发表评论