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

C++實現自頂向下的歸并排序算法09-14

C語言實現歸并排序算法實例分析06-28

C語言實現歸并排序算法08-19

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