数据结构实验12 ：排序

实验12 ：排序

要求：

直接插入排序；
折半插入排序；
希尔排序;
冒泡排序
简单选择排序
树型选择排序
堆排序
详情见代码，注释应该比较清晰。
（树形排序暂时还没有，等着补上（因为这个太费时间了））
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 5;
int b[N], a[N];
int n;

void InsertSort(int a[]) { // 直接插入排序（升序）


    int i, j;
    for (i = 2; i <= n; i++) {
        if (a[i] < a[i - 1]) {  // 反之， 若a[i] >= a[i - 1] ，则此时这部分数组是升序的， 则不用处理
            a[0] = a[i];  // a[0] 叫监视哨
            for (j = i - 1; a[0] < a[j]; j--) {
                // 这里的判断条件不 加等号即不是 a[0] <= a[j] 有两个原因
                // 1. 保持排序的稳定性
                // 2. 如果加了等号， 那么当 i == 2 时， j == 0 ， 然后 a[0] <= a[j]  此循环继续 j 变为-1 那么就变成 a[-1] 虽然这是合法的， 但会出现莫名的错误
                a[j + 1] = a[j];
            }
            a[j + 1] = a[0];
        }
    }
}

void BInsertSort(int a[]) { // 折半插入排序

    int i, j, high, low, mid;
    for (i = 2; i <= n; i++) {
        if (a[i] < a[i - 1]) {
            a[0] = a[i];
            low = 1, high = i - 1;
            while (low <= high) {
                mid = low + high >> 1; // 二进制运算， 相当于 （low + high）/ 2
                if (a[0] < a[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }

            for (j = i - 1; j >= high + 1; j--) {
                a[j + 1] = a[j];
            }
            a[high + 1] = a[0];
        }
    }
}

void ShellInsert(int a[], int dk) {  // 一趟 增量为dk的希尔排序
    for (int i = dk + 1; i <= n; i++) { // dk + 1 是最小的 单位了
        if (a[i] < a[i - dk]) {
            a[0] = a[i];
            int j;
            for (j = i - dk; j > 0 && a[0] < a[j]; j -= dk) {
                a[j + dk] = a[j];
            }
            a[j + dk] = a[0];
        }
    }
}

void ShellSort(int a[]) {  // t 趟 希尔排序
    int k, t, dk[N];
    t = int(log(n + 1));// 书上给的
/*    cout << "t : " << t << "\n";*/
    for (int i = 1; i <= t; i++) {
        dk[i] = pow(2, t - i + 1) - 1;  // 书上给的
/*        cout << "dk" << i << ':' << dk[i] << "\n";*/
    }

    for (int i = 1; i <= t; i++) {
        ShellInsert(a, dk[i]);
    }
}

void BubbleSort(int a[]) {  // 冒泡排序
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n - i + 1; j++) {
            if (a[j - 1] > a[j]) {
                swap(a[j - 1], a[j]);
            }
        }
    }
}

void SelectSort(int a[]) {  // 简单选择排序
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[i] > a[j]) {
                swap(a[i], a[j]);
            }
        }
    }
}

void HeapAdjust(int a[], int s, int m) { // 筛法调整堆
    // 假设a[s + 1..m] 已经是堆， 将a[s..m] 调整为以a[s] 为根的大根堆
    int rc = a[s];
    for (int j = 2 * s; j <= m; j *= 2) { // 从2 * s 开始
        if (j < m && a[j] < a[j + 1]) // 注意 莫忘j < m
            j++;
        if (rc >= a[j])
            break;
        a[s] = a[j];
        s = j;
    }
    a[s] = rc;
}

void CreatHeap(int a[]) { // 建大根堆
    for (int i = n / 2; i > 0; i--) {
        HeapAdjust(a, i, n);
        //  序号大于 int (n / 2) 的节点都是叶子节点 注意 n / 2 - 1 不行  因为 n / 2 * 2 ?= n
    }
}

void HeapSort(int a[]) {
    CreatHeap(a);
    for (int i = n; i > 1; i--) {
        swap(a[1], a[i]);
        HeapAdjust(a, 1, i - 1);
    }
}

int TSelect(int c[], int s, int m) {
    if (m == 1)
        return c[1];
    for (int i = s; i <= m; i += 2) {
        c[i / 2] = min(c[i], c[i + 1]);
    }
    int d = m - s + 1;
    m = s - 1;
    s = m - d / 2 + 1;
}

void TSelectSort(int a[]) {
    // 因为实在不知道如何记录 value 对应的 key  我就用map写吧
    int c[N]; // 储存树
    map<int, int> ma; // 记录 value 对应key
    int k, nn = n;
    if (n % 2 == 1) {
        a[n + 1] = INF;
        nn++;
    }
    /*让第 n + 1 个数变成正无穷， 叶子节点为偶数个
     *如果 n 为 偶数， 那就不起作用
     * 如果n 为奇数， 起作用
     */
    k = nn / 2 + 1;

    for (int i = 1; i <= n; i++) {
        c[k] = a[i];
        ma[a[i]] = k++;
    }

    for (int i = 1; i <= n; i++) {
        a[i] = TSelect(c, nn / 2 + 1, nn);
        c[ma[a[i]]] = INF;
    }


}

int main() {

    printf("请输入你要排序的序列中的元素个数：\n");
    while (cin >> n) {
        if (n == 0)
            break;
        printf("请输入各元素：\n");
        for (int i = 1; i <= n; i++) {
            cin >> b[i];
        }
        for (int i = 1; i <= n; i++) {
            a[i] = b[i];   // 复制此数组， 以便于再次利用原数组
        }
        printf("请选择你要排序的方法的下标：\n"
            "1、直接插入排序；\n"
            "2、折半插入排序；\n"
            "3、希尔排序;\n"
            "4、冒泡排序\n"
            "5、简单选择排序\n"
            "6、堆排序\n");
        int o;
        cin >> o;
        switch (o) {
        case 1: InsertSort(a); break;
        case 2: BInsertSort(a); break;
        case 3: ShellSort(a); break;
        case 4: BubbleSort(a); break;
        case 5: SelectSort(a); break;
        case 6: HeapSort(a); break;
        }
        printf("排序后的结果为：\n");
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << "\n";
        printf("请输入你要排序的序列中的元素个数(结束请输入0)：\n");
    }

    return 0;
}
数据结构实验12 ：排序

实验12 ： 排序

要求：

实验12 ：排序
