vlambda博客
学习文章列表

七大排序算法之选择排序

前言

和冒泡排序一样,这个也是简单而必须掌握的基础排序算法。

原理

遍历数组每个元素,若为升序,则寻找最小的数与第一个数交换,一趟排序结束后,最小的数位于数组第一个位置,然后在2-n个数中,寻找最小的元素放在第二个位置,往复下去,排序结束。

时间复杂度

固定:n*n

代码

public class SelectSort {

    //选择排序
    //做N趟排序,每一趟选择最小的数与前面的交换

    //时间复杂度  固定的  n*n
    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+" ");
        }
    }

}

下一篇:插入排序

入口在此:

插入排序

https://blog.csdn.net/hq942845204/article/details/80156706