#include<iostream>
#include<vector>
using namespace std;
//void swap(int &a, int &b);
void printnum(vector<int>& num) {
    for (auto i:num)
        cout << i << " ";

    cout << endl;
}

/*****************************************冒泡排序*********************************/
//冒泡排序-每一轮确定最小的元素
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
void bubblesort(vector<int>&num) {
    int length = num.size();
    for (int i = 0; i < length-1; i++) {
        int index = i;
        for (int j = index+1; j < length; j++) {
            if (num[index] > num[j]) {
                swap(num[index], num[j]);
            }

        }
    }
}
//冒泡排序-每一轮确定最大元素
void bubblesort1(vector<int>& num) {
    int length = num.size();
    for (int i = 0; i < length-1; i++) {

        for (int j = 0; j < length-1-i; j++) {
            if (num[j] > num[j+1]) {
                swap(num[j], num[j+1]);
            }

        }
    }
}
//冒泡排序，如果某次排序中未存在交换元素，则说明有序
void bubblesort2(vector<int>& num) {
    int length = num.size();
    bool iswap=true;
    for (int i = 0; i < length - 1; i++) {
        if (!iswap)
            break;
        for (int j = 0; j < length - 1 - i; j++) {
            if (num[j] > num[j + 1]) {
                swap(num[j], num[j + 1]);
                iswap = true;
            }
            else {
                iswap = false;
            }
        }
    }
}
/*****************************************end*********************************/

/*****************************************选择排序*********************************/
//选择排序，将元素与第一位元素比较，找出最大或最小元素，记录其下标，交换位置，完成一次排序。
void selectsort(vector<int>& num) {
    int length = num.size();
    for (int i = 0; i < length; i++) {
        int min = i;
        for (int j = i+1; j < length; j++) {
            if (num[min] > num[j]) {
                min = j;
            }
        }
        swap(num[i], num[min]);        
    }
}
/*****************************************end*********************************/
/*****************************************插入排序*********************************/
//插入排序,在一个已经有序的元素序列中，一次插入一个元素。
void insertsort(vector<int>& num) {
    int length = num.size();
    for (int i = 1; i < length; i++) {
        if (num[i] <  num[i - 1]) {
            int x = num[i];//设置哨兵
            int j = i - 1;
            while (j >= 0 && num[j] > x) {
                //将元素往后移位
                num[j+1] = num[j];
                j--;
            }
            //因为j--了，所以要+1.
            num[j+1] = x;        
        }    
    }
}
//错误的，为体现插入排序的思想。存在了交换
void insertsort2(vector<int>& num) {
    int n = num.size();
    for (int i = 1; i < n; i++) {
        if (num[i] < num[i - 1]) {
            int x = i;
            int j = i-1;
            while (j >= 0 && num[j] > num[x]) {
                //采用交换的方式，但要注意交换后元素的下标变化
                swap(num[j], num[x]);
                x = j;
                j--;
            }
        }    
    }
}
/*****************************************end*********************************/

/*****************************************快速排序*********************************/
//递归方法-hoare法
void quicksort(vector<int>& num,int low,int high) {
    if (low >= high) {
        return;
    }
    int first = low;
    int last = high;
    int key = low;
    while (first < last) {
        //从后往前找第一个比key小的元素
        while (first<last && num[last]>=num[key]) {
            last--;        
        }
        //从前往后找第一个比key大的元素
        while (first < last && num[first] <= num[key]) {
            first++;    
        }
        //交换两个元素
        swap(num[last], num[first]);
    }
    //当first=last时，说明此位置就是key的正确位置
    swap(num[key], num[first]);
    key = first;
    //
    quicksort(num, low, key - 1);
    quicksort(num, key + 1, high);
}
//挖坑法
void quicksort2(vector<int>& num, int low, int high) {

    //结束递归的条件
    if (low >= high) {
        return;
    }
    int first = low;
    int last = high;
    int key = num[low];
    while (first < last) {
        //从后往前找比key小的元素
        while (first<last && num[last]>=key) {
            last--;
        }
        num[first] = num[last];
        while (first < last && num[first] <= key) {
            first++;
        }
        num[last] = num[first];
    }
    num[last] = key;

    quicksort2(num, low, first - 1);
    quicksort2(num, first + 1, high);

}
/*****************************************end*********************************/

/*****************************************希尔排序*********************************/
//每一趟以一组为单位,将每个分组都变得有序
void shellsort1(vector<int>& num) {
    int len = num.size();
    //外层循环，确定分组个数，并逐渐减少分组
    for (int gap = len / 2; gap > 0; gap /= 2) {
        //遍历每个分组
        for (int i = 0; i < gap; i++) {
            //每个分组内进行插入排序
            for (int j = i + gap; j < len; j += gap) {
                int k = j - gap;
                int temp = num[j];
                if (num[j] < num[j - gap]) {    
                    while (k >= 0 && num[k] > temp) {
                        num[k + gap] = num[k];
                        k -= gap;
                    }
                }
                num[k + gap] = temp;

            }
        }

    }
}
//网上实例代码--每一趟排序所有分组中的一小部分元素
void shellSort(std::vector<int>& arr) {
    int n = arr.size();

    // 开始间隔的大小
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个间隔gap进行插入排序,-----不明白
        for (int i = gap; i < n; ++i) {
            //插入排序
            int temp = arr[i];
            int j;
            // 将arr[i]插入到已经排序的子数组中
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}
/*****************************************end*********************************/
/*****************************************归并排序*********************************/
void mergesort(vector<int>& num,vector<int>& numtemp,int low,int high) {
    if (low >= high) {
        return;
    }
    //分组
    int left = low;
    int right = high;
    int mid = (left + right) / 2;
    int start1 = left;
    int end1 = mid;
    int start2 = mid + 1;
    int end2 = right;
    mergesort(num, numtemp,start1, end1);
    mergesort(num, numtemp,start2, end2);
    //合并
    int index = low;
    //当两个半区都有元素时
    while (start1 <= end1 && start2 <= end2) {
        numtemp[index++] = num[start1] < num[start2] ? num[start1++] : num[start2++];
    }
    //当左半区没有元素时
    while (start2 <= end2) {
        numtemp[index++] = num[start2++];
    }
    while (start1 <= end1) {
        numtemp[index++] = num[start1++];
    }
    //将合并后的数组复制到原数组
    while (left <= right) {
        num[left] = numtemp[left];
        left++;
    }    
}
void mergeSort2(vector<int>& num, int left, int right) {
    //终止条件
    if (left >= right) {
        return;
    }
    //先分组
    int low = left;
    int high = right;
    int mid = (low + high) / 2;
    mergeSort2(num, low, mid);
    mergeSort2(num, mid + 1, high);
    //再合并
    int start1 = low, end1 = mid, start2 = mid + 1, end2 = high;
    //创建一个临时数组
    int len = high - low+1;
    //临时数组的首元素
    int key = 0;
    vector<int>*temp = new vector<int>(len);
    //将两个半区的数组合成一个数组,将结果放到临时数组里面
    //两个半区都有元素时
    while (start1 <= end1 && start2 <= end2) {
        (*temp)[key++] = num[start1] < num[start2] ? num[start1++] : num[start2++];
    }
    while (start1 <= end1) {
        (*temp)[key++] = num[start1++];
    }
    while (start2 <= end2) {
        (*temp)[key++] = num[start2++];
    }
    //将临时数组赋值到原数组中
    for (int i = 0; i < (*temp).size(); i++) {
        num[i+left] = (*temp)[i];
    }
    delete temp;
}
/*****************************************end*********************************/
/*****************************************堆排序*********************************/
//num-待维护的数组,n-数组的长度,i-待维护的节点
void headity(vector<int>& num, int n, int i) {
    int node = i;
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    if (right<n && num[right]>num[node]) {
        node = right;
    }
    if (left<n && num[left]>num[node]) {
        node = left;
    }
    if (node != i) {
        swap(num[node], num[i]);
        headity(num, n, node);
    }
}
void headsort(vector<int>& num) {
    //建堆,找到第一个非叶子节点
    int len = num.size();
    int i;
    for (i = len / 2 - 1; i >= 0; i--) {
        headity(num, len, i);
    }
    //排序
    for (int j = len-1; j >= 0; j--) {
        swap(num[j], num[0]);
        headity(num, j, 0);
    }
}
/*****************************************end*********************************/
/*****************************************计数排序*********************************/
void countsort(vector<int>& num) {
    //计数数组
    //1找到待排序数组中的最大值,创建计数数组大小为最大值+1；
    int len = num.size();
    int max=num[0];
    for (int i = 1; i < len; i++) {
        if (max < num[i]) {
            max = num[i];
        }
    }
    vector<int>countnum(max + 1,0);
    for (int j = 0; j < len; j++) {
        countnum[num[j]]++;
    }
    //累积数组
    for (int k = 1; k < max+1; k++) {
        countnum[k] += countnum[k - 1];
    }
    vector<int>result(len, 0);
    for (int l = 0; l < len; l++) { 
        result[countnum[num[l]] - 1] = num[l];
        countnum[num[l]]--;
    }
    //将结果复制到原数组中
    num = result;
}
/*****************************************end*********************************/
int main() {
    vector<int>my_num = {8,9,1,4,2,3,6,7,5,5};
    ////冒泡排序
    //bubblesort(my_num);
    ////选择排序
    //selectsort(my_num);
    //插入排序
    /*insertsort(my_num);*/
    //快速排序
    /*quicksort(my_num, 0, my_num.size()-1);*/
    //希尔排序
    /*shellsort(my_num);*/
    /*shellsort1(my_num);*/
    //归并排序
    //vector<int>num(my_num);
    //mergesort(my_num, num, 0, my_num.size() - 1);
    /*mergeSort2(my_num, 0, my_num.size() - 1);*/
    /*headsort(my_num);*/
    countsort(my_num);
    printnum(my_num);
    return 0;
}