C 中的递归 - 冒泡排序？

Question

提前对最后的代码量表示歉意，因为有一点我会把它留到最后。 我正在将一些变量读取到一个结构中，并且我想对它们重新排序，以便最接近 0 的数字位于顶部（它们都是负值，因为它们是分贝读数）。 如果我没记错的话，我想我可能做了冒泡排序（或者一些可怕的尝试） 不管怎样，我决定尝试用递归来解决这个问题，我可以想出 2 或 3 种方法来完成这个任务，可能需要更多的代码，但不那么头疼，但我尝试了一下，它有效！

然而......一切都很完美，但最后我留下了一个随机重复的......我有10个节点，节点[0]到节点[9]。我故意将 5 之后（包括 5）的所有内容声明为 null，只是为了测试如果没有完整的 10 个条目，它将停止。 我的 printf 表明它停止了，但我最终将 5 个值之一复制到节点 [9] 中？

我很累，所以它可能盯着我的脸，但我真的不明白这是怎么发生的。任何提示/技巧将不胜感激。此外，任何关于不良实践或提高代码效率的方法的观察都不会被拒绝！

不必担心硬编码值或全局变量，它适用于嵌入式设备，并且该结构将由另一个函数填充。另外，我在下面的代码中留下了所有用于调试的打印语句，供任何尝试对其进行快速编译的人使用。

谢谢

#define MAX_NAME_SIZE 16
#define MAX_RSSI_SIZE 5

struct route_data
{
    char* ssid;

    int rssi;
};

struct route_data nodes[9];
struct route_data temp;


void main(){
nodes[0].ssid = "N1";
nodes[0].rssi = -20;
nodes[1].ssid = "N2";
nodes[1].rssi = -40;
nodes[2].ssid = "N3";
nodes[2].rssi = -34;
nodes[3].ssid = "N4";
nodes[3].rssi = -27;
nodes[4].ssid = "N5";
nodes[4].rssi = -80;

nodes[5].ssid = "NULL";
nodes[6].ssid = "NULL";
nodes[7].ssid = "NULL";
nodes[8].ssid = "NULL";
nodes[9].ssid = "NULL";

int y =0;

while(y!=10){
printf("Node[%d] -\n\t%s\t %d\n\n",y,nodes[y].ssid, nodes[y].rssi);
y++;
}

chooseBest(0,1);

y=0;

while(y!=10){
printf("Node[%d] -\n\t%s\t %d\n\n",y,nodes[y].ssid, nodes[y].rssi);
y++;
}

}

int chooseBest(int x, int i){

    //No point comparing the same values, increment up
    if(x==i){
    printf("X and I match - x %d\t i %d\n\n",x,i);
    i++;
    chooseBest(x,i);
    }
    //if X is less than I, and I is not null, check if i is greater than x and then swap
    else if((nodes[x].rssi<nodes[i].rssi)&&(nodes[i].rssi!=0)){
    printf("\nNode X Rssi %d\t Node I Rssi %d\n",nodes[x].rssi,nodes[i].rssi);
    printf("Node[X] is smaller than I - i %d\n",i);
    printf("X - %d\tI - %d\n\n",x,i);
        if(i>x){
            if(i!=0){
                temp.ssid = nodes[x].ssid;
                temp.rssi = nodes[x].rssi;

                nodes[x].ssid = nodes[i].ssid;
                nodes[x].rssi = nodes[i].rssi;

                nodes[i].ssid = temp.ssid;
                nodes[i].rssi = temp.rssi;
            }
        }
    i++;
    chooseBest(x,i);
    }
    //Is X greater than I and X is not null? If so, is X greater than I. Swap values
    else if((nodes[x].rssi>nodes[i].rssi)&&(nodes[x].rssi!=0)){
    printf("Node[X] is bigger\n");
    printf("X - %d\tI - %d\n\n",x,i);
        if(x>i)
        {
            temp.ssid = nodes[x].ssid;
            temp.rssi = nodes[x].rssi;

            nodes[x].ssid = nodes[i].ssid;
            nodes[x].rssi = nodes[i].rssi;

            nodes[i].ssid = temp.ssid;
            nodes[i].rssi = temp.rssi;

        }
    i++;
    chooseBest(x,i);
    }
    else{
        //If X is null we have traversed all values
        if(nodes[x].rssi==0){
            printf("Nodes[x] equals null\n");
            printf("X - %d\tI - %d\n\n",x,i);
        return 0;
        }
        //Otherwise, we have reached the end of I and need to increment X and reset I
        else{
        printf("About to increment X\n");
        printf("X - %d\tI - %d\n\n",x,i);
        x++;
        i=0;
        chooseBest(x,i);
        //printf("End of the line\n");
        }

    }

Answer 1

您只分配了 9 个节点，而您正在使用 10 个节点。这很可能会导致问题。

Answer 2

1）对于您正在使用的项目数量，冒泡排序就可以了。但是，如果您需要对很多东西进行排序（例如多几个数量级），您可能需要切换到不同的排序算法。平均情况下，冒泡排序的时间复杂度为 O(n^2)。 （来源：https://en.wikipedia.org/wiki/Bubble_sort#Performance )

2) 递归通常用于“分而治之”式的排序算法，例如 QuickSort。冒泡排序可以轻松地迭代实现。 （示例：https://en.wikipedia.org/wiki/Bubble_sort#Implementation )

3) 如果您在具有严格内存限制的嵌入式系统上运行此程序，则递归可能是一个糟糕的选择。递归通常需要有一个大的堆栈空间来支持您正在进行的嵌套函数调用。您可以通过尾递归来解决这个问题，但是您必须确保编写的递归函数支持这一点。 （尾递归示例：https://en.wikipedia.org/wiki/Tail_call#Example_programs< /一>）