/*
*
*/
#include<iostream>
using namespace std;

/// <summary>
/// 桶排序：利用数组下标对某个区间的整数进行排序
/// 用大写字母O来表示时间复杂度：O(M + N)
/// </summary>
/// <typeparam name="T">整数</typeparam>
/// <param name="in_array">输入参数：整数数组</param>
/// <param name="in_length">输入参数：数组元素个数</param>
/// <param name="out_array">输出参数：排序结果</param>
/// <returns>执行成功返回1，否则返回0</returns>
template<class T>
int sort_cast(T in_array[], int in_length, T out_array[]) {
    int max = in_array[0];
    int i, j;//控制循环的变量
    int t;//临时变量
    for (i = 1; i < in_length; i++)//找到待排序数组中的最大值，用来设置桶的数量
    {
        if (max < in_array[i])max = in_array[i];
    }

    int* cask = new int[max += 1];//桶
    /*桶的数量取决于待排序数中的最大值,可以准备更多的桶，这样会耗费更多的内存空间，所以应该设置合适，
     *因为桶数组下标从0开始，所以桶的数量是max+=1
     *数组元素的值是该下标代表的排序数出现的次数
    */

    for (i = 0; i < max; i++)//初始化桶
    {
        cask[i] = 0;
        //cout <<"init:: "<< cask[i] << endl;
    }

    for (i = 0; i < in_length; i++)
    {
        t = in_array[i];
        cask[t]++;//统计该下标代表的排序数出现的次数
        //cout << t << ":: " << cask[t] << endl;
    }
    t = 0;
    for (i = 0; i < max; i++)
    {
        for (j = 0; j < cask[i]; j++)
        {
            out_array[t++] = i;
            //cout << i << endl;
        }
    }
    delete cask;
    return 1;
}
/// <summary>
/// 冒泡排序
/// 时间复杂度O(N*N)
/// </summary>
/// <typeparam name="T">整数，小数</typeparam>
/// <param name="a">输入参数：待排序数组</param>
/// <param name="n">输入参数：数组元素个数</param>
/// <param name="flag">true 从大到小，false 从小到大</param>
/// <returns>执行成功返回1，否则返回0</returns>
template<class T>
int sort_bubble(T a[], int n, bool flag = true) {
    int i, j, t;
    //使用冒泡排序算法
    for (i = 0; i < n - 1; i++)//对n个数排序，只用进行n-1趟
    {
        for (j = 0; j < n - i - 1; j++) //从下标0的数开始进行比较，直到最后一个尚未归位的数
        {
            if (flag ? a[j] < a[j + 1] : a[j] >a[j + 1])
            {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
    return 1;
}
/// <summary>
/// 快速排序
/// 时间复杂度 最差O(N*N) 平均O(NlogN)
/// </summary>
/// <typeparam name="T">整数，小数</typeparam>
/// <param name="a">输入参数：待排序数组</param>
/// <param name="left">输入参数：起点下标</param>
/// <param name="right">输入参数：终点下标</param>
/// <returns>执行成功返回1，否则返回0</returns>
template<class T>
int sort_quick(T a[], int left, int right) {
    int i, j, t, temp;
    if (left > right)return 1;

    temp = a[left];//temp 中存放基准数
    i = left;
    j = right;
    while (i != j)
    {
        //顺序很重要，先从右向左找
        while (a[j] >= temp && i < j)
            j--;
        //再从左往右找
        while (a[i] <= temp && i < j)
            i++;
        //交换两个数在数组中的位置
        if (i < j)//两个哨兵还没有相遇
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    //最终，将基准数归位置
    a[left] = a[i];
    a[i] = temp;

    sort_quick(a, left, i - 1);
    sort_quick(a, i + 1, right);
    return 1;
}
//快速排序  
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        int i = l, j = r;
        int x = s[i];//保存左边第一个数，这样s[i]的位置就成了待填的坑，所以我们接下来从右侧开始找
        while (i < j)//如果i和j还没碰头，就继续
        {
            // 从右侧开始找，从右向左找第一个小于x的数填入s[i]的坑，填过后，s[j]就变成了新坑  
            while (i < j && s[j] >= x)
                j--;
            if (i < j)
                s[i++] = s[j];
            // 从左向右找第一个大于等于x的数 ，填入s[j]，s[i]则变为新坑
            while (i < j && s[i] < x)
                i++;
            if (i < j)
                s[j--] = s[i];
        }
        s[i] = x;//碰头后就把二分线放在s[i]
        quick_sort(s, l, i - 1); // 递归调用   处理左侧
        quick_sort(s, i + 1, r);// 递归调用   处理右侧
    }
}
int main() {
    const int n = 8;//表示待排序数字个数，
    int a[n] = { 9,5,6,2,1,4,3,5 };//待排序的数

    int i, j, t;
    //使用快速排序算法
    quick_sort(a, 0, n - 1);
    for (i = 0; i < n; i++)
    {
        cout << a[i] << endl;
    }
    //使用冒泡排序算法
    /*int flag = false;
    sort_bubble(a, n, flag);
    for (i = 0; i < n; i++)
    {
        cout << a[i] << endl;
    }*/
    //使用桶排序算法
    /*sort_cast(in_array, in_length, in_array);
    for (int i = 0; i < in_length; i++) {
        cout << in_array[i] << endl;
    }*/
    return 1;
}