在 C 中计数排序显然有效，但二进制搜索不起作用

Question

我正在寻找有关在第 3 周的 CS50 课程中实现计数排序功能的帮助。

必须对 int 数组进行排序。我测试了各种未排序的数组，我的计数排序函数似乎可以正确排序数组，但我的搜索函数之后将无法在排序的数组上运行。有人可以给我一个提示吗？

void countsort( int array[], int size) {
    int count=0;
    int zahl=0;
    int max=65536;
    int countarr [max];
    int finalarr [size];
    memset (countarr, 0, sizeof(countarr));
    for(int i=0;i<size;i++) {
        zahl=array[i];
        countarr[zahl]++;
    }
    for(int i=0;i<max;i++) {
        while(countarr[i]>0) {
            finalarr[count]=i;
            countarr[i]--;
            count++;
        }
    }
    array=finalarr;
    for(int i=0;i<size;i++){
        printf(" %i ",array[i]);
    }
}

这是我在数组排序后使用的搜索算法，它适用于其他人的排序算法。

bool binarysearch(int value, int values[], int n){
    int start=0,
        end=n,
        mid=0,
        midpos=0;
    while(end>0) {
        midpos=(start+end)/2; 
        mid=values[midpos];
        if(mid==value) return true;
        if(mid<value) start=++midpos;
        if(mid>value) end=--midpos;
    }
    return false;
} 

Answer 1

1. 在binarysearch中，循环条件while(end>0)是错误的。如果我们搜索的值大于数组中至少一个元素，则end永远不会为零。尝试将其更改为 while(end>=start) ，字面意思是所考虑的间隔是非空的。

2. 在countsort中，行array=finalarr;不会复制整个数组。相反，局部变量array成为指向finalarr的指针。原始数组的内容保持不变，并且当您退出函数时，排序后的数组将消失。这就解释了为什么你的二叉搜索与其他排序函数一起工作(更好(。
   尝试将finalarr[count]=i;更改为array[count]=i;并完全摆脱finalarr，立即将值放入array。或者，您可以使用memmove而不是该行。