【小白学算法】12. 排序算法-选择排序

简介: 【小白学算法】12. 排序算法-选择排序

选择排序(Selection sort)是一种简单直观的排序算法。


它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。


比如说现在有个数组[6,3,5,7,0],对其从小到大进行排序,那么选择排序的过程应该是这样的:


1268169-20210504224441667-796494851.png


从这个过程中可以看出选择排序的一些规则:


  • 选择排序一共有 数组大小-1轮。
  • 而在每一轮的排序中,又会有一个小循环,规则是:
  1. 先假定当前的这个数是最小的。
  2. 然后与后面的每个数进行比较,如果发现有更小的数,重新确定最小的数,并得到这个数的下标。
  3. 继续遍历到数组最后,于是确定出本轮的最小数以及它的下标。
  4. 进行位置交换


推导过程的代码


将数组[101,34,119,1]从小到大进行排序。


package sort;
import java.util.Arrays;
public class SelectSorting {
    public static void main(String[] args) {
        int [] arr = {101,34,119,1};
        selectSort(arr);
    }
    // 选择排序
    public static void selectSort(int[] arr) {
        // 原始数组[101,34,119,1]
        // 第一轮排序
        int minIndex = 0;
        int min = arr[0]; //假定第一个元素就是最小值
        for (int j = 0 + 1; j < arr.length; j++) {
            if (min > arr[j]) {  // 比较,如果是true,那么说明min不是最小值
                min = arr[j];  // 重置最小值
                minIndex = j;  // 重置minIndex
            }
        }
        // 最小值与arr[0]交换位置
        if (minIndex != 0) {  // 优化点:如果第一个用于比较的元素就是最小值,就不用交换位置
            arr[minIndex] = arr[0];
            arr[0] = min;
        }
        System.out.println("第一轮之后:");
        System.out.println(Arrays.toString(arr));  // 第一轮之后 [1, 34, 119, 101]
        // 第二轮排序
        minIndex = 1;
        min = arr[1]; //假定第二个元素就是最小值
        for (int j = 1 + 1; j < arr.length; j++) {
            if (min > arr[j]) {  // 比较,如果是true,那么说明min不是最小值
                min = arr[j];  // 重置最小值
                minIndex = j;  // 重置minIndex
            }
        }
        // 最小值与arr[1]交换位置
        if (minIndex != 1) {
            arr[minIndex] = arr[1];
            arr[1] = min;
        }
        System.out.println("第二轮之后:");
        System.out.println(Arrays.toString(arr));  // 第二轮之后 [1, 34, 119, 101]
        // 第三轮排序
        minIndex = 2;
        min = arr[2]; //假定第三个元素就是最小值
        for (int j = 2 + 1; j < arr.length; j++) {
            if (min > arr[j]) {  // 比较,如果是true,那么说明min不是最小值
                min = arr[j];  // 重置最小值
                minIndex = j;  // 重置minIndex
            }
        }
        // 最小值与arr[2]交换位置
        if (minIndex != 2) {
            arr[minIndex] = arr[2];
            arr[2] = min;
        }
        System.out.println("第三轮之后:");
        System.out.println(Arrays.toString(arr));  // 第三轮之后 [1, 34, 101, 119]
    }
}


根据推导过程发现的规律,转化成最终的代码:


package sort;
import java.util.Arrays;
public class SelectSorting {
    public static void main(String[] args) {
        int [] arr = {101,34,119,1};
        selectSort(arr);
        System.out.println("排序后:");
        System.out.println(Arrays.toString(arr));
    }
    // 选择排序
    public static void selectSort(int[] arr) {
        // 原始数组[101,34,119,1]
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {  // 比较,如果是true,那么说明min不是最小值
                    min = arr[j];  // 重置最小值
                    minIndex = j;  // 重置minIndex
                }
            }
            if (minIndex != i) {  // 优化点:如果第一个用于比较的元素就是最小值,就不用交换位置
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
}


如果要从大到小进行排序,很简单,只要改动这里即可:


......
                if (min < arr[j]) {  // 大于号改成小于号
                    min = arr[j];  
                    minIndex = j;  
                }
......


从过程推导再到最后形态,还是比上来直接看2层for循环要好理解的多了。

相关文章
|
21天前
|
搜索推荐 算法 C语言
C语言选择排序算法,从入门到精通只需1秒!
C语言选择排序算法,从入门到精通只需1秒!
|
12天前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
7 0
|
12天前
|
存储 算法 搜索推荐
黑马c++ STL常用算法 笔记(3) 排序算法
黑马c++ STL常用算法 笔记(3) 排序算法
|
21天前
|
算法 前端开发 搜索推荐
前端算法之选择排序
前端算法之选择排序
13 0
|
21天前
|
人工智能 算法 搜索推荐
直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序——“数据结构与算法”
直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序——“数据结构与算法”
|
21天前
|
搜索推荐 算法 C语言
【排序算法】C语言实现选择排序与冒泡排序
【排序算法】C语言实现选择排序与冒泡排序
|
21天前
|
存储 算法 搜索推荐
【数据结构与算法】归并排序(详解:递归与非递归的归并排序 | 赠:冒泡排序和选择排序)
【数据结构与算法】归并排序(详解:递归与非递归的归并排序 | 赠:冒泡排序和选择排序)
|
21天前
|
机器学习/深度学习 搜索推荐 算法
【排序算法】插入排序与选择排序详解
【排序算法】插入排序与选择排序详解
|
21天前
|
搜索推荐 算法
【八大经典排序算法】选择排序
【八大经典排序算法】选择排序
13 0
|
21天前
|
存储 算法 搜索推荐
【数据结构与算法】:选择排序与快速排序
欢迎来到排序的第二个部分:选择排序与快速排序!
【数据结构与算法】:选择排序与快速排序