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

C++实现(照抄)一些

插入排序之希尔排序

#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 shellsort(int a[], int n) {
    for (int dk = n / 2; dk >= 1; dk >>= 1) {
        int te = 0;
        for (int i = dk + 1; i <= n; i++) {//i是gap 与前面的i - dk比较
            if (a[i] < a[i - dk]) {//a[i - dk] 应该比a[i]小 才是增序 不满足条件 把前面的都换位置 挪腾
                te = a[i];//暂存i
                int j;
                for (j = i - dk; j > 0 && te < a[j]; j -= dk) {
                    //te < a[j]找到合适的位置 j小于i a[j]应该比a[i]小 才是增序 不满足条件
                    a[j + dk] = a[j];//挪腾
                }
                a[j + dk] = te;
            }
        }
    }
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    shellsort(arr, 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;

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;
}

堆排序 大根堆 结合P311自己画的例子看

#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;
}

基数排序 稳定 讲解看  https://segmentfault.com/q/1010000006110201

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

int maxbit(int a[]) {
    int m = -1e9;
    for (int i = 0; i < n; i++) m = max(m, a[i]);
    int d = 0;
    while (m) {
        d++; m /= 10;
    }
    return d;
}
int radixsort(int a[]) {
    int temp[n];//辅助数组
    int d = maxbit(a);//总共多少位
    int r = 10;
    int count[r];//也就是书上的r
    fill(temp, temp + n, 0);
    int radix = 1;
    
    while (d--) {
        fill(count, count + r, 0);
        for (int i = 0; i < n; i++) {
            int k = (a[i]/radix) % 10;//按照基数排序的思想 提取一位 第k个桶
            count[k]++;//统计每个桶的里面会装几个
        }
        for (int i = 1; i < n; i++) {
            count[i] += count[i - 1];//最终的桶
        }
        for (int i = n - 1; i >= 0; i--) {//count[9]等于n
            int k = (a[i]/radix) % 10;//第k个桶
            count[k]--;//从这个桶中取出一个 
            temp[count[k]] = a[i];//放入temp 从第n-1个位置一直放到第0个
        }
        for (int i = 0; i < n; i++) {
            a[i] = temp[i];//搞好了 复制回原来的数组
        }
        radix *= 10;
    }
}
int main(){
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    radixsort(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 = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}