重复PHP之选择排序

  思路:一组数惨遭,选出最小者与第一单职位反复交换,然后于剩余数中再度寻觅最小者与第二独职务反复交换,依次类推,循环到倒数第二单数及末段一个屡次较了。

挑选排序原理
每一样遍由用排序的笔录受选出最小的因素,顺序放在已解好序的阵最后,直到整个记下排序完毕。也就算是:每一样次在n-i+1(i=1,2,…n-1)个记录被摘关键字太小的记录作为一如既往序列中第i个记录。基于这考虑的算法主要出简短选择排序、树型选择排序和堆排序。(这里仅仅介绍常用的简选择排序)

  图片 1

  • 简单易行选择排序的中心思维:给定数组: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};

  测试代码:


  图片 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地图