1、选择排序
- Select Sort，最简单的排序算法之一；
- 步骤：重复遍历数组（第一次从第一个位置开始，第二次从第二个位置开始），每遍历依次，都将该次遍历遇到的最小数放在数组的前端；
- 趟数：n 个数据的数组，选择排序需要排 n-1 趟才能完成排序；
- 复杂度：平均时间复杂度为O(n^2)，实际运行下来的时长比冒泡排序要短；
- 稳定性：选择排序的一趟选择中，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了。所以冒泡排序是一种不稳定算法。
2、Java代码
package Algorithm.Sort;import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;/*** @author yhx* @date 2020/09/29*/
public class SelectSort {private static final int NUM = 100;public static void main(String[] args) {int[] arr1 = {101, 34, 119, 1, -20};int[] arr2 = {101, 34, 119, 1, -20};int[] arr3 = new int[NUM];for (int i = 0; i < NUM; i++) {// .random()用于产生一个0到1的随机小数arr3[i] = (int) ((Math.random() * 2 - 1) * NUM);}Select selectSort = new Select();// 选择排序的过程演示System.out.println("选择排序的过程演示：");selectSort.selectProcess(arr1);System.out.println();// 整合过的选择排序System.out.println("整合过的选择排序：");selectSort.select(arr2);System.out.println(Arrays.toString(arr2));System.out.println();// 用大量数据测试优化后的选择排序的排序速度System.out.println("整合后的选择排序演示：");// Date()函数用于标记时间Date date1 = new Date();// 时间标记精确到毫秒SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");String date1Str = simpleDateFormat.format(date1);System.out.println("arr3[]排序前的时间是：" + date1Str);selectSort.select(arr3);Date date2 = new Date();String date2Str = simpleDateFormat.format(date2);System.out.println("arr3[]排序后的时间是：" + date2Str);System.out.println("arr3[]选择排序后的结果为：" + Arrays.toString(arr3));}
}class Select {/*** 选择排序的详细步骤演示** @param arr 传入的数组*/public void selectProcess(int[] arr) {// 第一趟排序int minIndex = 0;int min = arr[0];// 从第2个元素开始遍历数组一遍，找到最小元素的值和索引for (int i = 1; i < arr.length; i++) {if (min > arr[i]) {min = arr[i];minIndex = i;}}// 最小值与第1个位置互换位置arr[minIndex] = arr[0];arr[0] = min;System.out.println("arr1[]第一趟排序后：" + Arrays.toString(arr));// 第二趟排序minIndex = 1;min = arr[1];for (int i = 1 + 1; i < arr.length; i++) {if (min > arr[i]) {min = arr[i];minIndex = i;}}// 最小值与第2个位置互换位置arr[minIndex] = arr[1];arr[1] = min;System.out.println("arr1[]第二趟排序后：" + Arrays.toString(arr));// 第三趟排序minIndex = 2;min = arr[2];for (int i = 1 + 1 + 1; i < arr.length; i++) {if (min > arr[i]) {min = arr[i];minIndex = i;}}// 最小值与第3个位置互换位置arr[minIndex] = arr[2];arr[2] = min;System.out.println("arr1[]第三趟排序后：" + Arrays.toString(arr));// 第四趟排序minIndex = 3;min = arr[3];for (int i = 1 + 1 + 1 + 1; i < arr.length; i++) {if (min > arr[i]) {min = arr[i];minIndex = i;}}// 最小值与第4个位置互换位置arr[minIndex] = arr[3];arr[3] = min;System.out.println("arr1[]第四趟排序后：" + Arrays.toString(arr));}/*** 整合过的选择排序** @param arr 待排序数组*/public void select(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;int min = arr[minIndex];for (int j = i + 1; j < arr.length; j++) {if (min > arr[j]) {min = arr[j];minIndex = j;}}if (minIndex != i) {arr[minIndex] = arr[i];arr[i] = min;}}}
}
3、运行结果
选择排序的过程演示：
arr1[]第一趟排序后：[-20, 34, 119, 1, 101]
arr1[]第二趟排序后：[-20, 1, 119, 34, 101]
arr1[]第三趟排序后：[-20, 1, 34, 119, 101]
arr1[]第四趟排序后：[-20, 1, 34, 101, 119]整合过的选择排序：
[-20, 1, 34, 101, 119]整合后的选择排序演示：
arr3[]排序前的时间是：2020-09-29 14:47:22:630
arr3[]排序后的时间是：2020-09-29 14:47:22:658
arr3[]选择排序后的结果为：[-95, -95, -91, -89, -88, -83, -83, -82, -81, -78, -76, -75, -71, -66, -62, -59, -57, -56, -54, -52, -52, -51, -51, -46, -44, -44, -43, -41, -40, -39, -37, -35, -35, -35, -32, -29, -26, -25, -21, -21, -21, -18, -18, -17, -17, -16, -10, -9, -8, -5, -5, -5, -3, -2, -1, 3, 3, 4, 5, 6, 6, 6, 10, 10, 17, 18, 19, 25, 25, 26, 27, 28, 29, 29, 31, 31, 33, 36, 38, 39, 40, 40, 44, 45, 46, 49, 49, 52, 61, 64, 66, 68, 71, 74, 74, 78, 81, 88, 93, 93]