Java实现的选择排序

选择排序不管在什么样的情况下（即使是已经排好序的序列），都需要进行$n^2/2$次比较操作和$n$次交换操作，因此它的时间复杂度为O($n^2$)

代码：

/** * 选择排序（从小到大） * 从数组中选择最小的元素，与数组中第一个元素交换位置。 * 再从数组剩下的元素中选择最小的元素，与第二个元素交换位置。 * 不断地进行这样的操作，直到整个数组排序结束。 * * @Author Nino 2019/10/2 */ import java.util.Arrays; import java.util.Random; public class SelectionSort<E extends Comparable<E>> { public void sort(E[] arr) { int n = arr.length; for (int i = 0; i < arr.length; i++) { int minIndex = i; //寻找[i, n)之间的最小值 for (int j = i + 1; j < n; j++) { if (arr[j].compareTo(arr[minIndex]) < 0) { minIndex = j; } } swap(arr, i, minIndex); } } /** * 交换数组nums中i，j索引的值 * @param nums * @param i * @param j */ private void swap(E[] nums, int i, int j) { E temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } /** * 测试用例 * @param args */ public static void main(String[] args) { Random random = new Random(); Integer[] arr = new Integer[10]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.valueOf(random.nextInt(20)); } System.out.println(Arrays.asList(arr).toString()); new SelectionSort<Integer>().sort(arr); System.out.println(Arrays.asList(arr).toString()); } }

结果：

[11, 15, 0, 12, 3, 13, 14, 1, 0, 12] [0, 0, 1, 3, 11, 12, 12, 13, 14, 15]