#数据结构 对规则整型数据进行快速排序和堆排序

下列对快速排序和堆排序，随机生成如下规则的5组整形数据：
l 随机数据
l 单调增加
l 单调降低
l 近似单调增加
l 近似单调降低
（生成近似单调的数据可以采用如下方法：先生成单调的数据，然后在随机调整一定次数，每次调整时交换两个附近的元素；或者生成时从第一个数据0开始，后面一个数据在上一个数据的基础之上增加[-b, a]之内的随机值，这里0<b<a，这样控制a和b就能生成近似有序的测试数据）
对每组种数据，数据规模100个以上数据。分别用快速排序、堆排序进行排序（结果单调增），并用变量统计算法的比较和移动次数。
（比较次数和移动次数用额外变量存储，比如用全局变量cmp_cnt和move_cnt代表比较和移动次数，在算法中，遇到比较时用cmp_cnt++，有元素移动则用move_cnt++，最后打印cmp_cnt和move_cnt的值即可）

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

const int N = 100;
int cmp_cnt, move_cnt;

void quick_sort(int arr[], int left, int right) {
    if (left >= right) return;
    int i = left - 1, j = right + 1, pivot = arr[(left + right) >> 1];
    while (i < j) {
        do i++, cmp_cnt++; while (arr[i] < pivot);
        do j--, cmp_cnt++; while (arr[j] > pivot);
        if (i < j) {
            swap(arr[i], arr[j]);
            move_cnt += 2;
        }
    }
    quick_sort(arr, left, j), quick_sort(arr, j + 1, right);
}

void down(int arr[], int u, int size) {
    int t = u;
    if (u * 2 <= size && arr[u * 2] > arr[t]) t = u * 2, cmp_cnt++;
    if (u * 2 + 1 <= size && arr[u * 2 + 1] > arr[t]) t = u * 2 + 1, cmp_cnt++;
    if (u != t) {
        swap(arr[u], arr[t]);
        move_cnt += 2;
        down(arr, t, size);
    }
}

void heap_sort(int arr[], int size) {
    for (int i = size / 2; i; i--) down(arr, i, size);
    for (int i = size; i > 1; i--) {
        swap(arr[1], arr[i]);
        move_cnt += 2;
        down(arr, 1, i - 1);
    }
}

int main() {
    srand(time(0));
    int a[N + 1], b[N + 1];
    for (int k = 0; k < 5; k++) {
        if (k == 0) {
            for (int i = 1; i <= N; i++) a[i] = rand() % N;
        } else if (k == 1) {
            for (int i = 1; i <= N; i++) a[i] = i;
        } else if (k == 2) {
            for (int i = N; i >= 1; i--) a[i] = N - i + 1;
        } else if (k == 3 || k ==4) {
            a[1] = rand() % N;
            for (int i = 2; i <= N; i++) a[i] = a[i - 1] + rand() % N - N / 2;
            for (int t = rand() % N / 10; t >=0 ; t--) swap(a[rand() % N + 1], a[rand() % N + 1]);
            if(k==4) reverse(a+1,a+N+1);
        }

        for (int i = 1; i <= N; i++) b[i] = a[i];
        cmp_cnt = move_cnt =0;
        quick_sort(b, 1, N);
        cout << "quick sort: " << cmp_cnt << ' ' << move_cnt << endl;

        for (int i = 1; i <= N; i++) b[i] = a[i];
        cmp_cnt = move_cnt =0;
        heap_sort(b, N);
        cout << "heap sort: " << cmp_cnt << ' ' << move_cnt << endl;

        cout << endl;
    }

    return 0;
}