改变基数排序基数?
changing radix-sort base?
我试图理解基数排序,但在理解实现实际代码时改变基数时遇到问题。这是我用来学习基数排序的代码,我会尝试解释我不明白的地方。
此代码由 GeeksForGeeks 提供:
// C++ implementation of Radix Sort
#include<iostream>
using namespace std;
// A utility function to get maximum value in arr[]
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
int output[n]; // output array
int i, count[10] = {0};
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains actual
// position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// A utility function to print an array
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver program to test above functions
int main()
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr)/sizeof(arr[0]);
radixsort(arr, n);
print(arr, n);
return 0;
}
所以我遇到的一个问题是我需要有一个可变基数基数排序,用户可以在其中选择他的基数。我的理解是,基数只是函数的表示,但不确定如何将其实现为基数排序。如果我继续使用基数 10,它将如何影响排序算法(复杂性之外)?
您的代码是以 10 为基数的。每次您在代码中看到硬编码的 10 以 10 为基数时,要更改它,您需要使每次出现都是动态的。
基数排序的复杂度不依赖于基数,它总是 O(kn) [键的长度 * 键的 n]。更改基数有助于减少进行排序所需的传递次数,但会增加每次传递中计算的桶数。除此之外,任何碱基都会排序并产生相同的结果。
我遇到了这个问题,它没有正确答案,现在有。
首先是一些注意事项:
这可能不是 Radix 的最佳算法,但它是问题的答案。
//b is the base you want
//exp is the value used for the division
void counting_sort(int* A, int n, int exp, int b) {
int * C = new int[b];
int* B = new int[n];
for (int i = 0; i < b; i++)
{
C[i] = 0;
}
for (int i = 0; i < n; i++)
{
C[(A[i] / exp) % b]++;
}
for (int i = 1; i < b; i++)
{
C[i] += C[i - 1];
}
for (int i = n - 1; i >= 0; i--)
{
B[C[(A[i] / exp) % b] - 1] = A[i];
C[(A[i] / exp) % b]--;
}
for (int i = 0; i < n; i++)
{
A[i] = B[i];
}
delete[] B;
delete[] C;
}
int getMax(int* A, int n) {
int max = A[0];
for (int i = 1; i < n; i++) {
if (A[i] > max) {
max = A[i];
}
}
return max;
}
void radix_sort(int* A, int n) {
long long max = (long long)getMax(A, n);
long long base = 8// whatever base you need, I used ll, since long wasn't big enough for my needs (n = 200000).
for (long long exp = 1; max / exp > 0; exp *= base) {
counting_sort(A, n, exp, base);
}
}
基本上就是这些,但我会添加基数 2^(log n)
的代码
long long getBase(int* A, int n) {
long long log = (long long) log2(n);
return (long long)pow(2, log);
}
void radix_sort(int* A, int n) {
long long max = (long long)getMax(A, n);
long long base = getBase(A, n);
for (long long exp = 1; max / exp > 0; exp *= base) {
counting_sort(A, n, exp, base);
}
}
如果阅读本文的人有任何疑问,请查看我的个人资料。
我试图理解基数排序,但在理解实现实际代码时改变基数时遇到问题。这是我用来学习基数排序的代码,我会尝试解释我不明白的地方。
此代码由 GeeksForGeeks 提供:
// C++ implementation of Radix Sort
#include<iostream>
using namespace std;
// A utility function to get maximum value in arr[]
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
int output[n]; // output array
int i, count[10] = {0};
// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains actual
// position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}
// The main function to that sorts arr[] of size n using
// Radix Sort
void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);
// Do counting sort for every digit. Note that instead
// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
// A utility function to print an array
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver program to test above functions
int main()
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr)/sizeof(arr[0]);
radixsort(arr, n);
print(arr, n);
return 0;
}
所以我遇到的一个问题是我需要有一个可变基数基数排序,用户可以在其中选择他的基数。我的理解是,基数只是函数的表示,但不确定如何将其实现为基数排序。如果我继续使用基数 10,它将如何影响排序算法(复杂性之外)?
您的代码是以 10 为基数的。每次您在代码中看到硬编码的 10 以 10 为基数时,要更改它,您需要使每次出现都是动态的。
基数排序的复杂度不依赖于基数,它总是 O(kn) [键的长度 * 键的 n]。更改基数有助于减少进行排序所需的传递次数,但会增加每次传递中计算的桶数。除此之外,任何碱基都会排序并产生相同的结果。
我遇到了这个问题,它没有正确答案,现在有。
首先是一些注意事项:
这可能不是 Radix 的最佳算法,但它是问题的答案。
//b is the base you want
//exp is the value used for the division
void counting_sort(int* A, int n, int exp, int b) {
int * C = new int[b];
int* B = new int[n];
for (int i = 0; i < b; i++)
{
C[i] = 0;
}
for (int i = 0; i < n; i++)
{
C[(A[i] / exp) % b]++;
}
for (int i = 1; i < b; i++)
{
C[i] += C[i - 1];
}
for (int i = n - 1; i >= 0; i--)
{
B[C[(A[i] / exp) % b] - 1] = A[i];
C[(A[i] / exp) % b]--;
}
for (int i = 0; i < n; i++)
{
A[i] = B[i];
}
delete[] B;
delete[] C;
}
int getMax(int* A, int n) {
int max = A[0];
for (int i = 1; i < n; i++) {
if (A[i] > max) {
max = A[i];
}
}
return max;
}
void radix_sort(int* A, int n) {
long long max = (long long)getMax(A, n);
long long base = 8// whatever base you need, I used ll, since long wasn't big enough for my needs (n = 200000).
for (long long exp = 1; max / exp > 0; exp *= base) {
counting_sort(A, n, exp, base);
}
}
基本上就是这些,但我会添加基数 2^(log n)
的代码long long getBase(int* A, int n) {
long long log = (long long) log2(n);
return (long long)pow(2, log);
}
void radix_sort(int* A, int n) {
long long max = (long long)getMax(A, n);
long long base = getBase(A, n);
for (long long exp = 1; max / exp > 0; exp *= base) {
counting_sort(A, n, exp, base);
}
}
如果阅读本文的人有任何疑问,请查看我的个人资料。