左神算法-基础课-01-代码

Posted on | In , , ,

对数器

常用的获取随机数组的技巧：

1
Math.random()*(n-m)+m 	//生成大于等于m小于n的随机数；

因为这个课程开始针对对数器的认识就是排序。它有自身的输入输出的特点。所以对数器是这样写的。但是针对不同的数据结构类型，对数器的写法是不同的。

交换函数

i==j时这个交换功能会出错；

1
2
3
4
5
public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2){
        return ;
    }
    for (int end = arr.length - 1; end > 0 ; end--) {
        for (int i = 1; i <= end; i++) {
            if (arr[i-1] > arr[i]){
                swap(arr,i-1, i);
            }
        }
    }
}

插入排序

1
2
3
4
5
6
7
8
9
10
public static void insertionSort(int[] arr) {
    if (arr == null || arr.length < 2){
        return ;
    }
    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j > 0 && arr[j] < arr[j-1] ; j--) {
            swap(arr, j, j-1);
        }
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2){
        return ;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i; j < arr.length; j++) {
            minIndex = arr[minIndex] > arr[j] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
}

归并排序

1
2
3
4
5
6
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2){
        return ;
    }
    sortProcess(arr, 0, arr.length-1);
}
1
2
3
4
5
6
7
8
9
public static void sortProcess(int[] arr, int L, int R) {
    if (L == R){
        return ;
    }
    int mid = L + ((R - L) >> 1);   // 位运算优先级低于加减，所以一定要加上括号
    sortProcess(arr, L, mid);
    sortProcess(arr,mid+1, R);
    merge(arr, L, mid, R);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void merge(int[] arr, int L, int mid, int R){
    int help[] = new int[R-L+1];
    int p1 = L, p2 = mid + 1;
    int i = 0;
    while (p1 <= mid && p2 <= R){
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid){
        help[i++] = arr[p1++];
    }
    while (p2 <= R){
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[i + L] = help[i];
    }
}

小和问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static int smallSum(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    return mergeSort(arr, 0, arr.length - 1);
}

public static int mergeSort(int[] arr, int l, int r) {
    if (l == r){
        return 0;
    }
    int m = l + ((r-l) >> 1);
    return mergeSort(arr, l, m) + mergeSort(arr, m + 1, r) + merge(arr, l, m, r);
}

public static int merge(int[] arr, int l, int m, int r) {
    int help[] = new int[r - l + 1];
    int p1 = l, p2 = m + 1;
    int i = 0;
    int res = 0;
    while (p1 <= m && p2 <= r){
        res += arr[p1] < arr[p2] ? arr[p1] * (r - p2 + 1) : 0;	// 最重要的一句
        help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= m){
        help[i++] = arr[p1++];
    }
    while (p2 <= r){
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[l + i] = help[i];
    }
    return res;
}