首页 > 代码库 > 排序算法——归并排序

排序算法——归并排序

2024-07-04 02:58:51   230人阅读

归并排序是分治法的典型举例。

分治法的思想是，将原有问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

 

分治模式在每层递归时都有三个步骤：

分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。

解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。

合并这些子问题的解成原问题的解。

 

归并排序算法完全遵循分治模式。直观上其操作如下：

分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。

解决：使用归并排序递归地排序两个子序列。

合并：合并两个已经排序好的子序列以产生已排序的答案。

#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;

const int arrSize = 16;

void MergeSort(int* arr, const int first, const int last);
void MergeArr(int* arr, const int first, const int mid, const int last);

int main()
{
    srand((unsigned int)time(NULL));
    int arr[arrSize];
    
    for (int index = 0; index != arrSize; ++index) {
        arr[index] = rand() % 1000;
    }

    MergeSort(arr, 0, arrSize-1);

    for (int index = 0; index != arrSize; ++index) {
        cout << setw(4) << arr[index] << ‘ ‘;
        if ((index+1) % 4 == 0) {
            cout << endl;
        }
    }

    return 0;
}

//用于递归排序
void MergeSort(int* arr, const int first, const int last)
{
    if (first < last) {
        int mid = (first + last) / 2;
        MergeSort(arr, first, mid);
        MergeSort(arr, mid+1, last);
        MergeArr(arr, first, mid, last);
    }
}

//合并两个已经排序好的数组
void MergeArr(int* arr, const int first, const int mid, const int last)
{
    int* temp = new int[last-first+1];
    int i = first;
    int j = mid+1;
    int index = 0;

    while (i <= mid && j <= last) {
        if (arr[i] <= arr[j]) {
            temp[index++] = arr[i++];
        } else {
            temp[index++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[index++] = arr[i++];
    }
    while (j <= last) {
        temp[index++] = arr[j++];
    }

    for (i = first, index = 0; i <= last; ++i, ++index) {
        arr[i] = temp[index];
    }

    delete[] temp;
}


在函数的参数传递中，first、last、mid、mid+1 表示的是数组的下标。

归并排序的时间复杂度为O(nlgn)。

 

 


联系
我们