AP计算机教程11-4：选择排序

选择排序从索引0开始遍历整个数组，待找到最小值之后和0位元素交换。接下来，算法对索引1、2等做同样的工作，分别找到余下元素的最小值（分别是倒数第二小、倒数第三小等等）并交换，直到把索引为array.length - 2的元素和索引为array.length - 1的元素中的较小者交换到array.length - 2为止。这样整个数组就变成由小到大升序排列的了。

选择排序的算法有如下特征：

• 嵌套循环，外层循环从0开始，最后执行到array.length - 2（第7行）
• 寻找最小值的索引应该从外层循环当前的索引值开始（第9行）
• 内层循环从外层循环索引加一开始，遍历剩余的数组元素（第10行）
• 如果内层循环当前位置的元素比当前最小值还小，则更新当前最小值索引的内容（第12-15行）
• 内层循环结束后，交换外层循环当前元素和内层循环找到的最小值元素（第17-19行）

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

import java.util.Arrays;

public class SortTest
{
   public static void selectionSort(int[] elements)
   {
      for (int j = 0; j < elements.length - 1; j++)
      {
         int minIndex = j;
         for (int k = j + 1; k < elements.length; k++)
         {
            if (elements[k] < elements[minIndex])
            {
               minIndex = k;
            }
         }
         int temp = elements[j];
         elements[j] = elements[minIndex];
         elements[minIndex] = temp;
       }
   }

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

Under what condition will a selection 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 selectionSort(int[] elements)
{
  for (int j = 0; j < elements.length − 1; j++)      // line 1
  {
     int minIndex = j;                               // line 2
     for (int k = 0; k < elements.length; k++)       // line 3
     {
        if (elements[k] < elements[minIndex])        // line 4
        {
           minIndex = k;                             // line 5
        }
     }
     int temp = elements[j];
     elements[j] = elements[minIndex];
     elements[minIndex] = temp;
   }
}