排序6-归并排序

归并排序思路

每次将序列分为二组, 如果这两组数据是有序的, 在辅助空间进行排序.

细分至只有一个数据时序列是有序的, 从此开始向上合并临近小组

分组合并

//分组合并, 将要合并的两个序列按大小填入辅助空间中
void Merge(int arr[], int start, int end, int mid, int *tmp){
    //有序序列1
    int i_start = start;
    int i_end = mid;
    //有序序列2
    int j_start = mid+1;
    int j_end = end;
    //表示辅助空间有多少元素
    int length = 0;
    //合并两个有序序列,选取较小元素填入tmp
    while(i_start<=i_end && j_start<=j_end){ //两个序列有一个遍历完后退出循环
        if(arr[i_start]<arr[j_start]){
            tmp[length] = arr[i_start];
            length++;
            i_start++;
        }else{
            tmp[length] = arr[j_start];
            length++;
            j_start++;
        }
    }
    //j序列遍历完毕, i序列剩余放入tmp
    while(i_start<=i_end){
        tmp[length++] = arr[i_start++];
    }
    //i序列遍历完毕, j序列剩余放入tmp
    while(j_start<=j_end){
        tmp[length++] = arr[j_start++];
    }
    //辅助空间数据覆盖原空间
    for (int i = 0; i < length; i++){
        arr[start+i] = tmp[i];
    }
}

归并排序

//归并排序
void mergeSort(int arr[], int start, int end, int *tmp){
    //start>=end时,停止排序
    if(start>=end){
        return;
    }
    int mid = (start+end)/2;
    //分组
    //左
    mergeSort(arr,start, mid, tmp);
    //右
    mergeSort(arr,mid+1,end,tmp);
    //合并
    Merge(arr, start, end, mid, tmp);
}

创建序列

//创建序列
int* createArray(){
    srand((unsigned int)time(NULL));
    int *arr = (int*)malloc(sizeof(int) * MAX);
    for (int i = 0; i < MAX; i++){
        arr[i] = rand() % MAX;
    }
    return arr;
}

打印数组

//打印数组
void PrintArray(int arr[],int len){
    for (int i = 0; i < len; i++){
        cout << arr[i] << " ";
    }
    cout << endl;    
}

测试

int main(){
    int *myArr = createArray();
    PrintArray(myArr,MAX);
    //创建辅助空间
    int *tmp = (int*)malloc(sizeof(int) * MAX);
    //排序
    mergeSort(myArr,0,MAX-1,tmp);
    PrintArray(myArr,MAX);
    //释放资源
    free(tmp);
    free(myArr);

    system("pause");
    return 0;
}