排序2-冒泡排序、选择排序、插入排序

时间复杂度：这三种排序都是比较排序，时间复杂度都是O(n^2)，比较次数上，选择排序≈插入排序<冒泡排序，冒泡排序效率极低

基本思路：都比较简单，代码中已有注释

//冒泡排序
public static void bubbleSort(int[] arr){
        //从第一个元素开始依次向后比较，后一个更小就交换，一直交换到最后一个元素（最大）；
        //第二趟交换到倒数第二个元素（第二大）；第三趟同理,...
        for (int i = arr.length-1; i >=0; i--) {
            //标记是否交换过，如果没有交换，说明全部有序，后面无需再执行
            boolean tag = true;
            for (int j = 0; j < i ; j++) {
                if (arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    tag = false;
                }
            }
            if (tag){
                break;
            }
        }
}

//选择排序
public static void chooseSort(int[] arr){
        //选出从（0，length-1）最小的元素，放在第0个位置；选出从（1，length-1）最小的元素，放在第一个位置；以此类推...
        for (int i = 0; i < arr.length; i++) {
            int k = i+1;
            for (int j = k; j < arr.length; j++) {
                if (arr[j] < arr[k]){
                    k = j;
                }
            }
            if (k < arr.length && arr[i] > arr[k]){
                swap(arr,i,k);
            }
        }
}

//插入排序
public static void insertSort(int[] arr){
        //从第1个位置开始，与前一个数比较交换形成有序子数组，后续的位置只需要向前交换到第一个比该位置数字小的位置即可
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 ; j--) {
                if (arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
}

//交换：比较排序中常用基本操作
public static void swap(int[] arr, int j, int i) {
        if (j != i){
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
 }