排序算法之选择排序-java版---shengjk1

1. 选择排序

1.1 选择排序的基本介绍

选择排序类似于冒泡排序，均属于内排，也可以看做是对冒泡排序的优化。因为冒泡排序是比较相邻的两个值，然后直接交换。而选择排序是找到一个最大值或者最小值之后，再进行交换。

1.2 选择排序思想

第一次从 arr[0] ~ arr[n-1]中选择一个最大值或者最小值，与 arr[0] 交换；第二次从 arr[1] ~ arr[n-1]中选择一个最大值或者最小值，与 arr[1] 交换； 第二次从 arr[2] ~ arr[n-1]中选择一个最大值或者最小值，与 arr[2] 交换； 依次类推。

1.3 选择排序的时间复杂度和空间复杂度等

算法名称

平均时间复杂度

最好情况

最坏情况

空间复杂度

稳定性

选择排序

O(n^2)

O(n)

O(n^2)

O(1)

稳定

2. 代码演示/** * @author shengjk1 * @date 2020/3/30 */ public class SelectSort { public static void main(String[] args) { int[] arr = {1, 10, 2, 30, -1}; selectSort(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } public static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { minIndex = arr[i] < arr[j] ? i : j; } if (minIndex != i) { int tem = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tem; } } } } ---来自腾讯云社区的---shengjk1