选择排序法

in 算法与数据结构 with 0 comment

选择排序(Selection sort)

上一篇记录了冒泡排序,本篇章记录的是选择排序,希望加深理解并手写出选择排序的代码。 选择排序的核心:在一个列表中找出最小值(或最大值),放到指定位置 时间复杂度:O(N^2)

分析

1.int[] arr = {6,2,10,5}; 2.列表中的数字从arr[0] (或者i=0)开始,依次往后比较,说明需要循环 arr.length - 1 躺 3.在每一躺中,从arr[0+1] (或者i+1)开始,循环比较 arr.length -1 次数 4.在比较次数的过程中,需要找出最大(最小)值 5.进行交换

选择排序实现

模拟一下每一躺循环的过程

public void selectionSortTry(){
		int[] arr =  {6,2,10,5};
        //sort.selectionSortTry(arr);

        //假定max是最大的arr[0],这里指下标a
        int max = 0;
		
        //第一趟,这里数字6会跟列表中每一位逐一比较一次,然后取到最大值的下标
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[max]) {
                max = i; //max = i = 2
            }
        }

        //就arr数组而言,取到max = 2 使用临时变量,让两个数互换
        int temp;
        temp = arr[max];
        arr[max] = arr[0];
        arr[0] = temp;

        //int[] arr = [10, 2, 6, 5]


        //第二趟,这里数字2会跟列表中每一位逐一比较一次,然后取到最大值的下标
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] > arr[max]) {
                max = i; //max = i = 2
            }
        }

        //就arr数组而言,取到max = 2 使用临时变量,让两个数互换
        temp = arr[max];
        arr[max] = arr[1];
        arr[1] = temp;

        //int[] arr = [10, 6, 2, 5]



        //第三趟,这里数字2会跟列表中每一位逐一比较一次,然后取到最大值的下标
        for (int i = 3; i < arr.length; i++) {
            if (arr[i] > arr[max]) {
                max = i; //max = i = 3
            }
        }

        //就arr数组而言,取到max = 3 使用临时变量,让两个数互换
        temp = arr[max];
        arr[max] = arr[2];
        arr[2] = temp;

        //int[] arr = [10, 6, 5, 2]
}

总结一下 1.躺数,从i = 0开始,arr.length - 1次 2.比较次数,每次从i+1开始,arr.length - 1次 3.max下标,开始循环躺数时,max = i 下标

选择排序代码优化

public void selectionSort(int[] arr){
        //遍历需要进行的躺数(如数组第一位要和其它数字逐一比较称为一趟)
        for (int i = 0; i < arr.length - 1; i++) {
            int max = i;//记录最大值的下标,一开始认为数组第一位就是最大值(让它从第一位开始记录)

            //遍历数组个数并更新最大值下标
            for (int j = i+1; j < arr.length; j++) {
                //如果后面的值比第一个大,那么记录下标,后面进行交换把它放在前面一位
                if (arr[j] > arr[max]){
                    max = j;//更新最大值的下标
                }

            }
            //进行交换
            int temps = arr[max];
            arr[max] = arr[i];
            arr[i] = temps;

        }
        System.out.println(Arrays.toString(arr));
    }

不一定是最好的实现方式,有错误请指出,不胜感激! 选择排序:ShutDown...

0评论