排序算法 - 6.选择排序

选择排序的原理：

选择排序在开始的时候，先扫描整个列表，以找到列表中的最小元素，然后将这个元素与第一个元素进行交换。这样最小元素就放到它的最终位置上。然后，从第二个元素开始扫描，找到n-1个元素中的最小元素，然后再与第二个元素进行交换。以此类推，直到第n-1个元素(如果前n-1个元素都已在最终位置，则最后一个元素也将在最终位置上)。

选择排序的基本思想是：

每一趟在n − i + 1 ( i = 1 , 2 , . . . , n − 1 ) 个元素中选择最小的元素，并将其作为有序序列中第 i 个元素。

 public static void selectionSort(int[] array) {
     int len = array.length;
     int minIndex;
     //最后一个元素最后已经是排完的状态了，无需再排
     for (int i = 0; i < len - 1; i++) {
         //默认认为当前序列的第一个元素是当前序列中的最小/大元素
         minIndex = i;
        //找到更小的元素
         for (int j = i + 1; j < len; j++) {
             if (array[j] < array[minIndex]) {
                 minIndex = j;
             }
         }
        //交换最小/大元素和第一个元素的位置
         if (minIndex != i) {
             int temp = array[minIndex];
             array[minIndex] = array[i];
             array[i] = temp;
         }
     }
 }

算法分析

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。