树状数组 | 旋律小站

冒泡排序

 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
// 冒泡排序：超时

public int[] sortArray(int[] nums) {
    int len = nums.length;
    for (int i = len - 1; i >= 0; i--) {
        // 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较，
        // 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组
        boolean sorted = true;
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                sorted = false;
            }
        }
        if (sorted) {
            break;
        }
    }
    return nums;
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

时间复杂度：$O(N^2)$，这里 N 是数组的长度；
空间复杂度：$O(1)$，使用到常数个临时变量。

选择排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 选择排序：每一轮选择最小元素交换到未排定部分的开头

public int[] sortArray(int[] nums) {
    int len = nums.length;
    // 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子
    for (int i = 0; i < len - 1; i++) {
        // 选择区间 [i, len - 1] 里最小的元素的索引，交换到下标 i
        int minIndex = i;
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        swap(nums, i, minIndex);
    }
    return nums;
}

算法思想 1：贪心算法：每一次决策只看当前，当前最优，则全局最优。注意：这种思想不是任何时候都适用。

算法思想 2：减治思想：外层循环每一次都能排定一个元素，问题的规模逐渐减少，直到全部解决，即「大而化小，小而化了」。运用「减治思想」很典型的算法就是大名鼎鼎的「二分查找」。

优点：交换次数最少。

时间复杂度：$O(N^2)$，这里 N 是数组的长度；
空间复杂度：$O(1)$，使用到常数个临时变量。

插入排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// 插入排序：稳定排序，在接近有序的情况下，表现优异

public int[] sortArray(int[] nums) {
    int len = nums.length;
    // 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组
    for (int i = 1; i < len; i++) {
        // 先暂存这个元素，然后之前元素逐个后移，留出空位
        int temp = nums[i];
        int j = i;
        // 注意边界 j > 0
        while (j > 0 && nums[j - 1] > temp) {
            nums[j] = nums[j - 1];
            j--;
        }
        nums[j] = temp;
    }
    return nums;
}

优化：「将一个数字插入一个有序的数组」这一步，可以不使用逐步交换，使用先赋值给「临时变量」，然后「适当的元素」后移，空出一个位置，最后把「临时变量」赋值给这个空位的策略（就是上面那张图的意思）。编码的时候如果不小心，可能会把数组的值修改，建议多调试；

特点：「插入排序」可以提前终止内层循环（nums[j - 1] > temp 不满足时），在数组「几乎有序」的前提下，「插入排序」的时间复杂度可以达到 $O(N)$

由于「插入排序」在「几乎有序」的数组上表现良好，特别地，在「短数组」上的表现也很好。因为「短数组」的特点是：每个元素离它最终排定的位置都不会太远。为此，在小区间内执行排序任务的时候，可以转向使用「插入排序」。

时间复杂度：$O(N^2)$，这里 N 是数组的长度；
空间复杂度：$O(1)$，使用到常数个临时变量。

归并排序

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
 * 列表大小等于或小于该大小，将优先于 mergeSort 使用插入排序
 */
private static final int INSERTION_SORT_THRESHOLD = 7;

public int[] sortArray(int[] nums) {
    int len = nums.length;
    int[] temp = new int[len];
    mergeSort(nums, 0, len - 1, temp);
    return nums;
}

/**
 * 对数组 nums 的子区间 [left, right] 进行归并排序
 *
 * @param nums
 * @param left
 * @param right
 * @param temp  用于合并两个有序数组的辅助数组，全局使用一份，避免多次创建和销毁
 */
private void mergeSort(int[] nums, int left, int right, int[] temp) {
    // 小区间使用插入排序
    if (right - left <= INSERTION_SORT_THRESHOLD) {
        insertionSort(nums, left, right);
        return;
    }

    int mid = left + (right - left) / 2;
    // Java 里有更优的写法，在 left 和 right 都是大整数时，即使溢出，结论依然正确
    // int mid = (left + right) >>> 1;

    mergeSort(nums, left, mid, temp);
    mergeSort(nums, mid + 1, right, temp);
    // 如果数组的这个子区间本身有序，无需合并
    if (nums[mid] <= nums[mid + 1]) {
        return;
    }
    mergeOfTwoSortedArray(nums, left, mid, right, temp);
}

/**
 * 对数组 arr 的子区间 [left, right] 使用插入排序
 *
 * @param arr   给定数组
 * @param left  左边界，能取到
 * @param right 右边界，能取到
 */
private void insertionSort(int[] arr, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int temp = arr[i];
        int j = i;
        while (j > left && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
}

/**
 * 合并两个有序数组：先把值复制到临时数组，再合并回去
 *
 * @param nums
 * @param left
 * @param mid   [left, mid] 有序，[mid + 1, right] 有序
 * @param right
 * @param temp  全局使用的临时数组
 */
private void mergeOfTwoSortedArray(int[] nums, int left, int mid, int right, int[] temp) {
    System.arraycopy(nums, left, temp, left, right + 1 - left);

    int i = left;
    int j = mid + 1;

    for (int k = left; k <= right; k++) {
        if (i == mid + 1) {
            nums[k] = temp[j];
            j++;
        } else if (j == right + 1) {
            nums[k] = temp[i];
            i++;
        } else if (temp[i] <= temp[j]) {
            // 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前）
            nums[k] = temp[i];
            i++;
        } else {
            // temp[i] > temp[j]
            nums[k] = temp[j];
            j++;
        }
    }
}

优化 1：在「小区间」里转向使用「插入排序」，Java 源码里面也有类似这种操作，「小区间」的长度是个超参数；优化 2：在「两个数组」本身就是有序的情况下，无需合并；优化 3：全程使用一份临时数组进行「合并两个有序数组」的操作，避免创建临时数组和销毁的消耗，避免计算下标偏移量。注意：实现归并排序的时候，要特别注意，不要把这个算法实现成非稳定排序，区别就在 <= 和 < ，已在代码中注明。「归并排序」比「快速排序」好的一点是，它借助了额外空间，可以实现「稳定排序」，Java 里对于「对象数组」的排序任务，就是使用归并排序（的升级版 TimSort，在这里就不多做介绍）。

复杂度分析：

时间复杂度：$O(N\log N)$，这里 N是数组的长度；空间复杂度：$O(N^2)$，辅助数组与输入数组规模相当。

快排

 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
private static final Random RANDOM = new Random();

private void quickSort(int[] arr, int left, int right) {
    if (right - left < INSERTION_SORT_THRESHOLD) {
        insertSortInMergeSort(arr, left, right);
        return;
    }
    int pIdx = partition(arr, left, right);
    quickSort(arr, left, pIdx - 1);
    quickSort(arr, pIdx + 1, right);
}

private int partition(int[] arr, int left, int right) {
    int pivotIdx = RANDOM.nextInt(right - left + 1) + left;
    swap(arr, left, pivotIdx);

    int pivot = arr[left];

    while (left < right) {
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

实现细节（注意事项）：（针对特殊测试用例：顺序数组或者逆序数组）一定要随机化选择切分元素（pivot），否则在输入数组是有序数组或者是逆序数组的时候，快速排序会变得非常慢（等同于冒泡排序或者「选择排序」）；

时间复杂度：$O(N\log N)$，这里 N 是数组的长度；空间复杂度：$O(\log N)$，这里占用的空间主要来自递归函数的栈空间。

冒泡排序#

选择排序#

插入排序#

归并排序#

快排#

堆排序#

冒泡排序

选择排序

插入排序

归并排序

快排

堆排序