链表字符串ID排序异常：如何实现数字顺序的正确排序？

Hey there, let's break down why your linked list is sorting IDs as 1, 123, 2 instead of the expected 1, 2, 123. The core issue is straightforward: you're comparing IDs using string lexicographical order, not numeric order.

When you compare "123" and "2" as strings, the first character '1' has a lower ASCII value than '2', so the string comparison treats "123" < "2"—which works for text, but not for numeric values. Here are two practical solutions to fix this:

Solution 1: Convert IDs to Numeric Values for Comparison #

If all your IDs are valid integers (no letters, no meaningful leading zeros), the simplest fix is to convert string IDs to integers when comparing. Use C++'s stoi() function for this:

Modified Comparison Logic #

Replace every string-based comparison like Item->ID < head->ID with:

stoi(Item->ID) < stoi(head->ID)

Note #

If there’s a chance your IDs might contain non-numeric characters, add error handling (like try/catch blocks) to avoid crashes from invalid conversions.

Solution 2: Custom Numeric String Comparison (For IDs with Leading Zeros) #

If your IDs need to stay as strings (e.g., they have leading zeros like "002" that are part of the ID format), write a helper function to compare them as numeric values while preserving their string form. The logic is:

1. Shorter strings are smaller (since "2" is 1 character, it’s smaller than "123" which is 3 characters)
2. If lengths are equal, use regular string comparison (numeric strings of the same length follow lexicographical order that matches numeric order)

Step 1: Add the Helper Function #

bool isLessThanNumericString(const string& a, const string& b) {
    if (a.size() != b.size()) {
        return a.size() < b.size();
    }
    return a < b;
}

Step 2: Update the Sort Function #

Here’s your fixed SortRecords function, using the helper and fixing a couple of bugs (like missing head pointer updates and incomplete loop logic):

void SortRecords(Records* Item, Records* head, Records** Set_Head){
    // Initialize new node's Next to null to avoid dangling pointers
    Item->Next = nullptr;

    if (head == nullptr){
        *Set_Head = Item;
    } else if (isLessThanNumericString(Item->ID, head->ID)){
        Item->Next = head;
        *Set_Head = Item; // Update the head pointer to the new node
    } else {
        Records* Runner = head;
        // Traverse until we find the first node larger than Item
        while (Runner->Next != nullptr && !isLessThanNumericString(Item->ID, Runner->Next->ID)) {
            Runner = Runner->Next;
        }
        // Insert the new node after Runner
        Item->Next = Runner->Next;
        Runner->Next = Item;
    }
}

Testing the Fix #

With either solution, inserting IDs "1", "2", "123" will now result in the correct sorted order: 1 -> 2 -> 123.

内容的提问来源于stack exchange，提问作者Viknesh Suresh