选择排序

一、定义

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
具体步骤：

1. 首先，找到数组中最小的那个元素，将它和数组的第一个元素交换位置；
2. 再次，在剩下的元素中找到最小元素，将它和数组的第二个元素交换位置；

3. 如此往复，直到整个数组有序。

   
   1-1 选择排序运行轨迹

二、算法实现

public static void sort(Comparable[] a) {
     int n = a.length;
     for (int i = 0; i < n; i++) {
         int min = i;
         for (int j = i+1; j < n; j++) {
             if (less(a[j], a[min])) min = j;
         }
         exch(a, i, min);
         assert isSorted(a, 0, i);
     }
     assert isSorted(a);
}

三、性能分析

• 特点
  运行时间与输入无关，比较次数大约(N²)/2次；
  数据移动是最少的，移动N次；
• 时间复杂度
  O(N²)