菜单

反复PHP之接纳排序

2019年1月20日 - Php

  思路:一组数中,选出最小者与第七个地方数互换,然后在剩余数中再找最小者与第三个岗位数沟通,依次类推,循环到尾数第四个数和最后一个数比较停止。

慎选排序原理
每一次从待排序的笔录中选出最小的因素,顺序放在已排好序的队列最终,直到所有笔录排序完成。也就是:每次在n-i+1(i=1,2,…n-1)个记录中甄选关键字不大的笔录作为一如既往体系中第i个记录。基于此考虑的算法首要有大概选用排序、树型选择排序和堆排序。(那里只介绍常用的简要选取排序)

  图片 1

  测试代码:


  图片 2

先是趟排序: 原始数据:5 2 8 4 9 1

  结果:

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

  图片 3

排序结果:1 2 8 4 9 5

 


第二趟排序:

第1以外的数量{2 8 4 9 5}举行相比,2细微,

排序结果:1 2 8 4 9 5


其三趟排序:

除1、2以外的数据{8 4 9 5}进行比较,4微小,8和4调换

排序结果:1 2 4 8 9 5


第四趟排序:

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

排序结果:1 2 4 5 9 8


第五趟排序:

除第1、2、4、5以外的其它数据{9 8}举行相比,8不大,8和9沟通

排序结果:1 2 4 5 8 9


注:每回排序得到最小数的方式:for循环进行相比较,定义一个第多少个变量temp,首先前八个数相比较,把较小的数位居temp中,然后用temp再去跟剩下的数额比较,假如出现比temp小的多少,就用它代替temp中本来的多少。具体参照前面的代码示例,相信您在学排序此前曾经学过for循环语句了,那样的话,那里精晓起来就专门不难了。

代码实例

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)。

相关文章

发表评论

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

网站地图xml地图