计数与合并排序的比较

现在我正在学习算法，并且我被鼓励通过所有不同的排序方法来找出每种类型通过数组排序需要进行多少次比较。我需要在这个合并排序程序中实现一个计数器，但是我需要去的地方有点丢失。如果任何人都能指引我正确的方向，我会很感激。计数与合并排序的比较

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

计数与合并排序的比较

回答

相关问题