在C++中實(shí)現(xiàn)無比較排序可以使用基數(shù)排序或桶排序這兩種算法。以下是使用基數(shù)排序?qū)崿F(xiàn)無比較排序的示例代碼:
#include <iostream>
#include <vector>
void countingSort(std::vector<int>& arr, int exp) {
std::vector<int> output(arr.size());
int count[10] = {0};
for (int i = 0; i < arr.size(); i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = arr.size() - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < arr.size(); i++) {
arr[i] = output[i];
}
}
void radixSort(std::vector<int>& arr) {
int max = *std::max_element(arr.begin(), arr.end());
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
int main() {
std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
在上面的示例代碼中,使用基數(shù)排序?qū)崿F(xiàn)了對(duì)一個(gè)數(shù)組進(jìn)行無比較排序?;鶖?shù)排序是一種非比較排序算法,它根據(jù)數(shù)字的位數(shù)進(jìn)行排序,不需要進(jìn)行元素之間的比較。