选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第 选择排序 - 图1个记录交换。
最优时间复杂度 选择排序 - 图2, 最坏时间复杂度 ** **选择排序 - 图3；

代码

  1. /**
  2.  * @Description: 选择排序：
  3.  * 通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，
  4.  * 并和i个体记录交换
  5.  * 最优时间复杂度 O(n), 最坏时间复杂度 O(n2)
  6.  * @Author: lizhouwei
  7.  * @CreateDate: 2018/6/23 9:35
  8.  */
  9. public class SelectSort {
  11.     public static void selectSort(Integer[] arr) {
  12.         if (arr == null || arr.length == 0) {
  13.             return;
  14.         }
  15.         SortUtil.printArray("选择排序前", arr);
  16.         int min = 0;
  17.         int i = 0;
  18.         for (i = 0; i < arr.length; i++) {
  19.             min = i;
  20.             for (int j = i + 1; j < arr.length; j++) {
  21.                 if (arr[j] < arr[min]) {
  22.                     min = j;
  23.                 }
  24.             }
  25.             SortUtil.swap(arr, i, min);
  26.         }
  27.         SortUtil.printArray("选择排序后", arr);
  29.     }
  31. }

时间复杂度

选择排序最大特点就是交换移动数据次数相当少，并且无论最好最差的情况，其比较次数都是一样的，即第i趟排序需要进行n-i 次关键字的比较，此时需要选择排序 - 图4次，因此时间复杂度为 选择排序 - 图5；