C++归并排序算法实例

C++归并排序算法实例

　　归并排序算法是采用分治法的一个非常典型的应用。下面小编为大家整理了C++归并排序算法实例，希望能帮到大家！

　　归并排序的思想是将一个数组中的数都分成单个的；对于单独的一个数，它肯定是有序的，然后，我们将这些有序的单个数在合并起来，组成一个有序的数列。这就是归并排序的思想。它的时间复杂度为O(N*logN)。

　　代码实现

　　复制代码 代码如下:

　　#include

　　using namespace std;

　　//将有二个有序数列a[first...mid]和a[mid...last]合并。

　　void mergearray(int a[], int first, int mid, int last, int temp[])

　　{

　　int i = first, j = mid + 1;

　　int m = mid, n = last;

　　int k = 0;

　　while (i <= m && j <= n)

　　{

　　if (a[i] <= a[j])

　　temp[k++] = a[i++];

　　else

　　temp[k++] = a[j++];

　　}

　　while (i <= m)

　　temp[k++] = a[i++];

　　while (j <= n)

　　temp[k++] = a[j++];

　　for (i = 0; i < k; i++)

　　a[first + i] = temp[i];

　　}

　　void mergesort(int a[], int first, int last, int temp[])

　　{

　　if (first < last)

　　{

　　int mid = (first + last) / 2;

　　mergesort(a, first, mid, temp); //左边有序

　　mergesort(a, mid + 1, last, temp); //右边有序

　　mergearray(a, first, mid, last, temp); //再将二个有序数列合并

　　}

　　}

　　bool MergeSort(int a[], int n)

　　{

　　int *p = new int[n];

　　if (p == NULL)

　　return false;

　　mergesort(a, 0, n - 1, p);

　　[] p;

　　return true;

　　}

　　int main()

　　{

　　int arr[] = {2, 1, 4};

　　MergeSort(arr, 3);

　　for (int i = 0; i < 3; ++i)

　　{

　　cout<<arr[i]<<" ";

　　}

　　cout<<endl;

　　}

【C++归并排序算法实例】相关文章：

C语言实现归并排序算法实例09-18

C++实现自底向上的归并排序算法09-09

C语言冒泡排序算法实例06-15

C语言选择排序算法及实例代码07-25

C语言插入排序算法及实例代码07-02

C语言中使用快速排序算法对元素排序的实例06-20

Java排序算法06-17

c++快速排序详解10-18

php:树形结构的算法实例10-18

PHP快速排序算法详解08-30