如何修改计数排序算法实现从大到小排序（禁止事后反转数组）

Got it, let's figure out how to adjust counting sort to sort in descending order without reversing the array at the end—this is totally achievable by tweaking how we handle the count array and position elements in the output. Here's a complete, fixed version of your code with the necessary changes, plus explanations of what was adjusted:

#include<iostream>
#include<stdio.h>
#include<time.h>
using namespace std;

int main() {
    int n;
    int k;
    cout << "Number of elements: ";
    cin >> n;
    cout << "Max number (k): ";
    cin >> k;

    int tab[n];
    cout << "Enter the elements: ";
    for (int i = 0; i < n; i++) {
        cin >> tab[i];
    }

    // Counting sort modified for descending order
    int count[k + 1] = {0}; // Initialize all counts to 0

    // Step 1: Count frequency of each element (same as ascending sort)
    for (int i = 0; i < n; i++) {
        count[tab[i]]++;
    }

    // Step 2: Compute REVERSE prefix sum (key change for descending order)
    // This calculates how many elements are >= current value, giving us positions
    for (int i = k - 1; i >= 0; i--) {
        count[i] += count[i + 1];
    }

    // Step 3: Build the output array using the reverse prefix sums
    int output[n];
    for (int i = 0; i < n; i++) {
        // Place the element at its correct descending position
        output[count[tab[i]] - 1] = tab[i];
        count[tab[i]]--; // Decrement count to handle duplicates
    }

    // Copy sorted output back to original array
    for (int i = 0; i < n; i++) {
        tab[i] = output[i];
    }

    // Print the result
    cout << "Sorted array (descending): ";
    for (int i = 0; i < n; i++) {
        cout << tab[i] << " ";
    }
    cout << endl;

    return 0;
}

What Changed (And Why) #

• Fixed Input Order: First, I corrected the initial input flow—your original code was printing the number of elements before reading it, which would show garbage values. That's a small bug fix to make the code usable.
• Reverse Prefix Sum: The biggest change is how we calculate the prefix sum in the count array. Instead of starting from the smallest value and adding forward (which gives positions for ascending sort), we start from the second-largest value and add backward. This makes count[i] represent how many elements are greater than or equal to i—exactly what we need to place elements in descending order.
• Direct Positioning: When building the output array, we use these reverse prefix sums to place each element directly into its correct spot in the descending sorted array. Each time we place an element, we decrement its count to ensure duplicates are placed in the right consecutive positions.

This approach ensures the sort happens entirely within the algorithm logic—no need to reverse the array after sorting, as we're constructing the descending order from the start.

内容的提问来源于stack exchange，提问作者Jasiu