人人人妻人人人妻人人人,99精品国产综合久久久久五月天 ,欧美白人最猛性XXXXX,日韩AV无码免费播放


News新聞

業(yè)界新聞動態(tài)、技術(shù)前沿
Who are we?

您的位置：首頁      樂道系統(tǒng)FAQ      歸并排序：歸并操作的一種有效排序算法

歸并排序：歸并操作的一種有效排序算法

標(biāo)簽： 發(fā)布日期：2014-02-21 08:43:00 1059

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。

首先考慮下如何將將二個有序數(shù)列合并。這個非常簡單，只要從比較二個數(shù)列的第一個數(shù)，誰小就先取誰，取了后就在對應(yīng)數(shù)列中刪除這個數(shù)。然后再進(jìn)行比較，如果有數(shù)列為空，那直接將另一個數(shù)列的數(shù)據(jù)依次取出即可。

[cpp] view plaincopy
 
  1. //將有序數(shù)組a[]和b[]合并到c[]中  
  2. void MemeryArray(int a[], int n, int b[], int m, int c[])  
  3. {  
  4.     int i, j, k;  
  5.   
  6.     i = j = k = 0;  
  7.     while (i < n && j < m)  
  8.     {  
  9.         if (a[i] < b[j])  
  10.             c[k++] = a[i++];  
  11.         else  
  12.             c[k++] = b[j++];   
  13.     }  
  14.   
  15.     while (i < n)  
  16.         c[k++] = a[i++];  
  17.   
  18.     while (j < m)  
  19.         c[k++] = b[j++];  
  20. }  

可以看出合并有序數(shù)列的效率是比較高的，可以達(dá)到O(n)。

解決了上面的合并有序數(shù)列問題，再來看歸并排序，其的基本思路就是將數(shù)組分成二組A，B，如果這二組組內(nèi)的數(shù)據(jù)都是有序的，那么就可以很方便的將這二組數(shù)據(jù)進(jìn)行排序。如何讓這二組組內(nèi)數(shù)據(jù)有序了？

可以將A，B組各自再分成二組。依次類推，當(dāng)分出來的小組只有一個數(shù)據(jù)時，可以認(rèn)為這個小組組內(nèi)已經(jīng)達(dá)到了有序，然后再合并相鄰的二個小組就可以了。這樣通過先遞歸的分解數(shù)列，再合并數(shù)列就完成了歸并排序。

[cpp] view plaincopy
 
  1. //將有二個有序數(shù)列a[first...mid]和a[mid...last]合并。  
  2. void mergearray(int a[], int first, int mid, int last, int temp[])  
  3. {  
  4.     int i = first, j = mid + 1;  
  5.     int m = mid,   n = last;  
  6.     int k = 0;  
  7.       
  8.     while (i <= m && j <= n)  
  9.     {  
  10.         if (a[i] <= a[j])  
  11.             temp[k++] = a[i++];  
  12.         else  
  13.             temp[k++] = a[j++];  
  14.     }  
  15.       
  16.     while (i <= m)  
  17.         temp[k++] = a[i++];  
  18.       
  19.     while (j <= n)  
  20.         temp[k++] = a[j++];  
  21.       
  22.     for (i = 0; i < k; i++)  
  23.         a[first + i] = temp[i];  
  24. }  
  25. void mergesort(int a[], int first, int last, int temp[])  
  26. {  
  27.     if (first < last)  
  28.     {  
  29.         int mid = (first + last) / 2;  
  30.         mergesort(a, first, mid, temp);    //左邊有序  
  31.         mergesort(a, mid + 1, last, temp); //右邊有序  
  32.         mergearray(a, first, mid, last, temp); //再將二個有序數(shù)列合并  
  33.     }  
  34. }  
  35.   
  36. bool MergeSort(int a[], int n)  
  37. {  
  38.     int *p = new int[n];  
  39.     if (p == NULL)  
  40.         return false;  
  41.     mergesort(a, 0, n - 1, p);  
  42.     delete[] p;  
  43.     return true;  
  44. }  

 

歸并排序的效率是比較高的，設(shè)數(shù)列長為N，將數(shù)列分開成小數(shù)列一共要logN步，每步都是一個合并有序數(shù)列的過程，時間復(fù)雜度可以記為O(N)，故一共為O(N*logN)。因?yàn)闅w并排序每次都是在相鄰的數(shù)據(jù)中進(jìn)行操作，所以歸并排序在O(N*logN)的幾種排序方法（快速排序，歸并排序，希爾排序，堆排序）也是效率比較高的。

 

在本人電腦上對冒泡排序，直接插入排序，歸并排序及直接使用系統(tǒng)的qsort()進(jìn)行比較（均在Release版本下）

對20000個隨機(jī)數(shù)據(jù)進(jìn)行測試：

對50000個隨機(jī)數(shù)據(jù)進(jìn)行測試：

再對200000個隨機(jī)數(shù)據(jù)進(jìn)行測試：

 

注：有的書上是在mergearray()合并有序數(shù)列時分配臨時數(shù)組，但是過多的new操作會非常費(fèi)時。因此作了下小小的變化。只在MergeSort()中new一個臨時數(shù)組。后面的操作都共用這一個臨時數(shù)組。