//冒泡排序
void bubble_sort(int* a, int len){
    //n-1次
    for (int i = 0; i < len - 1; i++){
        //比较相邻两个，大的后挪
        for (int j = 0; j < len - i - 1; j++){
            if (a[j] > a[j + 1]){//比较相邻两个  不满足要求
                //交换
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }

        //travel(a, len);
    }
}


//选择排序
void select_sort(int* a, int len)
{
    int temp;
    size_t minIdx;
    for (int i = 0; i < len - 1; i++)
    {//选 len -1 次
        temp = a[i];//备份 a[i] 位置 的数据
        minIdx = i;//假设 a[i]最小
        //找出   i 到 len-1  范围内最小数据 记录其下标
        for (int j = i; j < len; j++)
            minIdx = ((a[j] < a[minIdx]) ? j : minIdx);
        //最小的  放到  a[i] 位置
        if (a[minIdx] < temp)
        {
            a[i] = a[minIdx];
            a[minIdx] = temp;
        }

        //travel(a, len);
    }
}

//插入排序
void insert_sort(int* a, int len)
{
    int temp;
    int insertIdx;
    //插入次数 n-1 次 
    for (int i = 1; i < len; i++)
    {//每次把下标为i元素插入到已序数组中
        //临时存储 待插数据
        temp = a[i];
        //从 i-1位置开始往前找插入位置


        for (insertIdx = i - 1; insertIdx >= 0 && a[insertIdx] > temp; insertIdx--)
        {
            a[insertIdx + 1] = a[insertIdx];
        }

        //找到后  插入
        a[insertIdx + 1] = temp;
        //travel(a, len);
    }


}

#include <stdio.h>
/*
基数排序
    a:数组
    len:元素个数
    max：最大元素值
*/
void radix_sort(int* a,int len,int max);

int main(){
    int arr[10] = { 0, 9, 5, 7, 8, 6, 3, 4, 2, 1 };

    radix_sort(arr, 10,9);

    for (int i = 0; i < 10; i++)
        printf("%d ", arr[i]);
    printf("\n");

    while (1);
    return 0;
}

/*
基数排序
a:数组
len:元素个数
max：最大元素值
*/
void radix_sort(int* a, int len, int max){
    //定义一个临时数组
    int* pTemp = new int[max + 1];

    for (int i = 0; i < max + 1; i++)
        pTemp[i] = -1;

    //把a数组中元素依序存入pTemp数组中
    for (int i = 0; i < len; i++)
        pTemp[a[i]] = a[i];

    //把pTemp数组覆盖回来
    int k = 0;
    for (int i = 0; i < max + 1; i++){
        if (pTemp[i] != -1)
            a[k++] = pTemp[i];
    }
    //释放
    delete[] pTemp;
}

#include <iostream>
using namespace std;
//元素个数
#define NUM  10
//数据范围
#define AREA 1000
//箱子个数
#define SIZE  10

void init(int* a);
void travel(int* a, int len, bool isAfter=false);
//箱排序
void bucket_sort(int* a, int len);
int main(){
    int arr[NUM];
    init(arr);

    travel(arr,NUM);

    bucket_sort(arr, NUM);

    travel(arr, NUM,true);
    while (1);
}

//箱排序
void bucket_sort(int* a, int len){
    int count;//用来做循环次数的循环变量
    //做箱子
    int* pTemp = new int[SIZE * len];
    int k;
    /*
        int pTemp[SIZE][len];
        pTemp[a[i] /count%10][i]
    */
    for (count = 1; count < AREA; count *= 10){
        //1 初始化10个箱子
        for (int i = 0; i < SIZE * len; i++){
            pTemp[i] = -1;
        }
        //2 根据当前位把a数组中元素放到箱子里
        //  看对应十进制为    a[i] /count%10
        for (int i = 0; i < len; i++){
            //pTemp[a[i] /count%10][i]

            pTemp[(a[i] / count % 10)*len + i] = a[i];
        }

        //3 覆盖回来
        k = 0;
        for (int i = 0; i < SIZE * len; i++){
            if (-1 != pTemp[i]){
                a[k++] = pTemp[i];
            }
        }

        travel(a, NUM);
    }
    delete[] pTemp;
}


void init(int* a){
    for (int i = 0; i < NUM; i++)
        a[i] = rand() % AREA;
}
void travel(int* a, int len, bool isAfter){
    if (isAfter){
        cout << "after  sort:";
    }
    else{
        cout << "before sort:";
    }

    for (int i = 0; i < len; i++)
        cout << a[i] << " ";

    cout << endl;
}

/*
循环方式实现二分查找
从arr数组中找值为findData的元素
找到返回其下标 找不到返回-1
len为数组元素个数
*/
int halfFind(int* arr, int len, const int& findData){
    int m;                //中间的下标
    int left=0;            //左边下标
    int right=len-1;    //右边下标
    while (1){
        //把中间下标算出来
        m = left + (right - left) / 2;
        if (findData == arr[m]){//判断是否找到了  
            return m;//找到了 返回
        }
        else{
            //没找到  修改left和right的值  继续循环
            if (findData > arr[m]){//要找数据比中间数据大 
                left = m + 1;//排除掉左边
            }
            else{//要找数据比中间数据小 
                right = m - 1;//排除掉右边
            }
        }
        if (left > right) break;//找不到 防止死循环
    }
    return -1;
}

/*
递归方式实现二分查找
从arr数组中找值为findData的元素
找到返回其下标 找不到返回-1
len为数组元素个数
*/
int half_find(int* arr, int len, const int& findData){
    return Half_Find(arr, 0, len - 1, findData);
}
//用于递归的函数
int Half_Find(int* arr, int left, int right, const int& findData){
    if (left > right) 
        return -1;
    int m = left + (right - left) / 2;
    if (findData == arr[m])
    {//判断是否找到了  
        return m;//找到了 返回
    }
    //没找到  修改left和right的值  继续循环
    if (findData > arr[m])
    {//要找数据比中间数据大 
        return Half_Find(arr, m + 1, right, findData);
    }
    else
    {//要找数据比中间数据小 
        return Half_Find(arr, left, m - 1, findData);
    }
}

#include <iostream>
using namespace std;

#define NUM 18
void travel(int* a, int len, bool isAfter = false);

/*
    left  - mid   左边的
    mid+1 - right 右边的
*/
void MergeSort(int* a, int left, int mid, int right);

//归并排序
void merge_sort(int* a, int left, int right);
//常规写法归并排序
void mergeSort(int* a, int len);

int main(){
#if 1    
    int arr[NUM] = { 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64,
        33, 83, 27, 95, 2, 88 };
#else
    int arr[NUM] = {    23, 26, 31, 41, 53, 58, 59, 93, 97, 
        2, 27, 33, 62, 64, 83, 84, 88, 95 };
#endif
    
    travel(arr, NUM, true);

    //MergeSort(arr, 0, 0 + (NUM - 1 - 0) / 2, NUM - 1);
    //MergeSort(arr, 0, 8, 17);

    //merge_sort(arr, 0, 17);
    mergeSort(arr, NUM);
    travel(arr, NUM, true);

    

    while (1);
    return 0;
}

void travel(int* a, int len, bool isAfter){
    if (isAfter){
        cout << "after  sort:";
    }
    else{
        cout << "before sort:";
    }

    for (int i = 0; i < len; i++)
        cout << a[i] << " ";

    cout << endl;
}


/*
left  - mid   左边的
mid+1 - right 右边的
*/
void MergeSort(int* a, int left, int mid, int right){
    int L = left;
    int R = mid + 1;
    int k = 0;//作为pTemp的下标
    //1 申请临时内存空间
    int* pTemp = new int[right - left + 1];
    //2 一边比较一边把数据从a放到pTemp中
    while (L<=mid && R<=right){
        if (a[L] < a[R])    pTemp[k++] = a[L++];
        else                pTemp[k++] = a[R++];
    }
    //3 把剩下的一半放入pTemp中
#if 0
    while (L <= mid){ pTemp[k++] = a[L++]; }
    while (R <= right){ pTemp[k++] = a[R++]; }
#else
    
    if (L <= mid){
        memcpy(pTemp + k, a + L, sizeof(int)*(mid-L+1));
    }
    else{
        memcpy(pTemp + k, a + R, sizeof(int)*(right-R+1));
    }
#endif
    //4 pTemp中数据覆盖回 a
#if 0
    int j = 0;
    for (int i = left; i <= right; i++){
        a[i] = pTemp[j++];
    }
#else
    memcpy(a + left, pTemp, sizeof(int)*(right - left + 1));
#endif
    //5 释放
    delete[] pTemp;
}

//归并排序
void merge_sort(int* a, int left, int right){
    if (left < right){
        int m = left + (right - left) / 2;
        //拆
        merge_sort(a, left, m);        //左边
        merge_sort(a, m + 1, right);//右边
        //合
        MergeSort(a, left, m, right);
        //travel(a+left, right-left+1);
    }
}
//常规写法归并排序
void mergeSort(int* a, int len){
    merge_sort(a, 0, len - 1);
}

#include <iostream>
using namespace std;
#define NUM 18
void travel(int* a, int len, bool isAfter = false);

//分组排序
void quick_sort(int* a, int left, int right);

int main(){
    int arr[NUM] = { 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64,
        33, 83, 27, 95, 2, 88 };
    travel(arr, NUM, true);

    quick_sort(arr, 0, 17);

    travel(arr, NUM, true);
    while (1);
    return 0;
}
void travel(int* a, int len, bool isAfter){
    if (isAfter){
        cout << "after  sort:";
    }
    else{
        cout << "before sort:";
    }

    for (int i = 0; i < len; i++)
        cout << a[i] << " ";

    cout << endl;
}

//分组排序
void quick_sort(int* a, int left, int right){
    if (left >= right) return;

    //假设a[left]是中间数据
    int temp = a[left];
    int L = left;    //用来移动的左下标
    int R = right;  //用来移动的右下标

    //循环让L和R并拢
    while (L < R){
        //先挪R
        while (L<R && a[R] > temp) R--;
        a[L] = a[R];
        //再挪L
        while (L < R && a[L] < temp) L++;
        a[R] = a[L];
    }
    a[L] = temp;

    travel(a, NUM);

    //继续拆
    quick_sort(a, left, L - 1);//左边
    quick_sort(a, L+1, right);//右边
}