C++歸并排序算法實例

　　歸并排序算法是采用分治法的一個非常典型的應用。下面小編為大家整理了C++歸并排序算法實例，希望能幫到大家！

　　歸并排序的思想是將一個數(shù)組中的數(shù)都分成單個的；對于單獨的一個數(shù)，它肯定是有序的，然后，我們將這些有序的單個數(shù)在合并起來，組成一個有序的數(shù)列。這就是歸并排序的思想。它的時間復雜度為O(N*logN)。

　　代碼實現(xiàn)

　　復制代碼 代碼如下:

　　#include

　　using namespace std;

　　//將有二個有序數(shù)列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); //再將二個有序數(shù)列合并

　　}

　　}

　　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-26

C++插入排序算法實例08-26

C++冒泡排序算法實例詳解06-09

C語言實現(xiàn)歸并排序算法實例09-18

C++實現(xiàn)自底向上的歸并排序算法09-09

C++實現(xiàn)自頂向下的歸并排序算法09-14

C語言實現(xiàn)歸并排序算法實例分析06-28

C語言實現(xiàn)歸并排序算法08-19

C語言冒泡排序算法實例06-15