a_day 阅读(360) 评论(0)

前言:

  继续排序方法,紧接早上的插入排序,紧跟其后,现在跟新上选择排序算法

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

情景描述:

  新学期换了新体育老师,面对同样的排队情景,他说道:“我不管之前是怎么教的,之后都按照我的来做,大家自己进行选择排序”。

  1.   从第一位同学开始,和第二位同学比较,谁矮了,谁就记着目前自己是最矮的(可以站前面,嘿嘿), 然后再和第三位同学比较...最矮的依次和后面每位同学比较(这里的最矮是实时变化的),最后自己跑到本次排序队列第一个位置进行位置互换
  2.   排除已经排好队的同学,重复步骤1,每次选出一个最矮的,站到本次队列的第一个,直到剩下最后一人,排列完成

  有的同学说:“这不是和之前老湿说的冒泡的一样嘛”

  有的同学则说:“不一样,感觉没那么费劲了”
     老湿说:“都对,思想和冒泡是一样的,每次选出要排列里面的--最高或最低相应站到最后或最前,但是,冒泡它每次比较都要换位置,而咱这选择不需要每次都换,咱先把目前最高或最低记着(缓存起来),拿缓存和后面的人比,就不需要每次相邻的都得两两比较了......”

  同学们瞬间大悟,大湿高明~!


  上图中,黄色部分为每次新一轮排序的第一个缓存对象(随时变化),深色部分为已排序列表


代码片段:

 

/**
     * 选择排序,从当前位(0开始)开始和下一位依次比较,找到最小元素,让当前位和最小元素换位,其他元素不变
     * 继续从当前位的下一位开始,依次查找最小元素并换位,直至最后一位
     * @param arr
     * @return
     */
    public static int[] selectSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int min = arr[i]; // 每次都认为当前队列第一位为最小值,进行缓存
            int index = i;       // 缓存最小值(变化)坐标
            for (int k = i + 1; k < len; k++) { // 向后比较
                if (arr[k] <= min) { // 如果后一个小于等于前一个
                    min = arr[k]; // 更换最小值
                    index = k; // 变更最小值坐标
                }
            }
            if (min == arr[i]) // 相等则不变化,默认保留当前队列第一个为最小
                continue;
            // 循环完毕,找出了最小值的坐标,即为index,把当前坐标i元素和最小元素换位
            int k = arr[i];
            arr[i] = arr[index];
            arr[index] = k;
        }
        return arr;
    }

 


优点:移动数据的次数少

缺点:比较次数多,且根据元素排列,不具稳定性

 

                              写作不易,难免有疏漏和错误,还请慷慨指正,不错请推荐

  ps:欢迎转载,转载请注明出处:http://www.cnblogs.com/liuyitian/p/4054437.html


                                          每天多学一点点     代码少敲一点点