c++中的 Sort Count.我怎样才能跳过排序的一部分?

Question

我有以下排序的例子(Count Sort)，它实际上有点奇怪，但它工作，所以它是好的:

#include<iostream>
using namespace std;
int getMx(int* arr,int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}       
}
return max;
}
void CountSort(int* arr, int n) {
int* output = new int[n];
int max = getMx(arr, n);
int* count = new int[max + 1];
for(int i = 0; i < max + 1; i++) {
count[i] = 0;
}
for(int i = 0; i < n; i++) {
count[arr[i]]++;
}
for(int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
for(int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for(int i = 0; i < n; i++) {
arr[i] = output[i];
}

delete[] output;
delete[] count;
}
int main () {
int arr[] = { 100, 5, 2, 0, 125 };
int n = sizeof(arr) / sizeof(arr[0]);
CountSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << endl;
}
return 0;
}

所以主要的想法是当我在Count[I]上对每个索引中存储的数字求和时，去掉部分。并得到第二个循环后的输出

例子int arr = [3, 2, 5, 4, 1, 0]
int count=[1,1,1,1,1,1]

，然后得到

int output= [0, 1, 2, 3, 4, 5]

所以我不明白(

Answer 1

你可能在想这样的事情:

void CountSort(int* arr, int n) {
int max = getMx(arr, n);
int* count = new int[max + 1]{};
for(int i = 0; i < n; i++) {
count[arr[i]]++;
}
int k = 0;
for(int i = 0; i <= max; i++) {
while (count[i]--) {
arr[k++] = i;
}
}
delete[] count;
}

演示