快速排序算法模板 —— 模板题

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
void  quick_sort(int q[],int l,int r) {
    if(l >= r)  return;
    // 注意要上取整
    int x = q[(l + r + 1) / 2], i = l - 1,j = r + 1;
    
    while(i < j){
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    quick_sort(q, l, i - 1);
    quick_sort(q, i, r);
}

归并排序算法模板 —— 模板题

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
void merge_sort(int* nums, int l, int r){
    if(r - l <= 1){ // 只剩下两个或者不到两个的时候
        // 正好有两个的时候,采取手动排序
        if(r - l == 1 && nums[l] > nums[r])
            swap(nums[l], nums[r]);
        return;
    }
    int mid = (l + r) >> 1;
    merge_sort(nums, l , mid);
    merge_sort(nums, mid + 1, r);
    int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
    int p1 = l, p2 = mid + 1, k = 0;
    while(p1 <= mid || p2 <= r){
        if(p2 > r || (p1 <= mid && nums[p1] <= nums[p2])) {
            temp[k++] = nums[p1++];
        }else{
            temp[k++] = nums[p2++];
        }
    }
    memcpy(nums + l, temp, sizeof(int) * (r - l + 1));
    free(temp);
    return;
}