关于c++:\\-On\logn-\\复杂度之排序

疾速排序

不稳固

void quick_sort(int q[], int l, int r) {if (l >= r) return;
    
    // 位移和按位逻辑运算优先级低于加减
    int i = l - 1, j = r + 1, pivot = q[l + r >> 1];
    while (i < j) {while (q[ ++ i] < pivot);
        while (q[ -- j] > pivot);
        if (i < j) swap(q[i], q[j]);
    }
    
    quick_sort(q, l, j), quick_sort(q, j + 1, 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 i = l, j = mid + 1, k = 0;
    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 shell_sort(int q[], int n) {
    int i, j, gap;

    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = gap; i < n; i ++)
            for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
                swap(a[j], a[j + gap]);
}

堆排序

不稳固

void down(int u) {
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t])
        t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])
        t = u * 2 + 1;
    if (u != t) {swap(h[u], h[t]);
        down(t);
    }
}

void heap_sort(int h[], int n) {for (int i = n / 2; i; i --) {down(i);
    }
    int cnt = 1;
    while (m --) {ans[cnt ++] = h[1];
        h[1] = h[n --];
        down(1);
    }
}