排序算法 1017

排序算法 10/17 1、选择排序

时间复杂度为o(n^2)

public class SelectSort {
    public static int[] sort(int[] arr){
        //初始化最小下标
        int minIndex = 0;
        //外层循环逐个取得需要逐次比较的下标
        for (int i = 0 ; i < arr.length ; i++){
            //将i赋给最小下标
            minIndex = i;
            //内层循环 进行基于当前元素到数组末尾的逐次比较。
            for (int j = i ; j < arr.length ; j++){
                //逐次比较
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            //进行交换
            swap(i,minIndex,arr);
        }
        return arr;
    }
}

2、插入排序

原理：就像玩扑克，我们总会把前面的牌都变得有序，然后后面的牌依次比较，插入。

时间复杂度： o(n) - o(n^2)

public class InsertSort {
    public static int[] sort(int[] arr){
        //从第二个元素开始，依次向前比较，只要后面的比前面的小，
        //就继续比，直到大，插入，逐个向后移动
        for (int i = 1 ; i < arr.length; i++){
            //判断当前元素是否小于前一个元素，小于进入循环，交换
            for (int j = i ; j > 0 && arr[j] < arr[j-1] ; j--){
                swap(j,j-1,arr);
            }
        }
        return arr;
    }
}