选择排序从索引0开始遍历整个数组,待找到最小值之后和0位元素交换。接下来,算法对索引12等做同样的工作,分别找到余下元素的最小值(分别是倒数第二小、倒数第三小等等)并交换,直到把索引为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));
   }
}


0:00

Under what condition will a selection sort execute faster?

无论数组是什么内容,选择排序的内外层循环都需要完整执行,因而耗时不变。
3

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;
   }
}
内层循环没有从当前外层循环的索引加一处开始,造成一直会把全数组最小值往后移。
3


陈 欣

AADPS创始人

发表评论