反复算法之选用排序

  思路:一组数中,选出最小者与第一个职位数交换,然后在剩余数中再找最小者与第二个岗位数互换,依次类推,循环到最后多少个第二个数和最后一个数相比结束。

小小数据1,把1放在第一位,也就是1和5互换地点,

  结果:

其三趟排序:

  图片 1

排序结果:1 2 8 4 9 5

 

除第1、2、4、5以外的其余数据{9 8}举办相比,8细小,8和9互换

  图片 2


  图片 3

排序结果:1 2 4 8 9 5

  测试代码:


除第1、2、4以外的另外数据{8 9 5}举行相比,5小小的,8和5换成

除1、2以外的数量{8 4 9 5}举行相比,4微细,8和4交流

第1以外的数额{2 8 4 9 5}举行相比,2不大,

排序结果:1 2 4 5 9 8

  • 简单易行选用排序的核心思维:给定数组:int[]
    arr={里面n个数据};第1趟排序,在待排序数据arr[1]arr\[n\]中选出最小的数据,将它与arrr\[1\]交换;第2趟,在待排序数据arr\[2\]arr[n]中选出最小的数量,将它与r[2]换成;以此类推,第i趟在待排序数据arr[i]~arr[n]中选出最小的数额,将它与r[i]换成,直到整个排序完成。

  • 举例:数组 int[] arr={5,2,8,4,9,1};

第二趟排序:

第五趟排序:

选择排序原理
每便从待排序的笔录中选出最小的元素,顺序放在已排好序的行列最终,直到一切记录排序完毕。也就是:每一回在n-i+1(i=1,2,…n-1)个记录中精选关键字不大的记录作为一如既往体系中第i个记录。基于此考虑的算法紧要有大概接纳排序、树型采用排序和堆排序。(这里只介绍常用的粗略选用排序)

代码实例

public class SelectionSort {
public static void main(String[] args) {
    int[] arr={1,3,2,45,65,33,12};
    System.out.println("交换之前:");
    for(int num:arr){
        System.out.print(num+" ");
    }        
    //选择排序的优化
    for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
        int k = i;
        for(int j = k + 1; j < arr.length; j++){// 选最小的记录
            if(arr[j] < arr[k]){ 
                k = j; //记下目前找到的最小值所在的位置
            }
        }
        //在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
        if(i != k){  //交换a[i]和a[k]
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }    
    }
    System.out.println();
    System.out.println("交换后:");
    for(int num:arr){
        System.out.print(num+" ");
    }
}

运转结果

图片 4

Paste_Image.png

慎选排序的岁月复杂度:简单选取排序的可比次数与系列的起来排序无关。
假若待排序的队列有 N 个要素,则相比较次数永远都是N (N – 1) /
2。而活动次数与连串的启幕排序有关。当体系正序时,移动次数最少,为
0。当系列反序时,移动次数最多,为3N (N – 1) /
2。所以,综上,简单排序的时光复杂度为 O(N2)。



第一趟排序: 原始数据:5 2 8 4 9 1

第四趟排序:

注:每一次排序拿到最小数的主意:for循环举办相比,定义一个第五个变量temp,首先前五个数相比,把较小的数位居temp中,然后用temp再去跟剩下的数量相比较,倘诺现身比temp小的数目,就用它代替temp中原本的数目。具体参照后边的代码示例,相信您在学排序在此之前曾经学过for循环语句了,那样的话,那里通晓起来就专门容易了。



排序结果:1 2 4 5 8 9

排序结果:1 2 8 4 9 5

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图