选择排序、冒泡排序、插入排序【十大经典排序算法】

利用对数器验证结果【选用Arrays.sort()系统提供的来】

1 选择排序【选最小】

//选择排序【每次选出一个最小的】
public static void selectSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    for (int i = 0; i < arr.length - 1; i++){
        int min = i;//假设i位置为最小值
        for (int j = i+1; j < arr.length; j++) {
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        swap(arr, i, min);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2 冒泡排序【选最大】

//冒泡排序[每次选出最大的]
public static void bubbleSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    for (int i = 0; i < arr.length - 1; ++i){
        for(int j = 0; j < arr.length - i - 1; ++j){
            if(arr[j] > arr[j+1]){
                swap(arr, j, j+1);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3 插入排序【前面有序】

//插入排序[保证前面部分全部有序]
public static void insertSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    for(int i = 1; i < arr.length; ++i){ //保证[0, i]位置上有序
        for(int j = i - 1; j >= 0; j--){
            if(arr[j] > arr[j+1]){
                swap(arr, j, j+1);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4 对数器

4.1 gernateRandomArr(int maxSize, int maxValue)

Math.random() -> [0,1) 所有的小数，等概率返回一个
Math.random() * N -> [0,N) 所有小数，等概率返回一个
(int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个

arr[i] = (int)((Math.random()+1) * maxValue - Math.random() * maxValue);
【保证有正有负】

//构建随机数组
public static int[] generateRandomArr(int maxSize, int maxValue){
    // Math.random() -> [0,1) 所有的小数，等概率返回一个
    // Math.random() * N -> [0,N) 所有小数，等概率返回一个
    // (int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个
    int[] arr = new int[(int)(Math.random() * (maxSize + 1))];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)((Math.random()+1) * maxValue - Math.random() * maxValue);
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11

4.2 copy(int[] arr)

//复制数组
public static int[] copy(int[] arr){
    if(arr == null){
        return null;
    }
    int[] res = new int[arr.length];
    int i = 0;
    for (int num : arr) {
        res[i++] = num;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12

4.3 isEq

//判断数组是否相等
public static boolean isEq(int[] arr1, int[] arr2){
	 if((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)){
	     return false;
	 }
	 if(arr1 == null && arr2 == null){
	     return true;
	 }
	 if(arr1.length != arr2.length){
	     return false;
	 }
	 for(int i = 0; i < arr1.length; ++i){
	     if(arr1[i] != arr2[i]){
	         return false;
	     }
	 }
	 return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18