Shell Sort实现中元素未正确交换问题求助

问题概述 #

实现Shell Sort时遭遇元素未正确交换问题，已卡数日。当前使用5、3、1作为逐轮排序间隔，但部分应交换的元素未按预期完成交换。

输入说明 #

• 序列A中数据元素类型（0: int, 1: double, 2: char, 3: string）
• 待排序序列A（元素以空格分隔）
• Shell Sort的轮次数量
• 每轮Shell Sort的间隔值（以空格分隔）

输出说明 #

• 若第一个输入值不在{0,1,2,3}范围内，输出"err"
• 否则：
  • 第一行：第一轮的间隔值
  • 第二行：第一轮排序后的结果（元素以逗号分隔）
  • ...
  • 倒数第二行：最后一轮的间隔值
  • 最后一行：最终排序结果（元素以逗号分隔）

核心实现代码片段 #

template<class type>
void shell_sort(vector<type>& a, int b[], int t)
{
    //vector a: Contains elements to be sorted.
    //array b: Stores the gaps for each pass of Shell sort.
    //t: Number of passes to execute.
    int length = a.size();
    for (int index = 0; index < t; index++)
    {
        int gap = b[index];
        cout << gap << endl;
        for (int i = gap; i < length; i++)
        {
            type temp = a[i];
            int j = i;
            cout << "a[j] and a[j-gap]: " << a[j] << " " << a[j - gap] << endl;
            while (j >= gap && a[j - gap] > temp)
            {
                cout << "a[j] and a[j-gap] swapped: " << a[j] << " " << a[j - gap] << endl;
                a[j] = a[j - gap];
                j -= gap;
            }

            a[j] = temp;
        }
        print_vector(a);
        cout << endl;
    }
}

示例输入 #

0
49 38 65 97 76 13 27 49 55 4
3
5 3 1

预期输出 #

5
13,27,49,55,4,49,38,65,97,76
3
13,4,49,38,27,49,55,65,97,76
1
4,13,27,38,49,49,55,65,76,97

实际问题表现（带调试信息的输出） #

0
49 38 65 97 76 13 27 49 55 4
3
5
a[j] and a[j-gap]: 13 49
a[j] and a[j-gap] swapped: 13 49
a[j] and a[j-gap]: 27 38
a[j] and a[j-gap] swapped: 27 38
a[j] and a[j-gap]: 49 65
a[j] and a[j-gap] swapped: 49 65
a[j] and a[j-gap]: 55 97
a[j] and a[j-gap] swapped: 55 97
a[j] and a[j-gap]: 4 76
a[j] and a[j-gap] swapped: 4 76
13,27,49,55,4,49,38,65,97,76
3
a[j] and a[j-gap]: 55 13
a[j] and a[j-gap]: 4 27 //4 and 27 should be swapped but didnt
a[j] and a[j-gap]: 49 49
a[j] and a[j-gap]: 38 55
a[j] and a[j-gap] swapped: 38 55
a[j] and a[j-gap]: 65 4
a[j] and a[j-gap]: 97 49
a[j] and a[j-gap]: 76 55
13,27,49,38,4,49,55,65,97,76
1
a[j] and a[j-gap]: 27 13
a[j] and a[j-gap]: 49 27
a[j] and a[j-gap]: 38 49
a[j] and a[j-gap] swapped: 38 49
a[j] and a[j-gap]: 4 49
a[j] and a[j-gap] swapped: 4 49
a[j] and a[j-gap]: 49 49
a[j] and a[j-gap]: 55 49
a[j] and a[j-gap]: 65 55
a[j] and a[j-gap]: 97 65
a[j] and a[j-gap] swapped: 76 97
13,27,38,4,49,49,55,65,76,97

问题根源分析 #

问题出在类型不匹配：在solution函数中，无论模板参数type是什么，都将输入元素存入vector<string>，再传给shell_sort。当处理int类型时，实际进行的是字符串比较而非数值比较。

比如调试中4和27的比较：字符串"4"的ASCII码（52）大于"27"的首字符'2'的ASCII码（50），因此a[j-gap] > temp（即"27" > "4"）的结果为false，不会进入交换逻辑，导致本该交换的元素未交换。

修复方案 #

修改solution函数，根据模板参数type直接解析输入为对应类型，而非统一存为string：

template<class type>
void solution()
{
    string to_sort;
    getline(cin, to_sort);
    
    vector<type> sort_v;
    stringstream ss(to_sort);
    type val;
    while (ss >> val) {
        sort_v.push_back(val);
    }
    int t;
    cin >> t;
    int* b = new int[t];
    for (int i = 0; i < t; i++)
    {
        cin >> b[i];
    }
    shell_sort(sort_v, b, t);
    delete[] b; // 释放动态分配的内存，避免内存泄漏
}

同时，确保print_vector函数能正确处理对应类型的输出（当前实现已支持，无需修改）。

完整修复后代码 #

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

template<class type>
void print_vector(vector<type>& v)
{
    for (auto i = v.begin(); i != v.end(); ++i) {
        cout << *i;
        if (i != v.end() - 1) { cout << ","; }
    }
}

template<class type>
void shell_sort(vector<type>& a, int b[], int t)
{
    int length = a.size();
    for (int index = 0; index < t; index++)
    {
        int gap = b[index];
        cout << gap << endl;
        for (int i = gap; i < length; i++)
        {
            type temp = a[i];
            int j = i;
            cout << "a[j] and a[j-gap]: " << a[j] << " " << a[j - gap] << endl;
            
            while (j >= gap && a[j - gap] > temp)
            {
                cout << "a[j] and a[j-gap] swapped: " << a[j] << " " << a[j - gap] << endl;
                a[j] = a[j - gap];
                j -= gap;
            }

            a[j] = temp;
        }
        print_vector(a);
        cout << endl;
    }
}

template<class type>
void solution()
{
    string to_sort;
    getline(cin, to_sort);
    
    vector<type> sort_v;
    stringstream ss(to_sort);
    type val;
    while (ss >> val) {
        sort_v.push_back(val);
    }
    int t;
    cin >> t;
    int* b = new int[t];
    for (int i = 0; i < t; i++)
    {
        cin >> b[i];
    }
    shell_sort(sort_v, b, t);
    delete[] b;
}

int main()
{
    int flag;
    cin >> flag;
    cin.ignore();
    if (flag == 0)
    {
        solution<int>();
    }
    else if (flag == 1)
    {
        solution<double>();
    }
    else if (flag == 2)
    {
        solution<char>();
    }
    else if (flag == 3)
    {
        solution<string>();
    }
    else
    {
        cout << "err" << endl;
    }
    return 0;
}

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