按姓氏排序結構

Question

我有按姓氏排序的算法，但我無法弄清楚如何按姓氏排序，然後如果兩個人有相同的姓氏，按他們的名字排序。

void sortLastName(FRIEND friends[ARRAY_MAX], int& count) { 

    FRIEND temp; 

    for(int i = 0; i < count - 1; i++) { 
     for (int j = i + 1; j < count; j++) { 
      if (stricmp(friends[i].lastName, friends[j].lastName) > 0) { 
       temp = friends[i]; //swapping entire struct 
       friends[i] = friends[j]; 
       friends[j] = temp; 
      } 
     } 
    } 
} 

===編輯====================

我不想使用STD sort()

Answer 1

首先，比較姓氏。如果它們相等，則比較所述第一名稱：

int compareResult = stricmp(friends[i].lastName, friends[j].lastName); 
if(compareResult == 0) 
    compareResult = stricmp(friends[i].firstName, friends[j].firstName); 
if(compareResult < 0) 
    // swap friends[i] and friends[j] 

Answer 2

首先，使用qsort或適當的C++當量這需要其比較兩個對象的功能。

的比較應該然後是簡單的：

int compare_by_name(const FRIEND& f1, const FRIEND& f2) 
{ 
    int last_name_matches = strcmpi(f1.lastName, f2.lastName); 
    return (last_name_matches != 0) ? last_name_matches : 
      strcmpi(f1.firstName, f2.firstName) ; 
} 

注意：一個真實的C++實現可能會使用模板的比較器功能。

Answer 3

添加以下內容：

else if (stricmp(friends[i].lastName, friends[j].lastName) == 0 && 
     stricmp(friends[i].firstName, friends[j].firstName) > 0) { 
    temp = friends[i]; //swapping entire struct 
    friends[i] = friends[j]; 
    friends[j] = temp; 
} 

Answer 4

你必須改變你的比較。基本算法是如果朋友[i]>朋友[j]然後交換它們。因此，將「>」的定義更改爲包含名字比較。

類似下面應該做的：

if (stricmp(friends[i].lastName, friends[j].lastName) > 0 || 
    (stricmp(friends[i].lastName, friends[j].lastName) == 0 && 
    stricmp(friends[i].firstName, friends[j].firstName) > 0)) 

你可能想要做的姓氏比較只有一次，雖然（它存儲在一個臨時變量，而不是比較兩次），但這個想法是一樣的。

請注意，執行此操作的「最佳」方法可能是在FRIEND類中提供比較函數。然後，您可以使用if(friends[i].CompareTo(friends[j]) > 0)。

Answer 5

請不要自己實施排序 - std :: sort（在<algorithm>）這個工作更好，更高效。 （除了你只想看看你的算法如何用於實驗目的）

無論如何你必須指定一個比較函數或更好的函子。

struct FriendComparer { 
    bool operator() (const FRIEND& a, const FRIEND& b) { 
     // Comparison code here (see previous posts) 
    } 
}; 

你只需調用它是這樣的：

std::sort(friendArray, friendArray + count, FriendComparer()); 

Answer 6

你爲什麼不使用std::sort？這就是它是：

struct NameComparer { 
    bool operator()(const FRIEND& lhs, const FRIEND& rhs){ 
    int compareResult = stricmp(lhs.lastName, rhs.lastName); 
    if(compareResult == 0){ 
     compareResult = stricmp(lhs.firstName, rhs.firstName); 
    } 
    return compareResult < 0; 
    } 
}; 

std::sort(friends, friends + ARRAY_MAX, NameComparer()); 

當然，你真的應該使用C++ std::string類爲好。這就是它的目的。然後，您不必隨意使用容易出錯的C字符串操作函數，如stricmp。

Answer 7

除了建立使用兩個名字比較函數的選擇，你可以排序的拳頭名然後排序的姓氏，但你必須小心使用stable sort，第二道。不妨將它用於第一個。

好消息：std::stable_sort可用，並保證穩定（感謝Adam和libt的更正）。雖然有些實現可能會不穩定，但不保證明文std::sort和c標準庫qsort是穩定的。正如馬克在評論中指出的那樣，你展示的泡沫排序已經很穩定。

---

這是效率較低的單排序與-A-自定義比較功能的選擇，但它可以很容易地讓你的用戶在運行時選擇多種類的（因爲你不必須定義每種可能的比較功能，或者一種迷你語言）。

Answer 8

定義一個比較函數（或類如jalf建議），並使用STL的標準::排序（）：

bool compareFriends(FRIEND const & lhs, FRIEND const & rhs) 
{ 
    int const resultLast = stricmp(lhs.lastName, rhs.lastName); 

    if(resultLast == 0) 
    { 
     return stricmp(lhs.firstName, rhs.firstName) < 0; 
    } 
    else 
    { 
     return resultLast < 0 
    } 
} 

void sortLastName(FRIEND friends[ARRAY_MAX], int& count) 
{ 
    std::sort(friends, friends + count, &compareFriends); 
} 

Answer 9

如果你不介意使用boost.tuple（和更換或至少修改現有Friend的實現），還有一個包含比較函數。

#include <boost/tuple/tuple.hpp> 
#include <boost/tuple/tuple_comparison.hpp> 

typedef boost::tuple<std::string, std::string> Friend; 

Friend f1, f2; 
bool compareFriends = f1 < f2; 

以上所有都應該工作。

Answer 10

您可以使用對齊姓氏和名字左邊的串聯作爲排序鍵

這是你正在尋找另一個角度來看，我認爲:)

string key(const FRIEND& aFriend) 
{ 
    const int INITIALS_MAX_LENGTH = 200; // assume the worst 

    string firstNameKeyPart = string(INITIALS_MAX_LENGTH, ' '); 
    string lastNameKeyPart = string(INITIALS_MAX_LENGTH, ' '); 

    firstNameKeyPart.replace(0, 0, aFriend.firstName); 
    lastNameKeyPart.replace(0, 0, aFriend.lastName); 

    return lastNameKeyPart + firstNameKeyPart; 
} 

//... 

if (key(friends[i]) > key(friends[j])) 
{ 
    //swap 
} 

Answer 11

你可以按姓氏排序，如果姓氏相同，則按姓氏排序。 像這樣的東西（冒泡排序使用）：

for (int i = 1; i < dictionary.size(); ++i) 
    for (int j = 0; j < dictionary.size()-1; ++j) { 
     if (dictionary[i].Last < dictionary[j].Last) 
      swap(dictionary[i], dictionary[j]); 
    } 

for (int i = 1; i < dictionary.size(); ++i) 
    for (int j = 0; j < dictionary.size() - 1; ++j) { 
     if (dictionary[i].Last == dictionary[j].Last && dictionary[i].First < dictionary[j].First) 
      swap(dictionary[i], dictionary[j]); 
    }