跳转至

归并排序#
发布于2021-01-19
上次编辑2021-02-25 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def merge(A: List[int], help: List[int], left: int, mid: int, right: int) -> None:
    i, j, k = left, mid + 1, left
    while i <= mid:
        if j > right or A[i] <= A[j]:
            help[k] = A[i]
            i, k = i + 1, k + 1
        else:
            help[k] = A[j]
            j, k = j + 1, k + 1
    while j <= right:
        help[k] = A[j]
        j, k = j + 1, k + 1
    A[left : right + 1] = help[left : right + 1]


def merge_sort(A: List[int], help: List[int], left: int, right: int) -> None:
    if left >= right: return
    mid = left + ((right - left) >> 1)
    merge_sort(A, help, left, mid)
    merge_sort(A, help, mid + 1, right)
    merge(A, help, left, mid, right)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void merge(vector<int> &A, vector<int> &help, int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid) {
        if (j > right || A[i] <= A[j]) help[k++] = A[i++];
        else help[k++] = A[j++];
    }
    while (j <= right) help[k++] = A[j++];
    copy(help.begin() + left, help.begin() + right + 1, A.begin() + left);
}

void merge_sort(vector<int> &A, vector<int> &help, int left, int right) {
    if (left >= right) return ;
    int mid = left + ((right - left) >> 1);
    merge_sort(A, help, left, mid), merge_sort(A, help, mid + 1, right);
    merge(A, help, left, mid, right);
}
返回顶部

在手机上阅读