八大排序——简单选择排序

目录

1.1基本操作：

1.2动态图：

1.3代码：

代码解释

1. main 方法

2. selectSort 方法

示例运行过程

初始数组

每轮排序后的数组

最终排序结果

代码总结

---

1.1基本操作：

选择排序（select sorting）也是一种简单的排序方法。

它的基本思想是：第一次从arr[0到]arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]到arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]到arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

1.2动态图：

1.3代码：

public class Insert {public static void main(String[] args) {int[] arr = {8,65,41,28,6,1,4,5,32,9,10};System.out.println("排序前");System.out.println(Arrays.toString(arr));selectSort(arr);}public static void selectSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {//寻找最小值，将当前的作为最小值来看待int minIndex = i;int min = arr[i];for (int j = i + 1; j < arr.length; j++) {// 当前值的下一个值和当前值判断大小，如果先一个值小，那么就进行交换 ，// 当然要记录一下当前值的 下标 ，目的是为了当前值和第一个值进行交换if (min > arr[j]) {min = arr[j];minIndex = j;}}//进行交换arr[minIndex] = arr[i];arr[i] = min;System.out.println("第" + (i + 1) + "轮后");System.out.println(Arrays.toString(arr));}}
}

代码解释

1. main 方法

public static void main(String[] args) {
    int[] arr = {8, 65, 41, 28, 6, 1, 4, 5, 32, 9, 10};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));
    selectSort(arr);
}

• 功能：程序的入口。

• 逻辑：

  • 定义了一个未排序的整数数组 arr。

  • 打印排序前的数组。

  • 调用 selectSort 方法对数组进行排序。

2. selectSort 方法

public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        // 寻找最小值，将当前的作为最小值来看待
        int minIndex = i;
        int min = arr[i];
        for (int j = i + 1; j < arr.length; j++) {
            // 当前值的下一个值和当前值判断大小，如果下一个值小，那么就更新最小值和最小值的下标
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j;
            }
        }
        // 进行交换
        arr[minIndex] = arr[i];
        arr[i] = min;
        System.out.println("第" + (i + 1) + "轮后");
        System.out.println(Arrays.toString(arr));
    }
}

• 功能：实现选择排序算法。

• 逻辑：

  1. 外层循环：

     • 遍历数组，从第一个元素到倒数第二个元素（i 从 0 到 arr.length - 2）。

     • 每次循环的目的是找到未排序部分的最小值，并将其放到已排序部分的末尾。

  2. 初始化最小值和最小值的下标：

     • minIndex 记录当前最小值的下标，初始值为 i。

     • min 记录当前最小值，初始值为 arr[i]。

  3. 内层循环：

     • 从 i + 1 开始遍历未排序部分。

     • 如果找到比 min 更小的值，则更新 min 和 minIndex。

  4. 交换最小值：

     • 将找到的最小值与当前外层循环的位置 i 的值进行交换。

  5. 打印每轮排序后的数组：

     • 每轮排序后，打印当前数组的状态。

---

示例运行过程

初始数组

[8, 65, 41, 28, 6, 1, 4, 5, 32, 9, 10]

每轮排序后的数组

1. 第1轮：

   • 找到最小值 1，与第一个元素 8 交换。

   • 结果：[1, 65, 41, 28, 6, 8, 4, 5, 32, 9, 10]

2. 第2轮：

   • 找到最小值 4，与第二个元素 65 交换。

   • 结果：[1, 4, 41, 28, 6, 8, 65, 5, 32, 9, 10]

3. 第3轮：

   • 找到最小值 5，与第三个元素 41 交换。

   • 结果：[1, 4, 5, 28, 6, 8, 65, 41, 32, 9, 10]

4. 第4轮：

   • 找到最小值 6，与第四个元素 28 交换。

   • 结果：[1, 4, 5, 6, 28, 8, 65, 41, 32, 9, 10]

5. 第5轮：

   • 找到最小值 8，与第五个元素 28 交换。

   • 结果：[1, 4, 5, 6, 8, 28, 65, 41, 32, 9, 10]

6. 第6轮：

   • 找到最小值 9，与第六个元素 28 交换。

   • 结果：[1, 4, 5, 6, 8, 9, 65, 41, 32, 28, 10]

7. 第7轮：

   • 找到最小值 10，与第七个元素 65 交换。

   • 结果：[1, 4, 5, 6, 8, 9, 10, 41, 32, 28, 65]

8. 第8轮：

   • 找到最小值 28，与第八个元素 41 交换。

   • 结果：[1, 4, 5, 6, 8, 9, 10, 28, 32, 41, 65]

9. 第9轮：

   • 找到最小值 32，与第九个元素 32 交换（无需交换）。

   • 结果：[1, 4, 5, 6, 8, 9, 10, 28, 32, 41, 65]

10. 第10轮：

    • 找到最小值 41，与第十个元素 41 交换（无需交换）。

    • 结果：[1, 4, 5, 6, 8, 9, 10, 28, 32, 41, 65]

---

最终排序结果

[1, 4, 5, 6, 8, 9, 10, 28, 32, 41, 65]

代码总结

• 算法：选择排序。

• 时间复杂度：O(n²)，其中 n 是数组的长度。

• 空间复杂度：O(1)，原地排序，不需要额外的空间。

• 优点：实现简单，适合小规模数据。

• 缺点：时间复杂度较高，不适合大规模数据。