【数据结构与算法之排序与查找】简单选择排序

川长思鸟来 2024-03-25 16:38 83阅读 0赞

#### 【数据结构与算法之排序与查找】简单选择排序 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之排序与查找】简单选择排序

简单选择排序基本方法：

在第i 趟排序中，从 n - i + 1( n = 1,2,…,n-1) 个元素中选择最小的元素作为有序序列的第i 个记录，也就是与序列中第 i 个位置上的元素交换。

每一趟选择排序都从序列里面未排好序的元素中选择最小的元素，再将这个元素与未排好序的元素中的第 1 个元素交换。

举个栗子：

![在这里插入图片描述][4dd8f64a290340e3964d202421225922.png_pic_center]

Java 实现简单选择排序：

public static void selectSort(int[] array) {
        
        int min;
        for (int i = 0; i < array.length - 1; i++) {
         // 控制排序趟数
            min = i;
    
            for (int j = i + 1; j < array.length; j++) {
        
    
                // 在未排好序的子序列中找到最小元素的位置
                if (array[j] < array[min]) {
        
                    min = j; // min 始终记录最小元素的位置
                }
            }
    
            if (min != i) {
         // 最小的元素不是未排序子序列的第1个位置
                int tmp = array[min];
                array[min] = array[i];
                array[i] = tmp;
            }
        }
    }

测试

public static void main(String[] args) {
        
    
        int[] array = {
        3, 12, 20, 1, 0, 5, 8, 19, 5};
        selectSort(array);
    
        for (int e : array) {
        
            System.out.print(e + " ");
        }
    
    }

运行结果

![在这里插入图片描述][3fb4830155e940d5ad05f68b4db2df4c.png_pic_center]

[4dd8f64a290340e3964d202421225922.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1f86cd24ec404c078e03f44cbdb8dea2.png
[3fb4830155e940d5ad05f68b4db2df4c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9656e5a94e3448bcab0eff8c0d044c07.png