How to use radix sort algorithm in C++

How to use the radix sorting algorithm in C

The radix sorting algorithm is a non-comparative sorting algorithm that divides the elements to be sorted into a finite set of digits to complete the sorting. In C, we can use the radix sort algorithm to sort a set of integers. Below we will discuss in detail how to implement the radix sort algorithm, with specific code examples.

1. Algorithm idea
   The idea of ​​the radix sorting algorithm is to divide the elements to be sorted into a limited set of digital bits, and then sort the elements on each bit in turn. After the sorting on each bit is completed, the elements are reorganized according to the order of that bit, and then the sorting of the next bit is continued until all bits are sorted.
2. Specific implementation steps
   (1) First, we need to determine the number of digits in the maximum value among all elements to be sorted. This will determine how many rounds of sorting we need to do.

(2) Then, we need to create an auxiliary array and a count array. The auxiliary array is used to store temporary results during the sorting process, and the counting array is used to record the number of occurrences of each number.

(3) Next, we need to perform multiple rounds of sorting. Each round of sorting reorganizes the array according to the current bit size.

(4) In each round of sorting, we need to traverse the array to be sorted, use the current bit value of each element as an index, and put the elements into the corresponding bucket.

(5) Then, we need to count the number of elements in each bucket, which can be recorded using a counting array.

(6) Next, we need to determine the position of the elements in each bucket in the auxiliary array by counting the array. This can be determined by counting the prefix sum of elements in the array.

(7) Finally, we overwrite the elements in the auxiliary array into the array to be sorted to complete a round of sorting.

(8) Repeat steps (3) to (7) until all bits are sorted.

3. Code example
   The following is a code example that uses C to implement the radix sorting algorithm:

#include <iostream>
#include <vector>

using namespace std;

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    int digit = 1;
    vector<int> temp(arr.size());
    while (maxVal / digit > 0) {
        vector<int> count(10, 0);

        for (int i = 0; i < arr.size(); i++) {
            count[(arr[i] / digit) % 10]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = arr.size() - 1; i >= 0; i--) {
            temp[count[(arr[i] / digit) % 10] - 1] = arr[i];
            count[(arr[i] / digit) % 10]--;
        }

        for (int i = 0; i < arr.size(); i++) {
            arr[i] = temp[i];
        }

        digit *= 10;
    }
}

int main() {
    vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    radixSort(arr);

    cout << "排序结果：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

In the above example code, we first find the array to be sorted The maximum value to determine how many rounds of sorting are required. Then we created an auxiliary array and a count array. Next, we perform multiple rounds of sorting to reassemble the array according to the current bit size. Finally, we output the sorted results.

Summary:
Through the radix sorting algorithm, we can sort a set of integers in C. The core idea of ​​the radix sorting algorithm is to divide the elements to be sorted into a limited set of numerical bits, and then sort the elements on each bit in turn. This non-comparative sorting algorithm can effectively handle the sorting problem of a set of integers.

The above is the detailed content of How to use radix sort algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!