C++ - 仅使用数组进行链排序

Question

我有一个家庭作业，要用 C++ 创建一个 Strand sort 算法，但我不允许使用 lists，只能使用 arrays .我很难理解这个算法，因为从来没有人向我解释过它，而且 Google 提供的关于这个主题的信息有限。

我已尽力移植我在 Wikipedia 上找到的代码，从 PHP 到 C++，但它无法正常工作。 它不对数组进行排序。

这是我的代码，我知道其中很多可能写得不好，但这是我所知道的最好的。

#include <iostream>
using namespace std;
void echoArray(int a[], int n) {
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

//removes an element from array
int* array_remove(int* a, int& n, int index) {
    int p = 0;
    int* newArray = new int[n - 1];
    for(int i = 0; i < n; i++) {
        if(i != index) {
            newArray[p] = a[i];
            p++;
        }
    }
    n--;
    return newArray;
}
//adds an element to the end of an array
int* array_append(int* a, int& n, int el) {
    int* newArray = new int[n+1];
    int i = 0;
    for(; i < n; i++) {
        newArray[i] = a[i];
    }
    if(n == 0)
        i = 0;
    newArray[i] = el;
    n++;
    return newArray;
}

//inserts an element (el) to index p
int* array_insert(int* a, int& n, int p, int el) {
    int c = 0;
    n++;
    int* newArray = new int[n];
    for(int i = 0; i < n; i++) {
        if(i != p) {
            newArray[i] = a[c];
            c++;
        } else {
            newArray[i] = el;
        }
    }
    return newArray;
}

int* strandSort(int* a, int n) {
    int arrC = n;
    int resC = 0;
    int subC = 0;
    int* result = new int[1];
    while(arrC > 0) {
        subC = 0;
        int* sublist = new int[1];
        sublist = array_append(sublist, subC, a[0]);
        a = array_remove(a, arrC, 0);
        for(int i = 0; i < arrC; i++) {
            if(a[i] > sublist[subC - 1]) {
                sublist = array_append(sublist, subC, a[i]);
                a = array_remove(a, arrC, i);
                i--;
            }
        }
        if(resC > 0) {
            for(int i = 0; i < subC; i++) {
                bool spliced = false;
                for(int j = 0; j < resC - 1; i++) {
                    if(sublist[i] > result[j]) {
                        result = array_insert(result, resC, i, sublist[i]);
                        spliced = true;
                        break;
                    }
                }
                if(!spliced) {
                    result = array_append(result, resC, sublist[i]);
                }
            }
        } else {
            result = sublist;
            resC = subC;
        }
    }
    echoArray(result, resC);
    return result;
}

int main() {
    int a[] = {3, 20, 6, 1, 19, 21, 6, 11, 25, 6, 0, 1, 8, 7, 29, 26, 10, 29, 9, 5};
    int n = 20;
    strandSort(a, n);
    return 0;
}

此外，我意识到数组是通过引用传递的。

Answer 1

使用cout<<针对问题

看完Strand Sort的wiki之后，我们知道这个算法有两个部分。

1. 取出一个相对排序的列表
2. 将其与结果列表合并

所以需要找出哪一部分不对，加上

    cout << "step1: sublist = ";
    echoArray(sublist, subC);

之前 if(resC > 0) {我们将看到第 1 步是对还是错。

添加

    cout << "step2: result = ";
    echoArray(result, resC);

在 while(arrC > 0) {} 的底部循环检查step2。

获取:

step1: sublist = 3 20 21 25 29 
step2: result = 3 20 21 25 29 
step1: sublist = 6 19 26 29 
step2: result = 6 19 26 29 3 20 21 25 29 
step1: sublist = 1 6 11 
step2: result = 6 19 11 26 29 3 20 21 25 29 
step1: sublist = 6 8 10 
step2: result = 6 8 10 19 11 26 29 3 20 21 25 29 
step1: sublist = 0 1 7 9 
step2: result = 6 8 7 9 10 19 11 26 29 3 20 21 25 29 
step1: sublist = 5 
step2: result = 6 8 7 9 10 19 11 26 29 3 20 21 25 29 0 

正如我们所见，第 1 步总是正确的，但合并步骤是错误的。

所以我们将代码集中在if(resC > 0) {}中 block 。

仔细阅读代码

如果您仔细阅读代码，您会在 for(int j = 0; j < resC - 1; i++) { 中找到i++是废话。

而且merge步骤有很多bug，需要重新考虑。

第2步的固定代码:

if(resC > 0) {
    int j = 0;
    for(int i = 0; i < subC; i++) {
        bool spliced = false;
        for(;j < resC; j++) {
            if(sublist[i] < result[j]) {
                result = array_insert(result, resC, j++, sublist[i]);
                spliced = true;
                break;
            }
        }
        if(!spliced) {
            result = array_append(result, resC, sublist[i]);
        }
    }
} else {
    result = sublist;
    resC = subC;
}