选择排序
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长4分钟
选择排序是一个简单的排序算法，算法从第一个元素开始，通过不断从右边找到找到最小元素，替换当前元素，直到找到最后一个元素，数组就排序完成。最好的情况是当数组已经有序时，时间复杂度是O(N)，最坏的情况是当数组是反序时，时间复杂度是O(N^2)，平均时间复杂度是O(N^2)。
算法主要思路是
- 第一轮，从数组的第一个元素开始，向右查找最小的元素，然后替换当前元素。
- 第一轮查找完成后，数组中第一个元素就是最小的元素。
- 第二轮，从第二个元素开始向右查找最小的元素，然后替换当前元素。
- 第二轮查找完成后，数组中第二个元素就是第二小的元素。
- ...
- 直到右边只剩下一个元素，也就是数组中最大的元素，排序就完成。
比如数组[4, 2, 1, 3, 7, 6, 5]选择排序过程如下
1/6
选择排序算法实现如下。
1import java.util.Arrays;
2
3public class Main {
4
5 public static void main(String[] args) {
6 int[] arr = {4, 2, 1, 3, 7, 6, 5};
7 selectionSort(arr);
8 System.out.println(Arrays.toString(arr));
9 }
10
11 /**
12 * 选择排序
13 * 从第一个元素开始，查找右边最小的元素，然后替换当前元素
14 *
15 * @param arr 待排序数组
16 */
17 public static void selectionSort(int[] arr) {
18 for (int i = 0; i < arr.length - 1; i++) {
19 int min = i;
20 /**
21 * 查找右边最小的元素
22 */
23 for (int j = i + 1; j < arr.length; j++) {
24 if (arr[j] < arr[min]) {
25 min = j;
26 }
27 }
28 /**
29 * 替换当前元素和最小的元素
30 */
31 swap(arr, i, min);
32 }
33 }
34
35 /**
36 * 交换元素
37 *
38 * @param arr 数组
39 * @param i，j 待交换的位置
40 */
41 public static void swap(int[] arr, int i, int j) {
42 int temp = arr[i];
43 arr[i] = arr[j];
44 arr[j] = temp;
45 }
46}
47注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
选择排序也是一种效率比较低的排序算法，一般适用于对效率要求不高或者数据规模较小的排序。
排序算法选择排序
1