选择排序算法

2024-01-02 21:49:06

????????选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

????????选择排序的基本思想是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

????????选择排序的时间复杂度为O(n^2),其中n为待排序元素的个数。虽然时间复杂度较高,但选择排序是稳定的排序算法,且具有较好的性能表现。

实现思想:

? ? ? ? 首先,定义一个最小值min,将min赋值循环后的第一个未排序的值,将该值与后续的值进行比较,如果发现有比min还有小的值,将两个元素进行交换。如果没有发现比该元素还要小的值,说明该值不需要改动,当前位置就是其排序后的位置。依次循环,比较 (元素-1) 次即可完成排序。

推敲代码中:?
public class Sortselect {
    public static void main(String[] args) {
        int[] arrays = {12, 5, 8, 9, 4, 2};
        System.out.println("排序前:" + Arrays.toString(arrays));
        int min = arrays[0];
        for (int j = 0; j < arrays.length; j++) {
            if (min > arrays[j]) {
                //交换元素,将最小值移到相应的位置
                min = arrays[j];
                arrays[j] = arrays[0];
                arrays[0] = min;
            }
        }
        System.out.println("第一轮:" + Arrays.toString(arrays));

        min = arrays[1];
        for (int j = 1; j < arrays.length; j++) {
            if (min > arrays[j]) {
                //交换元素,将最小值移到相应的位置
                min = arrays[j];
                arrays[j] = arrays[1];
                arrays[1] = min;
            }
        }
        System.out.println("第二轮:" + Arrays.toString(arrays));

        min = arrays[2];
        for (int j = 2; j < arrays.length; j++) {
            if (min > arrays[j]) {
                //交换元素,将最小值移到相应的位置
                min = arrays[j];
                arrays[j] = arrays[2];
                arrays[2] = min;
            }
        }
        System.out.println("第三轮:" + Arrays.toString(arrays));

        min = arrays[3];
        for (int j = 3; j < arrays.length; j++) {
            if(min > arrays[j]){
                min = arrays[j];
                arrays[j] = arrays[3];
                arrays[3] = min;
            }
        }
        System.out.println("第四轮:" + Arrays.toString(arrays));

        min = arrays[4];
        for (int j = 4; j < arrays.length; j++) {
            if(min > arrays[j]){
                min = arrays[j];
                arrays[j] = arrays[4];
                arrays[4] = min;
            }
        }
        System.out.println("第五轮:" + Arrays.toString(arrays));

        min = arrays[5];
        for (int j = 5; j < arrays.length; j++) {
            if(min > arrays[j]){
                min = arrays[j];
                arrays[j] = arrays[5];
                arrays[5] = min;
            }
        }
        System.out.println("第五轮:" + Arrays.toString(arrays));
    }
}

找到规律后,实现简化:
public class SelectSort {
    public static void main(String[] args) {
        int[] arrays = {12, 5, 8, 9, 4, 2};
        System.out.println("排序前:" + Arrays.toString(arrays));
        int min = arrays[0];
        for (int i = 0; i < arrays.length - 1; i++) {
            min = arrays[i];
            for (int j = i; j < arrays.length; j++) {
                if (min > arrays[j]) {
                    //交换元素,将最小值移到相应的位置
                    min = arrays[j];
                    arrays[j] = arrays[i];
                    arrays[i] = min;
                }
            }
            System.out.println("排序中:" + Arrays.toString(arrays)); //为了看清交换顺序
        }
        System.out.println("排序后:" + Arrays.toString(arrays));
    }
}

使用下标控制进行交换(实现):
public class SelectSort2 {
    public static void main(String[] args) {
        //选择排序的时间复杂度是O(n^2)
        int[] arrays = {12, 5, 8, 9, 4, 2};
        System.out.println("排序前:" + Arrays.toString(arrays));
        for (int i = 0; i < arrays.length - 1; i++) {
            int minIndex = i;
            int min = arrays[i];
            for (int j = i + 1; j < arrays.length; j++) {
                if (min > arrays[j]) { //说明假定的最小值不是最小的那一个
                    min = arrays[j]; //重置min
                    minIndex = j; //重置minIndex
                }
            }

            //将最小值,放在array[i],即交换
            if (minIndex != i) {
                arrays[minIndex] = arrays[i];
                arrays[i] = min;
            }
            System.out.println("第" + (i + 1) + "轮:" + Arrays.toString(arrays));
        }
        System.out.println("排序前:" + Arrays.toString(arrays));
    }
}
?

文章来源:https://blog.csdn.net/qq_58341172/article/details/135342365
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。