数据结构和算法学习笔记

func selectionSort[T constraints.Ordered](data []T) {
    // i 指向已处理的最后一个元素
    // j 指向还没处理的第一个元素
    // minIndex 指向未处理的最小元素
    for i := 0; i < len(arr); i++ {
        minIndex := i
        for j := i + 1; j < len(arr); j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

public class InsertionSort<E> {

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 1; i < arr.length; i++) {
            E temp = arr[i];
            int j;
            for (j = i; j > 0; j--) {
                if (temp.compareTo(arr[j - 1]) < 0) {
                    E tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                } else {
                    break;
                }
            }
            arr[j] = temp;
        }
    }
}

    public static <E extends Comparable<E>> void sort(E[] arr) {
    for (int i = 1; i < arr.length; i++) {
        E temp = arr[i];
        int j;
        for (j = i; j - 1 > 0 && temp.compareTo(arr[j - 1]) < 0; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    // 下面写法是为了防止整形溢出
    int mid = l + (r - l) / 2;
    sort(arr, l, mid);
    sort(arr, mid + 1, r);
    if (arr[mid].compareTo(arr[mid + 1]) > 0) {
        // 优化1：如果 arr[mid] < arr[mid + 1]，则说明 arr[l:mid] 和 arr[mid+1:r] 已经有序，不需要 merge
        merge(arr, l, mid, r);
    }
}

    private static <E extends Comparable<E>> void insertSort(E[] arr, int l, int r) {
    for (int i = l + 1; i <= r; i++) {
        E temp = arr[i];
        int j;
        for (j = i; j > l && temp.compareTo(arr[j - 1]) < 0; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}

private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    // 优化2：当数据规模小于 15 时，使用算法复杂度为O(n^2)的归并排序
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    // 下面写法是为了防止整形溢出
    int mid = l + (r - l) / 2;
    sort(arr, l, mid);
    sort(arr, mid + 1, r);
    if (arr[mid].compareTo(arr[mid + 1]) > 0) {
        // 优化1：如果 arr[mid] < arr[mid + 1]，则说明 arr[l:mid] 和 arr[mid+1:r] 已经有序，不需要 merge
        merge(arr, l, mid, r);
    }
}

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
    // 把 arr 中的 l 到 r 区间的元素复制到 temp 中
    System.arraycopy(arr, l, temp, l, r - l + 1);
    int i = l, j = mid + 1;
    // 每轮循环为 arr[k] 赋值
    for (int k = l; k <= r; k++) {
        if (i > mid) {
            // 左区间已经全部处理完毕
            arr[k] = temp[j];
            j++;
        } else if (j > r) {
            // 右区间已经全部处理完毕
            arr[k] = temp[i];
            i++;
        } else if (temp[i].compareTo(temp[j]) < 0) {
            // 左区间更小
            arr[k] = temp[i];
            i++;
        } else {
            // 右区间更小
            arr[k] = temp[j];
            j++;
        }
    }
}

// 自底向上的归并排序
public static <E extends Comparable<E>> void sortBU(E[] arr) {
    E[] temp = Arrays.copyOf(arr, arr.length);
    int n = arr.length;

    // 遍历合并的区间长度
    for (int sz = 1; sz < n; sz += sz) {
        // 遍历合并的两个区间的起始位置 i
        // 合并 [i, i+sz-1] 和 [i+sz, i+sz+sz-1]
        for (int i = 0; i + sz < n; i += sz + sz) {
            if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0) {
                // 当前面的区间大于后面时，才执行归并操作，否则就已经是有序的了
                int r = Math.min(i + sz + sz - 1, n - 1);
                merge(arr, i, i + sz - 1, r, temp);
            }
        }
    }
}

Random Array:
MergeSort, n = 1000000 : 0.429069 s
QuickSort, n = 1000000 : 0.257638 s
QuickSort2Ways, n = 1000000 : 0.209404 s
QuickSort3Ways, n = 1000000 : 0.400175 s
Ordered Array:
MergeSort, n = 1000000 : 0.003160 s
QuickSort, n = 1000000 : 0.189545 s
QuickSort2Ways, n = 1000000 : 0.050844 s
QuickSort3Ways, n = 1000000 : 0.382524 s
Save value Array:
MergeSort, n = 1000000 : 0.002958 s
QuickSort2Ways, n = 1000000 : 0.148120 s
QuickSort3Ways, n = 1000000 : 0.001708 s

public static <E extends Comparable<E>> void sort(E[] data) {
    for (int i = 0; i + 1 < data.length; i++) {
        for (int j = 0; j < data.length - i - 1; j++) {
            if (data[j].compareTo(data[j + 1]) > 0) {
                swap(data, j, j + 1);
            }
        }
    }
}

public static <E extends Comparable<E>> void sort2(E[] data) {
    for (int i = 0; i + 1 < data.length; i++) {
        boolean isSwapped = false;
        for (int j = 0; j < data.length - i - 1; j++) {
            if (data[j].compareTo(data[j + 1]) > 0) {
                swap(data, j, j + 1);
                isSwapped = true;
            }
        }
        if (!isSwapped) {
            break;
        }
    }
}

public static <E extends Comparable<E>> void sort3(E[] data) {
    for (int i = 0; i + 1 < data.length; ) {
        int lastSwappedIndex = 0;
        for (int j = 0; j < data.length - i - 1; j++) {
            if (data[j].compareTo(data[j + 1]) > 0) {
                swap(data, j, j + 1);
                lastSwappedIndex = j + 1;
            }
        }
//            if (lastSwappedIndex == 0) {
//                // 没有发生过交换，数组有序
//                break;
//            }
        i = data.length - lastSwappedIndex;
    }
}

public static <E extends Comparable<E>> void sort(E[] data) {
    int h = data.length / 2;
    while (h >= 1) {
        for (int start = 0; start < h; start++) {

            // 对 data[start, start+h, start+2h, start+3h, ...] 进行插入排序
            for (int i = start + h; i < data.length; i += h) {
                E t = data[i];
                int j;
                for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h) {
                    data[j] = data[j - h];
                }
                data[j] = t;
            }
        }

        h = h / 2;
    }
}

public static <E extends Comparable<E>> void sort2(E[] data) {
    int h = data.length / 2;
    while (h >= 1) {

        // 对 data[h, n) 进行插入排序
        for (int i = h; i < data.length; i += h) {
            E t = data[i];
            int j;
            for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h) {
                data[j] = data[j - h];
            }
            data[j] = t;
        }

        h = h / 2;
    }
}

public static <E extends Comparable<E>> void sort3(E[] data) {
    int h = 1;
    while (h < data.length) {
        h = h * 3 + 1;
        // 1, 4, 13, 40
    }
    while (h >= 1) {

        // 对 data[h, n) 进行插入排序
        for (int i = h; i < data.length; i += h) {
            E t = data[i];
            int j;
            for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h) {
                data[j] = data[j - h];
            }
            data[j] = t;
        }

        h = h / 3;
    }
}

// 查看元素 p 和元素 q 是否属于同一个集合
boolean isConnected(int p, int q);

// 把 p 和 q 所在的集合连接起来
void unionElements(int p, int q);

package SQRT;

import java.util.Arrays;

// LeetCode 303 307
public class NumberArray {

    private int[] data, blocks;

    private int N; // 元素总数
    private int B; // 每组元素个数
    private int Bn; // 组数

    public NumberArray(int[] nums) {
        N = nums.length;
        if (N == 0) {
            return;
        }

        B = (int) Math.sqrt(N);
        Bn = N / B + (N % B == 0 ? 0 : 1);

        data = Arrays.copyOf(nums, N);
        blocks = new int[N];
        for (int i = 0; i < N; i++) {
            blocks[i / B] += data[i];
        }
    }


    public int sumRange(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N || x > y) {
            return 0;
        }

        int bstart = x / B;
        int bend = x % B;

        int res = 0;
        if (bstart == bend) {
            for (int i = x; i <= y; i++) {
                res += data[i];
            }
            return res;
        }

        for (int i = x; i < (bstart + 1) * B; i++) {
            res += data[i];
        }
        for (int b = bstart + 1; b < bend; b++) {
            res += blocks[b];
        }
        for (int i = bend * B; i <= y; i++) {
            res += data[i];
        }
        return res;
    }

    public void update(int i, int val) {
        if (i < 0 || i >= N) {
            return;
        }

        int oldVal = data[i];
        int b = i / B;
        blocks[b] -= oldVal;
        blocks[b] += val;

        data[i] = val;
    }
}

|--cnt0 个 0--|--cnt1 个 1--|--cnt2 个 2--|
|-------------|-------------|------------|
0           cnt0        cnt1+cnt2        n

[l, r1] 区间有 r1 - l + 1 个元素
[l, r2) 区间有 r2 - l 个元素

public void setColors(int[] nums) {

    int[] cnt = new int[3];
    for (int num : nums) {
        cnt[num]++;
    }

    // 对 nums 排序，前中后 0 1 2
    for (int i = 0; i < cnt[0]; i++) {
        nums[i] = 0;
    }
    for (int i = cnt[0]; i < cnt[0] + cnt[1]; i++) {
        nums[i] = 1;
    }
    for (int i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) {
        nums[i] = 2;
    }
}

int[] cnt = new int[3];
for(int num : nums) {
    cnt[num]++;
}

总结 cnt 和 index 对应关系

0: [0, cnt[0])
1: [cnt[0], cnt[0] + cnt[1])
2: [cnt[0] + cnt[1], cnt[0] + cnt[1] + cnt[2])
3: [cnt[0] + cnt[1]+ cnt[2], cnt[0] + cnt[1] + cnt[2]+ cnt[3])

可以看到，排序就是
把 [0, cnt[0]) 设置为 0
把 [cnt[0], cnt[0] + cnt[1])) 设置为 1
把 [cnt[0] + cnt[1], cnt[0] + cnt[1] + cnt[2]) 设置为 2
……

        0  1  2  3
cnt     2  3  5  6
index   0  2  5  10  16

新开辟数组 index, 把 [index[i], index[i+1]) 区间的值为 i

index 中值的计算
index[1] = index[0] + cnt[0] (0+2=2)
index[2] = index[1] + cnt[1] (2+3=5)
index[3] = index[2] + cnt[2] (5+5=10)
……

public class Solution {
    public void setColors(int[] nums) {

        // 处理元素取值范围是 [0, R) 的计数排序
        int R = 3;

        int[] cnt = new int[R];
        for (int num : nums) {
            cnt[num]++;
        }

        // [index[i], index[i + 1]) 的值为 1
        int[] index = new int[R + 1];
        index[0] = 0;
        for (int i = 0; i < R; i++) {
            index[i + 1] = index[i] + cnt[i];
        }

        for (int i = 0; i < index.length - 1; i++) {
            for (int j = index[i]; j < index[i + 1]; j++) {
                nums[j] = i;
            }
        }
    }
}