(Java)算法学习(一): 选择排序-排序过程拆解与算法理解

夕阳UPdz

1277人浏览 · 2025-07-31 19:57:58

夕阳UPdz · 2025-07-31 19:57:58 发布

这里建议使用电脑浏览，手机可能观看困难

序.简单介绍:

选择排序是一种简单直观的排序算法，先通过外侧循环决定已排序区域和未排序区域，再由内侧循环通过重复遍历未排序部分，每次选择最小（或最大）元素，放到已排序部分的末尾来做到排序一组乱序数据的效果。其时间复杂度为 O(n²)，适用于小规模数据排序。

一.排序过程:

初始状态划分
将数组分为已排序部分（初始为空）和未排序部分（初始为整个数组）。
查找最小元素
遍历未排序部分，找到最小元素的索引。
交换元素位置
将最小元素与未排序部分的第一个元素交换，将其纳入已排序部分。
重复操作
重复上述步骤，每次缩小未排序部分的边界，直至所有元素排序完成。
演示:
这里演示从大到小的选择排序实际运行的排序逻辑:
*
* -选择排序的过程:
*
* EG: 7   3   9   2   5
*
* 每一轮循环,第一轮: i = 0
* 初始------<i指向7,即arr[0]>-------<j指向3,即arr[1]>--------------------------
* 开始>     7<-arr[i] |   3<-arr[j]   9               2                  5
* 第一步=> 判断当前arr[i]与arr[j]的大小关系,若arr[i] < arr[j],则进行交换,这里不交换
*
* 不交换>   7<-arr[i] |   3<-arr[j]   9               2                  5
* 第二步=> j向后选取 -> (j <= 数组长度 - 1) -> j循环继续
*
* j后移>    7<-arr[i] |   3           9<-arr[j]       2                 5
* 第三步=> 此处由于9(arr[j])>7(arr[i]),交换两者位置
*
* 交换后> 9<-arr[i] |   3           7<-arr[j]       2                 5
* 第四步=> j向后选取 -> (j <= 数组长度 - 1) -> j循环继续
*
* j后移>    9<-arr[i] |   3           7               2<-arr[j]        5
* 第五步=> 这里arr[i] > arr[j]，故不做交换
*
* 不交换>    9<-arr[i] |  3           7               2<-arr[j]        5
* 第六步=> j向后选取 -> (j <= 数组长度 - 1) -> j循环继续
*
* j后移>    9<-arr[i] |   3           7               2               5<-arr[j]
* 第七步=> 这里arr[i] > arr[j]，故不做交换
*
* 不交换>    9<-arr[i] |   3           7               2               5<-arr[j]
* 第八步=> j向后选取 -> (j >= 数组长度) -> j所在for循环结束，进入第二轮循环
*
*=================================================================
* 至此，第一轮循环结束，未排序区域的一个最大值(9)被排入了已排序区 -> i++ -> i = 1
*=================================================================
* 第二轮: i = 1
* 初始------<i指向3,即arr[1]>-------<j指向7,即arr[2]>--------------
* 开始>     9    3<-arr[i]    |      7<-arr[j]         2             5
* 第一步=> 此处由于7(arr[j])>3(arr[i]),交换两者位置
*
* 交换后>   9    7<-arr[i]     |      3<-arr[j]        2             5
* 第二步=> j向后选取 -> (j <= 数组长度 - 1) -> j循环继续
*
* j后移>    9    7<-arr[i]     |      3               2<-arr[j]      5
* 第三步=> 这里arr[i] > arr[j]，故不做交换
*
* 不交换> 9    7<-arr[i]     |      3               2<-arr[j]      5
* 第四步=> j向后选取 -> (j <= 数组长度 - 1) -> j循环继续
*
* j后移> 9    7<-arr[i]     |       3              2              5<-arr[j]
* 第五步=> 这里arr[i] > arr[j]，故不做交换
*
* 不交换> 9    7<-arr[i]    |       3              2              5<-arr[j]
* 第八步=> j向后选取 -> (j >= 数组长度) -> j所在for循环结束，进入第三轮循环
*=================================================================
* 至此，第二轮循环结束，未排序区域的一个最大值(7)被排入了已排序区 -> i++ -> i = 2
*=================================================================
* 第三轮: i = 2
* 初始------<i指向3,即arr[2]>-------<j指向2,即arr[3]>--------------
* 开始>    9       7     3<-arr[i]     |         2<-arr[j]        5
* 第一步=> 这里arr[i] > arr[j]，故不做交换
*
* 不交换> 9       7       3<-arr[i]     |        2<-arr[j]        5
* 第二步=> j向后选取 -> (j <= 数组长度 - 1) -> j循环继续
*
* j后移> 9    7         3<-arr[i]     |         2                5<-arr[j]
* 第三步=> 此处由于5(arr[j])>3(arr[i]),交换两者位置
*
* 交换>    9    7        5<-arr[i]     |         2                3<-arr[j]
* 第四步=> j向后选取 -> (j >= 数组长度) -> j所在for循环结束，进入第四轮循环
*=================================================================
* 至此，第三轮循环结束，未排序区域的一个最大值(5)被排入了已排序区 -> i++ -> i = 3
*=================================================================
* 第四轮: i = 3
* 初始------<i指向2,即arr[3]>-------<j指向5,即arr[4]>--------------
* 开始> 9        7         5         2<-arr[i]    |      3<-arr[j]
* 第一步=> 此处由于3(arr[j])>2(arr[i]),交换两者位置
*
* 交换>   9          7       5          3<-arr[i]    |      2<-arr[j]
* 第四步=> j向后选取 -> (j >= 数组长度) -> j所在for循环结束，进入第五轮循环
*=================================================================
* 至此，第四轮循环结束，未排序区域的一个最大值(3)被排入了已排序区 -> i++ -> i = 4
* 此时，i >= 数组长度-1 , i循环结束
* 排序结束!
*=================================================================
*排序结果: 9        7        5        3        2
*/

二.代码实现(这里使用Java语言实现):

//选择排序算法主体:

public static void select_sort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] > arr[i]) {
                MyMath.swap(arr, j, i);
            }
        }
    }
}

MyMath.swap(arr, j, i); 是我自己写的一个交换元素的方法，代码如下:

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

三.性能测试

使用了如下代码生成的随机数组,分别处理100，1000以及10000长度的乱序数组数据：

public class RandomArrayGenerator {

    /**
     * 生成指定长度的随机数组，元素范围在0-50000之间
     * @param length 数组长度
     * @return 随机整数数组
     */
    public static int[] getRandomArr(int length) {
        int[] arr = new int[length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 50000);
        }
        return arr;
    }
}