這種合併排序算法能做多少次比較？

Question

我想將compare++添加到此代碼中，以計算此算法完成的比較次數。在Merge(...)和if和else裏邊的第一個while循環的每次執行中，是否需要增加compare的計數？這些是compare應該增加的唯一位置嗎？ （我加了這個增量，我認爲它屬於和註釋。請忽略的交換功能）

#include "MergeSort.h" 

template<class ItemType> 
void MergeClass<ItemType>::sort(ItemType values[], int first, int last) 
// Post: The elements in values are sorted by key. 
{ 
    if (first < last) 
    { 
     int middle = (first + last)/2; 
     sort(values, first, middle); 
     sort(values, middle + 1, last); 
     Merge(values, first, middle, middle + 1, last); 
    } 
} 

template<class ItemType> 
void MergeClass<ItemType>::Merge(ItemType values[], int leftFirst, int leftLast, 
int rightFirst, int rightLast) 
// Post: values[leftFirst]..values[leftLast] and 
// values[rightFirst]..values[rightLast] have been merged. 
// values[leftFirst]..values[rightLast] are now sorted. 
{ 
    ItemType tempArray[5]; 
    int index = leftFirst; 
    int saveFirst = leftFirst; 
    while ((leftFirst <= leftLast) && (rightFirst <= rightLast)) 
    { 
     if (values[leftFirst] < values[rightFirst]) 
     { 
      tempArray[index] = values[leftFirst]; 
      leftFirst++; 
      //compare++; 
     } 
     else 
     { 
      tempArray[index] = values[rightFirst]; 
      rightFirst++; 
      //compare++; 
     } 
     index++; 
     //compare++; 
    } 
    while (leftFirst <= leftLast) 
    // Copy remaining items from left half. 
    { 
     tempArray[index] = values[leftFirst]; 
     leftFirst++; 
     index++; 
    } 
    while (rightFirst <= rightLast) 
    // Copy remaining items from right half. 
    { 
     tempArray[index] = values[rightFirst]; 
     rightFirst++; 
     index++; 
    } 
    for (index = saveFirst; index <= rightLast; index++) 
     values[index] = tempArray[index]; 
} 


template<class ItemType> 
inline void MergeClass<ItemType>::Swap(ItemType& item1, ItemType& item2) 
// Post: Contents of item1 and item2 have been swapped. 
{ 
    ItemType tempItem; 
    tempItem = item1; 
    item1 = item2; 
    item2 = tempItem; 
} 

template<class ItemType> 
MergeClass<ItemType>::MergeClass() 
{ 
    compare = 0; 
    swap = 0; 
} 
template<class ItemType> 
void MergeClass<ItemType>::sortPreformance() 
{ 
    cout << "Comparisons made: " << compare <<endl; 
    cout << "Swaps made: "<< swap <<endl; 
} 

Answer 1

如果它嚴格意味着分析，我把計數邏輯排序類之外。也就是說像下面這樣（這只是計算由std::sort使用比較和交換的數量）：

#include <iostream> 
#include <algorithm> 
#include <cstdlib> 
using namespace std; 

template<typename T> 
struct CountingItem { 
    CountingItem(const T& val = T()) : val_(val) {} 

    bool operator<(const CountingItem<T>& rhs) const { 
     ++compares; 
     return val_ < rhs.val_; 
    } 

    static size_t compares; 
    static size_t swaps; 
    T val_; 
}; 

template<typename T> 
size_t CountingItem<T>::compares = 0; 
template<typename T> 
size_t CountingItem<T>::swaps = 0; 

template<typename T> 
void swap(CountingItem<T>& a, CountingItem<T>& b) { 
    ++CountingItem<T>::swaps; 
    std::swap(a, b); 
} 

int main() 
{ 
    const size_t num_items = 10000; 
    CountingItem<int> items[num_items]; 
    for(int i = 0; i < num_items; i++) items[i] = rand() % 100; 
    sort(items, items+num_items); 
    cout << "Compares = " << CountingItem<int>::compares << endl; 
    cout << "Swaps = " << CountingItem<int>::swaps << endl; 

    // Reset CountingItem<int>::compares and swaps here if you're running another test 
}