时间戳

首页 > 解决方案 > 创建一个小排序（C++ 类介绍）

c++ - 创建一个小排序（C++ 类介绍）

问题描述

我目前是一名大学生，正在学习 c++ 课程，但我陷入了这个问题。"定义一个函数

void smallSort(int nums[], int 长度)

它使用“小排序”算法对一系列小数字进行排序。（在我们的例子中，“小”表示 0 到 9999 之间的任何值。）该算法的工作原理如下：声明一个名为 counts 大小为 10000 的本地 int 数组并将每个元素初始化为 0。然后循环遍历数组 nums 并为每个数字递增具有该索引的计数元素。最后一步是遍历 counts 数组并将值复制回 nums。例如，如果您的循环当前位于 counts 数组的元素 3 并且 counts[3] 包含一个 10，那么您可以将 10 个 3 复制到 nums 数组中。

举个例子：假设 nums 是 { 1, 4, 3, 0, 0, 4, 1, 4, 1, 2, 6, 4, 6, 0, 0, 0, 0, 4} 并且长度是 18。那么填充 counts 数组后，它将包含值 {6, 3, 1, 1, 5, 0, 2, ... }，counts[6] 之后的所有元素都等于 0。这是因为数组 nums 包含六个0、3 个 1、1 个 2、1 个 3、5 个 4、0 个 5、2 个 6，并且没有大于 6 的值。在算法的下一阶段，我们将遍历 counts 数组并复制回 6 个 0，然后是 3 个 1，将一个 2 等放入 nums 数组，使其包含 {0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 6, 6}。请注意，nums 现在按升序排序。”

这是我的解决方案：

void smallSort(int nums[], int length){
int count [10000];
    int a = 0;
    for(int i =0; i<10000; i++){
        count[i] = 0;
    }
    for(int i =0; i<length ; i++){
    count[nums[i]]++;   
    }
    for(int i = 0; i< length; i++){
        for(int j = 0; j<count[i]; j++){
            nums[a] = count[i];
            a++;
        }
    }
}

这是我应该得到的答案：0·1210·3000·2434·446·54·111·900·43·7·17·1001·9999·0·0·9999·1210·54↵ 0·0· 0·7·17·43·54·54·111·446·900·1001·1210·1210·2434·3000·9999·9999·↵</p>

这就是我得到的：0·1210·3000·2434·446·54·111·900·43·7·17·1001·9999·0·0·9999·1210·54·↵ 3·3·3 ·1·1·54·111·900·43·7·17·1001·9999·0·0·9999·1210·54·↵</p>

我已经尝试解决这个问题超过 2 小时，由于我一直遇到问题，我决定在 Xcode 上创建我自己的数组并尝试解决它，但是“count[nums[i]]++; 旁边出现一个错误； " 上面写着“线程 1：EXC_BAD_ACCESS（代码=1，地址=0x7ffeefc15928）”。

标签： c++arrays

解决方案

您的功能存在一些问题smallsort。

  1. 该count数组包含输入的每个值的频率。并且您将频率分配给nums[a].

  2. 外部for循环（nums数组被重新填充的地方）必须遍历所有count数组，因为输入值可以是 0 到 9999 之间的任何值。

通过这些修改，代码将如下所示：

void smallSort(int nums[], int length){
    int count [10000] = {0}; //This will set all array elements to 0
    int a = 0;

    for(int i =0; i<length ; i++){
        count[nums[i]]++;   
    }
    for(int i = 0; i< 10000; i++){
        for(int j = 0; j<count[i]; j++){
            nums[a] = i;
            a++;
        }
    }
}

int main(int argc, char const *argv[])
{
    int nums[] = {0, 1210, 3000,2434,446,54,111,900,43,7,17,1001,9999,0,0,9999,1210,54};
    smallSort(nums, 18);

    for(auto& i: nums)
        cout << i << ' ';       

    return 0;
}

输出： 

a.exe
0 0 0 7 17 43 54 54 111 446 900 1001 1210 1210 2434 3000 9999 9999

推荐阅读