根号N段合并排序

• 问题：

将数组a[0,n-1]划分为 根号N向下取整 个子数组，每个子数组有 O(根号N)个元素。然后递归地对分割后的子数组进行排序，最后将所得到的 根号N向下取整 个排好序的子数组合并排序。

• 思路：
  类似于归并排序，不过子问题数由 2 变为 根号N向下取整个，递归的结束条件由p==q变为根号子问题规模 <=1（即，子问题规模为1、2或者3），还需要注意的是：若根号子问题规模==1则对子问题内的序列进行排序

• 实现代码（C++）：

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

void sort_2_3(int* arr, int p, int q){
    int num = q - p + 1;
    if(num == 2){
        cout<<"sort_2_3 2:"<<arr[p]<<","<<arr[p+1]<<endl;
        if(arr[p] > arr[p+1]){
            int tmp = arr[p];
            arr[p] = arr[p+1];
            arr[p+1] = tmp;
        }
        cout<<"sort_2_3 2:"<<arr[p]<<","<<arr[p+1]<<endl;
    }
    else if(num == 3){
        cout<<"sort_2_3 3:"<<arr[p]<<","<<arr[p+1]<<","<<arr[p+2]<<endl;
        int Min = arr[p];
        int Max = arr[p];
        int min_i = 0;
        int max_i = 0;
        for(int index=0; index<3; index++){
            if(arr[p + index] < Min){
                Min = arr[p + index];
                min_i = index;
            }else if(arr[p + index] > Max){
                Max = arr[p + index];
                max_i = index;
            }
        }
        int Mid = arr[ p + 3 - min_i - max_i ];
        arr[p] = Min;
        arr[p + 1] = Mid;
        arr[p + 2] = Max;
        cout<<"sort_2_3 3:"<<arr[p]<<","<<arr[p+1]<<","<<arr[p+2]<<endl;
    }
    else{
        //cout<<num<<endl;
    }
}

void Merge(int*arr, int p, int q){
    cout<<"merge:"<<p<<","<<q<<endl;
    for(int i=p;i<=q;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    int n = q - p + 1;
    int num = int(sqrt(n));
    //开辟暂存空间
    int i=0;
    vector<vector<int> > tmps (num);
    for(; i< num- 1; i++){
        tmps[i].resize(num + 1);
    }
    tmps[i].resize(n - i*num + 1);

    //初始化数据
    for(i=0; i < num - 1; i++){
        int j=0;
        for(; j < num; j++){
            tmps[i][j] = arr[p + i*num + j];
        }
        tmps[i][j] = INT_MAX;
    }
    int in = 0;
    for(; in < n - i * num; in++)
        tmps[i][in] = arr[p + i*num + in];
    tmps[i][in] = INT_MAX;

    cout<<"初始化数据："<<endl;
    for(int i=0; i<num;i++){
        for(int j=0;j<tmps[i].size();j++){
            cout<<tmps[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"初始化数据."<<endl;

    //每行标记
    int poses[num];
    for(int i=0; i<num ;i++){
        poses[i]=0;
    }
    //比较
    int Min = tmps[0][0];
    int index_row = 0;
    for(i=p; i<=q; i++){
        for(int j=0; j<num; j++){
            if(tmps[j][poses[j]] < Min){
                Min = tmps[j][poses[j]];
                index_row = j;
            }
        }
        arr[i] = tmps[index_row][poses[index_row]];
        Min = tmps[index_row][poses[index_row] + 1];
        poses[index_row]++;
    }
    for(int i=p;i<=q;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

void sqrt_n_sort(int* arr, int p, int q){
    cout<<"deviation"<<endl;
    int n = q -p + 1;
    int num = int(sqrt(n));
    if(num > 1){
        int i=0;
        for(;i < num -1 ; i++){
            cout<<p + num*i<<","<<p + num*(i+1) - 1<<endl;
            sqrt_n_sort(arr, p + num*i, p + num*(i+1) - 1 );
            //sort_2_3(arr, p + num*i, p + num*(i+1) - 1);
        }
        cout<<p + num*i<<","<<q<<endl;
        sqrt_n_sort(arr, p + num*i, q);
        //sort_2_3(arr, p + num*i, q);
        Merge(arr, p, q);
    }else{
        sort_2_3(arr,p,q);
    }
}

int main()
{
    int arr[17] = {3,9,11,25,18,21,19,7,6,19,22,15,19,24,2,1,16};
    sqrt_n_sort(&arr[0], 0, 16);

    //cout<<"begin:"<<endl;
    for(int i=0; i<17; i++){
        cout<<arr[i]<<" "<<endl;
    }
    return 0;
}

• 补充问题：

用分治法设计一个算法，在数组A中寻找最大元素和最小元素

• 思路：
  与上题类似，不过更加简单，不需要merge过程，把sort_2_3()函数功能从对规模为2、3的子问题进行排序，改为求对规模为2、3的子问题的最大、最小值

• 实现（C++）：

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

void sort_2_3(int* arr, int p, int q, int* arr_min_max){
    int num = q - p + 1;
    int len = 0;
    if(num == 2){
        len = 2;
    }else if(num == 3){
        len = 3;
    }
    for(int i=p; i < p + len; i++){
        if(arr[i] < arr_min_max[0]){
            arr_min_max[0] = arr[i];
        }
        if(arr[i] > arr_min_max[1]){
            arr_min_max[1] = arr[i];
        }
    }
}

void sqrt_n_sort(int* arr, int p, int q, int* arr_min_max){
    cout<<"deviation"<<endl;
    int n = q -p + 1;
    int num = int(sqrt(n));
    if(num > 1){
        int i=0;
        for(;i < num -1 ; i++){
            cout<<p + num*i<<","<<p + num*(i+1) - 1<<endl;
            sqrt_n_sort(arr, p + num*i, p + num*(i+1) - 1, arr_min_max);
            //sort_2_3(arr, p + num*i, p + num*(i+1) - 1);
        }
        cout<<p + num*i<<","<<q<<endl;
        sqrt_n_sort(arr, p + num*i, q, arr_min_max);
        //sort_2_3(arr, p + num*i, q);
        //Merge(arr, p, q);
        //Max_MIN()
    }else{
        sort_2_3(arr,p,q,arr_min_max);
    }
}

//void Merge(int*arr, int p, int q){}

int main()
{
    int arr[17] = {3,9,11,25,18,21,19,7,6,19,22,15,19,24,2,1,16};
    int arr_min_max[2] = {INT_MAX,INT_MIN};
    sqrt_n_sort(&arr[0], 0, 16, &arr_min_max[0]);

    //cout<<"begin:"<<endl;
    for(int i=0; i<2; i++){
        cout<<arr_min_max[i]<<" "<<endl;
    }
    return 0;
}