C语言maxsort按日期排序结构体数组时同日期保留原序方法

你当前实现的基于最大值选择的排序（maxsort，属于选择排序变体）是不稳定排序，问题根源有两点：

• Index_of_max函数在遇到过期日期完全相同的元素时，始终选择遍历过程中第一个遇到的（索引最小的）最大值，将其交换到当前未排序段末尾时，会打乱相同日期元素的原有相对顺序
• Sort_By_Date函数中申请的temp_store没有被任何逻辑使用，属于冗余代码

不需要额外存储原数组副本，只需要修改最大值选择逻辑：当遍历到的元素过期日期和当前记录的最大值日期相等时，将最大值索引更新为当前遍历到的更大索引，保证每次选中的是未排序段里最靠后的最大值。交换这个最靠后的最大值到段尾时，不会跨元素挪动相同日期的项，自然就能保留原有相对顺序，同时删掉冗余的内存申请代码。

修改后的代码 #

首先修改Index_of_max函数，在年月日全部相等的分支添加索引更新逻辑，同时优化多余的条件判断：

int Index_of_max(Item* store, int len)
{
    int i, i_max = 0, curr_year, year, curr_month, month, curr_day, day;
    for (i = 1; i <= len - 1; i++)
    {
        year = (store[i].expiration_date[9] - '0') + ((store[i].expiration_date[8] - '0') * 10) + ((store[i].expiration_date[7] - '0') * 100) + ((store[i].expiration_date[6] - '0') * 1000);
        curr_year = (store[i_max].expiration_date[9] - '0') + ((store[i_max].expiration_date[8] - '0') * 10) + ((store[i_max].expiration_date[7] - '0') * 100) + ((store[i_max].expiration_date[6] - '0') * 1000);
        if (year > curr_year)
        {
            i_max = i;
        }
        else if (year < curr_year)
        {
            continue;
        }
        else // 年相等，比较月
        {
            month = (store[i].expiration_date[4] - '0') + ((store[i].expiration_date[3] - '0') * 10);
            curr_month = (store[i_max].expiration_date[4] - '0') + ((store[i_max].expiration_date[3] - '0') * 10);
            if (month > curr_month)
            {
                i_max = i;
            }
            else if (month < curr_month)
            {
                continue;
            }
            else // 月相等，比较日
            {
                day = (store[i].expiration_date[1] - '0') + ((store[i].expiration_date[0] - '0') * 10);
                curr_day = (store[i_max].expiration_date[1] - '0') + ((store[i_max].expiration_date[0] - '0') * 10);
                if (day > curr_day)
                {
                    i_max = i;
                }
                else if (day == curr_day)
                {
                    // 关键修改：日期相等时选索引更大的元素作为最大值，保证排序稳定性
                    i_max = i;
                }
                // day < curr_day 直接跳过即可
            }
        }
    }
    return i_max;
}

然后修改Sort_By_Date函数，删掉无用的temp_store相关逻辑：

void Sort_By_Date(Item* store, int *len)
{
    int length;
    for (length = *len; length > 1; --length)
    {
        int i_max = Index_of_max(store, length);
        swap(&store[length - 1], &store[i_max]);
    }
}

以3个相同过期日期的元素[Item0, Item1, Item2]为例：

1. 第一轮遍历未排序段长度为3，遍历到i=1时日期相等更新i_max=1，遍历到i=2时日期相等更新i_max=2，交换位置2和位置2，元素无变动
2. 第二轮遍历未排序段长度为2，遍历到i=1时日期相等更新i_max=1，交换位置1和位置1，元素无变动
3. 排序完成后元素原有相对顺序完全保留

如果是不同日期混合的场景，相同日期的元素始终会按照原有先后顺序排列，不会出现错位。

内容的提问来源于stack exchange，提问作者roee wagner