計數與合併排序的比較

現在我正在學習算法，並且我被鼓勵通過所有不同的排序方法來找出每種類型通過數組排序需要進行多少次比較。我需要在這個合併排序程序中實現一個計數器，但是我需要去的地方有點丟失。如果任何人都能指引我正確的方向，我會很感激。計數與合併排序的比較

//MergeSort.h 

#include <iostream> 
using namespace std; 
void merge_sort(int A[], int low, int high); 
void merge(int A[], int low, int mid, int high); 

void merge_sort(int A[], int low, int high) 
{ 
    int mid; 
    if(low<high) 
    { 
     mid=(low+high)/2; 
     merge_sort(A,low,mid); 
     merge_sort(A,mid+1,high); 
     merge(A,low,mid,high); 

    } 
} 

void merge(int A[], int low, int mid, int high) 
{ 
    int h, i, j, B[100], k; 
    h = low; 
    i = low; 
    j = mid + 1; 

    while ((h <= mid) && (j <= high)) 
    { 
     if (A[h] <= A[j]) 
     { 
      B[i] = A[h]; 
      h++; 
     } 
     else 
     { 
      B[i] = A[j]; 
      j++; 
     } 
     i++; 
    } 

    if (h > mid) 
    { 
     for (k = j;k <= high;k++) 
     { 
      B[i] = A[k]; 
      i++; 
     } 
    } 
    else 
    { 
     for (k = h;k <= mid;k++) 
     { 
      B[i] = A[k]; 
      i++; 
     } 
    } 

    for (k = low;k <= high;k++) 
    { 
     A[k] = B[k]; 
    } 
}

和

//MergeSort.cpp 

#include <iostream> 
using namespace std; 

#include "MergeSort.h" 
#include <ctime> 

int main() 
{ 
    int A[1000], n = 100, i; 
    srand(time(NULL)); 

    cout << "Here are " << n << " random numbers: \n"; 
    for (i = 0; i < n; i++) 
    { 
     A[i] = rand() % 100; 
     cout << " " << A[i]; 
    } 

    merge_sort(A, 0, n-1); 

    cout << "\n\nThe sorted array is: "; 
    for (int i=0;i<n;i++) 
     cout << A[i] <<" "; 

    cout<<endl<<endl; 
    system("pause"); 
}

來源

2016-04-27 Nick

您是否熟悉qsort庫函數？如果是這樣，想象你的合併排序需要一個類似的接口，即比較函數是由其他人編寫的並作爲參數傳遞的。你需要調用哪個比較函數？ – user3386109

我知道你對代碼實驗以及它是如何工作感到興奮，但是如果你正在學習算法，我建議你閱讀這本免費的書，其中有很多很好的解釋和證明，包括大量的僞代碼，這肯定會幫助你清楚事情爲你：http://jeffe.cs.illinois.edu/teaching/algorithms/。例如，只需在所有「合併排序」註釋的pdf-book中進行查找搜索即可。 – user3773048

計算比較次數的一種簡單方法是將merge和merge-sort函數從void更改爲返回其中的比較次數並遞歸計數。

來源

2016-04-27 04:40:55 Dandelion

乙的長度的陣列僅僅是100.it將被綁定。

來源

2016-04-27 04:38:33 Sky

最簡單的方法是使用一個靜態的全局變量，並在merge（）中每次比較A []時增加它，然後讓主程序在排序後顯示計數。這避免了必須改變現有功能的接口。

來源

2016-04-27 06:14:49 rcgldr

計數與合併排序的比較

回答

相關問題