选择排序SelectionSort

小咪咪 2022-05-23 08:28 83阅读 0赞

排序的方法有很多,冒泡排序,TopK,快排之类的,这里先说下选择排序(SelectionSort).  
先说下这个排序方法的核心思想:循环遍历,每次找到最小值,然后与该次排序数组的首位交换位置.比如:  
定义的活动数组长度为:5  
———开始排序——-  
排序前的数组为:  
2 4 4 0 0

--------------------

此趟排序,最小值为第4个位置上的0与第1个位置上的2交换位置>>  
经过第1次排序后的数组为:  
0 4 4 2 0

--------------------

此趟排序,最小值为第5个位置上的0与第2个位置上的4交换位置>>  
经过第2次排序后的数组为:  
0 0 4 2 4

--------------------

此趟排序,最小值为第4个位置上的2与第3个位置上的4交换位置>>  
经过第3次排序后的数组为:  
0 0 2 4 4

--------------------

此趟排序,最小值为第4个位置上的4与第4个位置上的4交换位置>>  
经过第4次排序后的数组为:  
0 0 2 4 4

--------------------

最终排序后的数组为:  
0 0 2 4 4  
循环排序的次数为:4次.  
———结束排序——-  
算法的核心代码如下:

int z = 0;
            //声明一个flag对循环排序次数进行存储
            int flag = 0;
            // 做第i趟排序
            for(int i = 0; i < oldArray.length - 1; i++) {
                z = i;
                //对排除了相对最小值的数组在此进行循环取剩下数组中的最小值
                for(int j = z + 1; j < oldArray.length; j++){
                    if(oldArray[j] < oldArray[z]){
                        //最小值是oldArray[j],这时最小值的存储下标是j
                        z = j;
                    }
                }
                //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
                //交换a[i]和a[z]的位置,oldArray[z]为第i轮外层循环的最小值,这时候前i-1位都是排序好的,所以把相对小的放在第i位
                if(i != z){
                    int temp = oldArray[i];
                    oldArray[i] = oldArray[z];
                    oldArray[z] = temp;
                }
                System.out.println("\n此趟排序,最小值为第"+(z+1)+"个位置上的"+oldArray[i]+"与第"+(i+1)+"个位置上的"+oldArray[z]+"交换位置>>");
                //else就是i=z的时候,这就是最后一轮,最后一轮里只剩下最大的数在队尾,所以不用操作
                //计数器加一
                flag++;
                //对每次排序所得到的结果进行遍历输出展示
                System.out.println("经过第"+(i+1)+"次排序后的数组为:");
                for(int num:oldArray){
                    System.out.print(num+" ");
                }
                System.out.println("\n___________________________________________ ____________");
            }

想多次验证的话这里提供一个快速生成指定长度的数组的方法:

//设定键盘监听事件,输入数字,进行整数校验
            Scanner sc =new Scanner(System.in);
            String n = sc.next();
            for (s = 0;s<n.length();s++){
                //判断此位上是否是数字
                if (!Character.isDigit(n.charAt(s))){
                    //此位上不是数字
                    System.out.println("输入的不是数字!");
                return ;
                }
            }
                int arrayLength = Integer.parseInt(n.toString());
                //然后根据键盘监听到的事件进行数组的生成
                int[] oldArray = new int[arrayLength];
                int random = 0;
                int temoCount = 0;
                for (int i = 0;i< arrayLength;i++){
                    random = (int) (Math.random()*arrayLength);
                    if (random != oldArray[i]){
                        oldArray[temoCount] = random;
                        temoCount++;
                    }
            }

根据这些代码,然后可以自定义整合优化控制台打印效果.  
下面简单的说下这种选择排序的时间复杂度问题,假设数组的长度为n(此处假设n为大数),第1次遍历,所循环的次数为n,选出最小值放在第1位,剩下的(n-1)位数组进行第2次排序.  
第2次遍历,循环次数为(n-1),选出最小值放在第2位,剩下的(n-2)位数组进行第3次排序.  
第3次遍历,循环次数为(n-2),选出最小值放在第3位,剩下的(n-3)位数组进行第4次排序.  
…..  
以此类推,假设一共有n(n的取值范围为\[1,+∞))个数,则总循环次数为:n+(n-1)+(n-2)…=n\*(n-1)/2–高斯!  
总调换位置次数为(n-1)次.  
其时间复杂度为O(N²).  
注:本章代码博主已经推送到个人GitHub上,有需要的可以去下载验证,地址为:  
[https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/SelectionSort.java][https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_SelectionSort.java]  
使用本代码验证输出后,效果如下图所示:

![这里写图片描述][70]  
Over!

[https_github.com_zhangruibin_Algorithm_blob_master_src_main_java_com_zhrb_rankAlgorithm_SelectionSort.java]: https://github.com/zhangruibin/Algorithm/blob/master/src/main/java/com/zhrb/rankAlgorithm/SelectionSort.java
[70]: /images/20220523/c8c11388718a4421950f5a332b9f1a08.png