#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

// 从左到右依次递增，打印数组
void PrintVector(vector<int> vec) {
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << ' ';
    }
}

// 冒泡排序，每次排序都会从后往前依次排好一位，稳定的排序算法
void BubbleSort(vector<int> &vec) {
    for (int i = 0; i < vec.size() - 1; i++) {
        for (int j = 0; j < vec.size() - i - 1; j++) {
            if (vec[j] > vec[j + 1]) {
                swap(vec[j], vec[j + 1]);
            }
        }
    }
}

// 选择排序，每次排序都会从左到右选择一个最小的数,不稳定的排序算法
void SelectSort(vector<int> &vec) {
    for (int i = 0; i < vec.size() - 1; i++) {
        int minindex = i;
        for (int j = i + 1; j < vec.size(); j++) {
            if (vec[minindex] > vec[j]) {
                minindex = j;
            }
        }
        if (minindex != i) {
            swap(vec[i], vec[minindex]);
        }

    }
}

// 直接插入排序，稳定的排序算法
void InsertSort(vector<int> &vec) {
    for (int i = 1; i < vec.size(); i++) {
        int minindex = i;
        int tmp = vec[i];
        for (int j = i - 1; j >= 0; j--) {
            if (vec[i] < vec[j]) {
                minindex = j;
            }
        }
        vec.erase(vec.begin() + i);
        vec.insert(vec.begin() + minindex, tmp);
    }
}

// 希尔插入
void ShellInsert(vector<int> &vec, int gap) {
    for (int i = 0; i < vec.size(); i += gap) {
        for (int j = i + gap; j < vec.size(); j += gap) {
            if (vec[i] > vec[j]) {
                swap(vec[i], vec[j]);
            }
        }
    }
}

// 希尔排序(缩小增量排序),不稳定的排序算法
void ShellSort(vector<int> &vec) {
    for (int gap = vec.size() / 2; gap >= 1; gap /= 2) {
        ShellInsert(vec, gap);
    }
}

// 计数排序
void CountSort(vector<int> &vec) {
    int maxx = *max_element(vec.begin(), vec.end());
    int *arr = new int[maxx + 1]; // 哈希表
    memset(arr, 0, sizeof(int) * (maxx + 1)); // 初始化数组，否则会有问题
    for (int i = 0; i < vec.size(); i++) {
        arr[vec[i]]++;
    }
    vec.clear();
    for (int i = 0; i <= maxx; i++) {
        while (arr[i]) {
            vec.push_back(i);
            arr[i]--;
        }
    }
    delete[] arr;
}

// 桶排序
void BucketSort(vector<int> &vec) {
    int maxx = *max_element(vec.begin(), vec.end());
    int minn = *min_element(vec.begin(), vec.end());
    int bucket_num = (maxx - minn) / vec.size() + 1; // 桶数量
    vector<vector<int>> bucket(bucket_num);
    for (int i = 0; i < vec.size(); i++) {
        bucket[(vec[i] - minn) / vec.size()].push_back(vec[i]); // 确定往哪个桶放入该元素，注意不要越界
    }
    for (int j = 0; j < bucket.size(); j++) {
        sort(bucket[j].begin(), bucket[j].end()); // 选择最快的排序算法
    }
    vec.clear();
    for (int i = 0; i < bucket.size(); i++) {
        for (int j = 0; j < bucket[i].size(); j++) {
            vec.push_back(bucket[i][j]);
        }
    }
}

// 建立大根堆
void Build_Max_Heap(vector<int> &vec, int start, int end) {
    int cur = start;
    int l = cur * 2 + 1;
    for (; l <= end; cur = l, l = cur * 2 + 1) {
        if (l < end && vec[l] < vec[l + 1]) l++; // 左右最大孩子
        if (vec[l] > vec[cur])  swap(vec[l], vec[cur]);
        else break;
    }
}

// 堆排序，不稳定的排序算法
void HeapSort(vector<int> &vec) {
    for (int i = vec.size() / 2 - 1; i >= 0; i--) {
        Build_Max_Heap(vec, i, vec.size() - 1); // 完成第一次建堆
    }
    // 完成所有位置大根堆的排序
    for (int i = 0; i < vec.size() - 1; i++) {
        swap(vec[0], vec[vec.size() - i - 1]);
        Build_Max_Heap(vec, 0, vec.size() - i - 2);
    }
}

// 快速排序，递归分治，每次循环排好一个基准位
void QuickSort(vector<int> &vec, int l, int r) {
    if (l >= r) return;
    int tmp = vec[l]; // 基准位
    int i = l, j = r;
    while (i < j) {
        while (i < j && tmp < vec[j])   j--;
        if (i < j && tmp > vec[j])  vec[i++] = vec[j];
        while (i < j && vec[i] < tmp)   i++;
        if (i < j && vec[i] > tmp)  vec[j--] = vec[i];
    }
    vec[i] = tmp; // 该次基准已经排序完成
    QuickSort(vec, l, i - 1);
    QuickSort(vec, i + 1, r);
}

void MergeSort(vector<int> &vec, int l, int mid, int r) {
    int *tmp = new int[r - l + 1];
    int i = l, j = mid + 1, index = 0;
    while (i <= mid && j <= r) {
        if (vec[i] <= vec[j]) {
            tmp[index++] = vec[i++];
        } else {
            tmp[index++] = vec[j++];
        }
    }
    while (i <= mid)    tmp[index++] = vec[i++];
    while (j <= r)      tmp[index++] = vec[j++];
    for (i = 0; i < index; i++) {
        vec[l + i] = tmp[i];
    }
    delete[] tmp;
}

// 归并排序，每次向下分成两组，从下到上依次将每组排序并存放在新建数组中，稳定的排序算法
void MergeLoop(vector<int> &vec, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    MergeLoop(vec, l, mid);
    MergeLoop(vec, mid + 1, r);
    MergeSort(vec, l, mid, r);
}
int main() {
    vector<int> vec = { 2, 4, 3, 6, 5, 0, 7, 9, 1};
//    BubbleSort(vec); // 冒泡排序 时间复杂度O(n²)
//    SelectSort(vec); // 选择排序 时间复杂度O(n²)
//    InsertSort(vec); // 直接插入排序 时间复杂度O(n²)
//    ShellSort(vec); // 希尔排序 时间复杂度O(n1.5)
//    CountSort(vec); // 计数排序
//    BucketSort(vec); // 桶排序
//    HeapSort(vec); // 堆排序 时间复杂度O(n*logn)
//    QuickSort(vec, 0, vec.size() - 1); // 快速排序 时间复杂度O(n*logn)
    MergeLoop(vec, 0, vec.size() - 1); // 归并排序 时间复杂度O(n*logn)
    PrintVector(vec);
    return 0;
}