• 选择排序.


    选择排序

    基本介绍

    选择排序也属于内部排序,是从欲排序的数据中,按指定的规则选出来某一元素,在依次规定交换位置后达到排序的目的.

    排序思想

    选择排序(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]进行交换,…第arr[n-2]与arr[n-1]中选取最小值,与arr[n-2]交换,总共通过n-1次交换,得到一个排序码从小到大的排序有序序列.

    思路分析图在这里插入图片描述

    用一个比较简单的数组再做一个选择排序的思路分析

    原始数组:101,34,119,1
    第一轮排序 :1,34,119,101(我们得到了我们的最小值)
    的二轮排序 :1,34,119,101
    第三轮排序: 1,34,101 ,119
    说明
    1,选择排序一共有数组大小-1轮排序
    2,每一轮排序,又是一个循环,循环的规则(代码)

    • 先假定当前这个数是最小的
    • 然后和后面的每一个数进行比较,如果发现有比当前数更小的数,就重写确定最小数,并得到下标
    • 当遍历到数组的最后时,就得到本轮最小数和下标
    • 最后进行和假定的那个最小数的位置进行交换.

    代码实现

    逐步推到的代码如下

    package sort;
    
    import java.util.Arrays;
    
    public class SelectSort {
        public static void main(String[] args) {
            int[] arr={1,2,-3,2,-5};
            selectSort(arr);
    
    
        }
        //选择排序
        public static void selectSort(int[] arr){
            //使用逐步推到的方法
            //第一轮
            //原始数组:[1,2,-3,2,-5]
            //第一轮排序 [-5, 2, -3, 2, 1]
            //算法,先简单--->做复杂,就是可以把一个复杂算法拆分成一个简单问题,在综合
    
            int minIndex=0;
            int min=arr[0];
            for(int j=0+1;j<arr.length;j++){
                if(min>arr[j]){//说明我们假定的最小值不是最小的
                    min=arr[j];//重置min
                    minIndex=j;//重置minIndex
                     }
            }
            //将最小值放在arr[0]的位置,即交换
               if (minIndex != 0) {
            arr[minIndex]=arr[0];
            arr[0]=min;}
    
            System.out.println("第一轮后:"+ Arrays.toString(arr));
    
                //第二轮
                //原始数组:[-5, 2, -3, 2, 1]
                //第二轮排序  [-5, -3, 2, 2, 1]
                 minIndex=1;
                 min=arr[1];
                for(int j=0+2;j<arr.length;j++){
                    if(min>arr[j]){//说明我们假定的最小值不是最小的
                        min=arr[j];//重置min
                        minIndex=j;//重置minIndex
                    }
                }
                //将最小值放在arr[1]的位置,即交换
                   if (minIndex != 1) {
                arr[minIndex]=arr[1];
                arr[1]=min;
                }
                System.out.println("第二轮后:"+ Arrays.toString(arr));
    
    
    
        //第三轮
        //原始数组:[-5, -3, 2, 2, 1]
        //第三轮排序  [-5, -3, 1, 2, 2]
        minIndex=2;
        min=arr[2];
                for(int j=0+3;j<arr.length;j++){
            if(min>arr[j]){//说明我们假定的最小值不是最小的
                min=arr[j];//重置min
                minIndex=j;//重置minIndex
            }
        }
        //将最小值放在arr[2]的位置,即交换
           if (minIndex != 2) {
        arr[minIndex]=arr[2];
        arr[2]=min;
        }
    
                System.out.println("第三轮后:"+ Arrays.toString(arr));
    
            //第四轮
            //原始数组:[-5, -3, 1, 2, 2]
            //第四轮排序 [-5, -3, 1, 2, 2]
            minIndex=3;
            min=arr[3];
            for(int j=0+4;j<arr.length;j++){
                if(min>arr[j]){//说明我们假定的最小值不是最小的
                    min=arr[j];//重置min
                    minIndex=j;//重置minIndex
                }
            }
            //将最小值放在arr[3]的位置,即交换
               if (minIndex != 3) {
              arr[minIndex]=arr[3];
               arr[3]=min;
             }
            System.out.println("第四轮后:"+ Arrays.toString(arr));
    
        }
    
    }
    
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96

    select sorting

    package sort;
    
    import java.util.Arrays;
    
    public class SelectSort {
        public static void main(String[] args) {
            int[] arr={1,2,-3,2,-5};
            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];//重置min
                        minIndex = j;//重置minIndex
                    }
                }
                //将最小值放在arr[0]的位置,即交换
                if (minIndex != i) {
                    arr[minIndex] = arr[i];
                    arr[i] = min;
                }
               System.out.println("第" + (i +1) + "轮后:" + Arrays.toString(arr));
    
            }
            System.out.println("最后的排序结果:" + Arrays.toString(arr));
    
    }}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    时间复杂度
    O(n2)

  • 相关阅读:
    安培龙冲刺创业板上市:收入依赖美的,邬若军、黎莉夫妇为实控人
    QT+OSG/osgEarth编译之四十一:osgUtil+Qt编译(一套代码、一套框架,跨平台编译,版本:OSG-3.6.5工具库osgUtil)
    【Linux】浅谈冯诺依曼体系结构与操作系统
    共享主机安全吗(以及如何保护它)?
    .NET ASPIRE 预览版 7 发布
    CSDN Q: “这段代码算是在STC89C52RC51单片机上完成PWM呼吸灯了吗?“
    基于AD Event日志检测NTDS凭据转储攻击
    PHP+MYSQL多条件选一通用搜索系统功能单文件7KB
    PTA天梯赛座位分配
    Centos设置nginx开机自启动设置
  • 原文地址:https://blog.csdn.net/weixin_51599093/article/details/127700590