希尔排序未正确交换元素

Question

我几天来一直在努力解决希尔排序实现中的一个问题。具体来说，我在连续传递中使用 5、3 和 1 的间隙，但遇到了应该交换的元素没有被交换的问题。这是一个例子：

输入说明：

1. 序列A中数据元素的类型（0：int，1：double，2：char，3：string）
2. 数据元素序列A（空格分隔）
3. 希尔排序的遍历次数
4. 希尔排序每遍的步骤（空格分隔）

输出说明：

1. 如果第一个输入值在{0,1,2,3}之外，则输出“err”。
2. 否则：
3. 第一行：第一遍的间隙
4. 第二行：第一遍后的排序结果（元素之间用逗号分隔）
5. ...
6. 倒数第二行：最后一遍的间隙
7. 最后一行：最终排序结果（元素之间用逗号分隔）

解决方案：

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

问题是，即使我的调试语句显示了正确的比较，但在排序过程中某些元素并未按预期交换。我尝试过使用 swap() 但结果保持不变，似乎这不是交换方法问题。我不确定我的代码中问题出在哪里。任何见解或建议将不胜感激。谢谢！

附录：完整代码

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

template<class type>
void print_vector(vector<type>& v)
{
    
    //cout << "printing result" << endl;
    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()
{
    //cout << "in solution"<<endl;
    string to_sort;
    getline(cin, to_sort);
    
    vector<string> sort_v;
    stringstream ss(to_sort);
    string word;
    while (ss >> word) {
        sort_v.push_back(word);
    }
    //print_vector(sort_v);
    //cout << endl;
    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);
}

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;
}

Answer 1

问题出在你的

solution

函数上。

在您提供的示例中，此模板函数专门用于

type

为

int

（因为标志为 0），但

solution

中的代码仍将值存储在

vector<string>

中，忽略该类型。因此

shell_sort

模板专用于

string

类型，而不是

int

。

简而言之，您正在对字符串进行排序，而不是整数。您需要将字符串转换为整数。