希尔 快速 堆排序 归并排序 照抄

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int si = 500;
int arr[si];
int n;

int partition(int a[], int l, int r) {
    int pivot = a[l];//这一个作为中心 也是暂存temp
    while (l < r) {
        while (l < r && a[r] >= pivot) r--;//退出循环时 a[r]比pivot小 应该在pivot左边 而在右边 把它倒腾到左边的位置 a[l] = a[r]; l这个位置刚刚好没人用
        a[l] = a[r];//把a[r]放在左边
        while (l < r && a[l] <= pivot) l++;//退出循环时 a[l]比pivot大 应该在pivot右边 而在左边 把它倒腾到右边的位置 a[r] = a[l]; r这个位置刚刚好没人用
        a[r] = a[l];//把a[l]放在右边
    }//两个子while循环多次之后 就能得到 左边都比pivot小 右边都比pivot大的序列
    
    a[l] = pivot;//还给他
    return l;//l就是pivot的位置
}
void Qsort(int a[], int l, int r) {
    if (l < r) {
        int pivot = partition(a, l, r);
        //pivot 中心 不用动
        Qsort(a, l, pivot - 1);
        Qsort(a, pivot + 1, r);
    }
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    Qsort(arr, 0, n);
    //测试序列
    //10 1 9 2 8 4 7 6 0 3 5
    //20 5 1 2 34 70 1 40 4 13 4 1 9 2 8 4 7 6 0 3 5
    for (int i = 1; i <= n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int si = 500;
int arr[si];
int n;

void AdjustDown(int h[], int k, int len) {//将第k个元素 向下进行调整
    int te = h[k];
    for (int i = 2 * k; i <= len; i *= 2) {
        if (i < len && h[i] < h[i + 1]) i++;//左孩子和右孩子比较 取比较大的孩子的index
        if (te >= h[i]) break;//te比他大 那h[k]不用动 就是(子)大根堆
        else {
            h[k] = h[i];//h[k]也就是te 比他小 要交换 变成(子)大根堆
            k = i;//父亲已经调整好了 是大根堆 向下调整子树 让他们变成大根堆
        }
    }
    h[k] = te;
}
void buildMaxHeap(int h[]) {
    for (int i = n / 2; i > 0; i--)//从i = n/2 到 i= 0 反复调整堆
        AdjustDown(h, i, n);
}
void hsort(int h[]) {
    buildMaxHeap(h);//初始建堆
    for (int i = n; i > 1; i--) {
        cout << h[1] << " ";//大根堆 第一个就是最大的
        swap(h[i], h[1]);
        AdjustDown(h, 1, i - 1);
    }
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    hsort(arr);
    //测试序列
    //10 1 9 2 8 4 7 6 0 3 5
    //20 5 1 2 34 70 1 40 4 13 4 1 9 2 8 4 7 6 0 3 5
    for (int i = 1; i <= n; i++) {
    //    cout << arr[i] << " ";
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int si = 500;
int arr[si];
int temp[si + 1];
int n;

void Merge(int a[], int low, int m, int h) {
    int i, j, k;
    for (i = low; i <= h; i++)
        temp[i] = a[i];//将所有目标元素复制到辅助数组
    for (i = k = low, j = m + 1; i <= m && j <= h; k++) {
        if (temp[i] <= temp[j])
            a[k] = temp[i++];//将小的复制到a中
        else
            a[k] = temp[j++];
    }
    while (i <= m) a[k++] = temp[i++];
    while (j <= h) a[k++] = temp[j++];
    //这两个while只会执行一个
}
void MergeSort(int a[], int l, int h) {
    if (l < h) {//low high
        int mid = l + h >> 1;
        MergeSort(a, l, mid);
        MergeSort(a, mid + 1, h);
        Merge(a, l, mid, h);
    }
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    MergeSort(arr, 1, n);
    //测试序列
    //10 1 9 2 8 4 7 6 0 3 5
    //20 5 1 2 34 70 1 40 4 13 4 1 9 2 8 4 7 6 0 3 5
    for (int i = 1; i <= n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}