排序(二) 选择排序

淡淡的烟草味﹌ 2022-12-10 08:59 44阅读 0赞

今天来总结一下选择排序 授人以鱼 不如授人以渔

复杂的算法 我们应该要有分治的思想 将复杂的问题拆分成一个个的小问题才能解决

选择排序的思路是这样的  
![8c42ffa5ab7186aa7f09e4ce68e338b9.png][]

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

小循环里 先找到最小值 放在最前面 如何找到最小值呢 ？

先假定第一个数为最小的 然后依次遍历 如果碰到比他小的 那min的值就更新 遍历完毕后

将最小值元素与与第一个元素发生位置互换

外层循环再次遍历 找到第二小的元素 此时就应该跳过第一个元素 把第二个元素当成循环里的最小值

完毕后再交换位置 直到外层循环完毕

补充 内层循环需要定义两个变量 一个储存最小值 一个储存最小值的索引 索引用来交换位置

要将大问题拆分成一个个小问题来解决

先模拟的第一次内层循环 后修改

min=arr[0];
    minindex=0;
    for(int j=i+1;j<arr.length;j++){ 
        if(min>arr[j]){ 
            min=arr[j];
            //这个是为了交换位置而准备的
            minindex=j;
        }
    }
    
    	
    //循环完毕后 应该交换位置 然后开始下次循环
    arr[minindex]=arr[0];
    arr[0]=min;
    
    之后外部套一个外层循环 
    for(int i=0;i<arr.length-1;i++){ 
            ......
    }

注意 有些0的地方要替换成i

完整的

public static void sort2(int[] arr) { 
    
            boolean flag=false;
            int c=0;
            for(int i=0;i<arr.length-1;i++){ 
                int min=arr[i];
                int minindex=i;
                for (int j=i+1;j<arr.length;j++){ 
                	//循环计数器
                    c++;
                    if(min>arr[j]){ 
                        flag=true;
                        min=arr[j];
                        minindex=j;
                    }
                }
                if(!flag){ 
                    break;
                }else { 
                    flag=false;
                }
                arr[minindex]=arr[i];
                arr[i]=min;
            }
            //System.out.println(Arrays.toString(arr) +"循环了"+c+"次");
        }

还是细节问题需要注意 就是循环结束的条件判断很重要

内层循环的j是跟随i一起变的 每次单位都要大1 所以 i的最大值要比数组长度  
小两个单位 比最大下标小一个单位

这样一来 当j达到最大时 正好为数组的最大下标 细品！！！

当然还有个改进的地方 如内部加一个flag 如果没有发生比较 则跳出

[8c42ffa5ab7186aa7f09e4ce68e338b9.png]: /images/20221123/c56f88476473426a9294b829ff3700df.png