时间戳

首页 > 解决方案 > 排序 0 ,1 和 2 的数组

c++ - 排序 0 ,1 和 2 的数组

问题描述

我的代码有什么问题，为什么它没有给出正确的输出？

输入

84
1 0 1 2 1 1 0 0 1 2 1 2 1 2 1 0 0 1 1 2 2 0 0 2 2 2 1 1 1 2 0 0 0 2 0 1 1 1 1 0 0 0 2 2 1 2 2 2 0 2 1 1 2 2 0 2 2 1 1 0 0 2 0 2 2 1 0 1 2 0 0 0 0 2 0 2 2 0 2 1 0 0 2 2

它的正确输出是：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

你的代码的输出是：

0-36092119132636100007056629140-858993460214748364-...

#include<iostream>
#include<algorithm>
using namespace std;

void sortArray(int *arr,int n){
    int low=0,mid=1,high=n-1;
    while(mid<=high){
        if(arr[mid]==1){
            mid++;
        }
        else if(arr[mid]==2){
            swap(arr[mid],arr[high]);
            high--;
        }
        else{
            swap(arr[mid],arr[low]);
            mid++,low++;
        }
    }
    for(int i=0;i<n;i++){
        cout<<arr[i];
    }
}
int main()
 {
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[n];
        }
        sortArray(arr,n);
    }
    return 0;
}

标签： c++arraysalgorithmsorting

解决方案

主要问题在于您的输入阅读：

for(int i=0;i<n;i++) {
        cin>>arr[n];
}

您正在阅读arr[n]which is undefined。您想i用作索引：

for(int i=0;i<n;i++) {
        cin>>arr[i];
}

由于数组将只包含 0、1 或 2，因此您也可以简化排序算法：

void sortArray(int *arr, size_t n)
{
    size_t count[3] = {0};

    for (size_t i = 0; i < n; ++i) {
       count[arr[i]]++;
    }

    size_t k = 0;
    for (size_t i = 0; i < 3; ++i) {
        for (size_t j = 0; j < count[i]; ++j)
            arr[k++] = i;
    }

    for (size_t i = 0; i < n; ++i)
        std::cout << arr[i] << ' ';

    std::cout << endl;
}

注意：您使用的是非标准扩展。C++ 标准没有 VLA（可变长度数组）。

可变长度数组通常分配在“堆栈”上，并且容易发生堆栈溢出。如果数组的长度太大，您将有未定义的行为。更糟糕的是，您也不能轻易知道数组的“正确”大小。因此，最好避免使用 VLA。你可以std::vector<int>改用。

推荐阅读