#include <iostream>#include <map>#include <vector>//冒泡排序void buttle(int array[], int len){    int temp;    for(int i = 0; i < len; i++)    {        for(int j = 0; j < len-1 -i; j++)        {            if(array[j] > array[j+1])             {                temp = array[j];                array[j] = array[j+1];                array[j+1] = temp;            }        }    }}//简单选择排序void select(int array[], int len){    int min_index;    int temp;    for(int i = 0; i < len; i++)    {        min_index = i;        for(int j = i+1; j < len; j++)        {            if(array[j] < array[min_index])            {                min_index = j;            }        }        if(min_index != i)        {            temp = array[i];            array[i] = array[min_index];            array[min_index] = temp;        }    }}//直接插入排序void insert(int array[], int len){    int temp;    //从第二个元素开始    for(int i = 1; i < len; i++)    {        for(int j = i; j >= 1; j--)        {            if(array[j] < array[j-1])            {                temp = array[j];                array[j] = array[j-1];                array[j-1] = temp;            }        }    }}//希尔排序void shell(int array[],int len){    int increment = len/2;    int temp;     while(increment >= 1)        {        for(int i = increment; i < len; i++)            {                temp = array[i];            int j = i - increment;            while(j >= 0 && array[j] < temp)                {                    array[j+increment] = array[j];                    j = j - increment;                }            array[j+increment] = temp;             }        increment /= 2;       }}//希尔排序void shell2(int array[], int len) {    int increment = len/2;    int temp;    while(increment >= 1) {        std::cout<<"increment:"<<increment<<std::endl;        for(int i = 0; i < len - increment; i++) {            for(int j = i; j < len - increment; j=j+increment)            {                if(array[j] > array[j+increment]) {                    temp = array[j];                    array[j] = array[j+increment];                    array[j+increment] = temp;                }            }        }        increment /= 2;    }}//计数排序void count(int array[], int len){    std::map<int, std::vector<int> > m;    for(int i = 0; i < len; i++)    {        int num = array[i];        if(m.find(num) != m.end())         {            m[num].push_back(num);        } else         {            std::vector<int> vect;            vect.push_back(num);            m[num] = vect;        }    }    std::map<int, std::vector<int> >::iterator it = m.begin();    int index = 0;    while(it != m.end())    {        for(int i = 0; i < it->second.size(); i++)        {            array[index] = it->second[i];            index++;        }        it++;    }}//堆排序——构建二叉堆void build_tree1(int array[], int index, int num)    //i表示中间节点在原数组中的索引，num表示需要参与建堆的节点个数{    int i;    int left_child_index = 2*index+1;    int right_child_index = 2*index+2;    //有左孩子    if(left_child_index < num)     {        if(array[left_child_index] > array[index])        {            int temp = array[index];            array[index] = array[left_child_index];            array[left_child_index] = temp;            build_tree1(array, left_child_index, num);        }    }    //有右孩子    if(right_child_index < num)     {        if(array[right_child_index] > array[index])        {            int temp = array[index];            array[index] = array[right_child_index];            array[right_child_index] = temp;            build_tree1(array, right_child_index, num);        }    }    return;}//堆排序——构建二叉堆void build_tree2(int array[], int index, int num)    //i表示中间节点在原数组中的索引，num表示需要参与建堆的节点个数{    int i;    int left_child_index = 2*index+1;    int right_child_index = 2*index+2;    if(right_child_index < num)     //右孩子存在的话，左孩子必定存在    {        //同时有左右孩子        if(array[left_child_index] > array[index] || array[right_child_index] > array[index])        {            int bigger_child_index = left_child_index;            if(array[left_child_index] < array[right_child_index]) {                bigger_child_index = right_child_index;            }            int temp = array[index];            array[index] = array[bigger_child_index];            array[bigger_child_index] = temp;            build_tree2(array, bigger_child_index, num);        }            } else if (left_child_index < num)    {        //只有左孩子        if(array[left_child_index] > array[index])         {            int temp = array[index];            array[index] = array[left_child_index];            array[left_child_index] = temp;            build_tree2(array, left_child_index, num);        }    }    return;}//堆排序void heat(int array[], int len){    for(int i = len/2; i >= 0; i--)    {        build_tree2(array, i, len);    }    for(int i = len -1; i > 0; i--)    {        int temp = array[i];        array[i] = array[0];        array[0] = temp;        build_tree2(array, 0, i);    }}//归并排序void merge_join(int left_child_array[], int left_child_array_len, int right_child_array[], int right_child_array_len, int *temp){    int left_cur_index = 0;    int right_cur_index = 0;    int temp_cur_index = 0;    //如果两个子数组都有数据    while(left_cur_index < left_child_array_len && right_cur_index < right_child_array_len)    {        if(left_child_array[left_cur_index] <= right_child_array[right_cur_index])        {            temp[temp_cur_index] = left_child_array[left_cur_index];            left_cur_index++;            temp_cur_index++;        } else {            temp[temp_cur_index] = right_child_array[right_cur_index];            right_cur_index++;            temp_cur_index++;        }    }    //如果只有其中一个数组有数据，直接把该数组数据全部加到排序数组后面好了    while(left_cur_index < left_child_array_len)     {        temp[temp_cur_index] = left_child_array[left_cur_index];        left_cur_index++;        temp_cur_index++;    }    while(right_cur_index < right_child_array_len)     {        temp[temp_cur_index] = right_child_array[right_cur_index];        right_cur_index++;        temp_cur_index++;    }    std::cout<<"--------------\n";    for(int i = 0; i < left_child_array_len + right_child_array_len; i++)    {        std::cout<<"i:"<<temp[i]<<std::endl;        left_child_array[i] = temp[i];    }    std::cout<<"--------------\n";}//归并排序void begin_merge(int array[], int len, int *temp){    if(len > 1)    {        int left_child_array_len = len/2;        int right_child_array_len = len - left_child_array_len;        int *left_child_array = array;        int *right_child_array = array + left_child_array_len;        //拆分左子树        begin_merge(left_child_array, left_child_array_len, temp);        //拆分右子树        begin_merge(right_child_array, right_child_array_len, temp);        //归并排序        merge_join(left_child_array, left_child_array_len, right_child_array, right_child_array_len, temp);    }}//归并排序void merge(int array[], int len){    int *temp = (int*)malloc(len * sizeof(int));    begin_merge(array, len, temp);    /*     for(int i = 0; i < len; i++)    {        std::cout<<"i:"<<temp[i]<<std::endl;    }    */    //array = temp;}int sorted_pivot(int array[], int len){    int pivot_index = 0;    int pivot_num = array[pivot_index];    std::cout<<"pivot_num:"<<pivot_num<<std::endl;    int left_index = 0;    int right_index = len -1;    while(left_index < right_index)    {        while(1)        {            if(array[right_index] < pivot_num || left_index >= right_index)            {                break;            }            right_index--;            std::cout<<"right_index:"<<right_index<<std::endl;        }        while(1)        {            if(array[left_index] > pivot_num || left_index >= right_index)            {                break;            }            left_index++;            std::cout<<"left_index:"<<left_index<<std::endl;        }        //交换两个值        int temp = array[left_index];        array[left_index] = array[right_index];        array[right_index] = array[left_index];    }    //将基准数归位    array[pivot_index] = array[left_index];    array[left_index] = pivot_num;        return left_index;}//快速排序void quick1(int array[], int len){    if(len < 2)    {        return;    }    int pivot = sorted_pivot(array, len);    quick1(array, pivot+1);    quick1(array + pivot + 1 , len - pivot +1);}int main(){    int arr[25] = {5,2,3,4,1,8,9,0,7,6,10,19,15,13,17,18,14,12,11,16,30,35,310,315,335};    quick1(arr,25);    for(int i = 0; i < 25; i++)    {        std::cout<<arr[i]<<std::endl;    }}