基数排序

基数排序：先按照最低位进行排序，然后对倒数第二位，以此类推。基于计数排序的基础上的一种排序方法。属于稳定排序，时间复杂度O（n），以空间换时间，需要额外的辅助空间。

计数排序：假设n个输入元素的每一个都是在0到k区间内的一个整数，其中k是一个整数。运行时间是O（n）.

计数排序的基本思想是：对每一个输入元素x,确定小于x的元素个数，从而，直接把x放在它输出数组中的位置。

计数排序伪代码：

CountingSort( A, B, k ) // A：输入数组； B输出数组；k 数组元素最大值

　　C[ k ] = { 0 }

　　for j = 1 to A.length

C[A[j]] = C[A[j]] + 1 // 统计数组中某一元素的个数

　 for i = 2 to k

　　 C[ i ] = C[ i ] + C[ i - 1 ] // 计算数组中小于C[i] 的元素的个数

　　for j = A.length downto 1

　　 B[ C[ A[ j ] ] ] = A[ j ] //注：在代码中，我在这里是先进行：C[A[j]] = C[A[j]] - 1 ，然后 B[C[A[j]]] = A[j] 。C[A[j]] 的最大值是 A.length，会超出数组B的下标范围。

　　 C[ A[ j ] ] = C[ A[ j ] ] - 1

计数排序代码：

#include<iostream>
#include<vector>
using namespace std;
vector<int> CountingSort(vector<int>A,int Max,int  Number)   //参数： K，最大数值; Number 数组中元素个数
{
    int max = Max + 1;
    vector<int> B(Number);
    vector<int>C(max, 0);
    
    for (int i = 0; i < Number; i++)
        C[A[i]] ++;

    for (int i = 1; i < max; i++)
        C[i] += C[i - 1];
    
    for (int j = Number - 1; j >= 0; j--)
    {
        C[A[j]]--;
        B[C[A[j]]] = A[j];
    }
    return B;
}

测试代码：

int main()
{
    vector<int> arry = { 21, 97, 9, 1, 5, 8, 19, 4, 7, 10, 15, 17, 21, 41, 51, 61, 81, 71, 91, 100 };
    cout << "排序前" << endl;
    for (int i = 0; i < 20; i++)
        cout << arry[i] << " ";
    cout << endl;
    int Max = 100;
    int Number = 20;
    vector<int>B = CountingSort(arry, Max, Number);
    for (int i = 0; i < 20; i++)
        cout << B[i] << " ";
    cout << endl;
    cout << "BigThink" << endl;
    system("pause");
    return 0;
}

View Code

基数排序：

RadixSort(A,d) // A 是输入数组，d是数组中最大值的位数

for i=1 to d

使用稳定排序法对A中数组的第 i位进行排序

基数排序代码：

#include<iostream>
#include<vector>
using namespace std;
//求取输入输入的最大数字的位数
int GetInt(vector<int>A,int Number)    //Number 输入数组个数
{
    int d = 1;
    int Max = A[0];
    for (int i = 0; i < Number; i++)
        if (A[i]>Max)
            Max = A[i];
    while (Max > 10)
    {
        Max = Max / 10;
        d++;
    }
    return d;
}

//基数排序法
vector<int> Radix_Sort(vector<int>A, int Number)     //参数 d 最大元素值的位数,Number是数组中元素个数
{
    int d = GetInt(A, Number);
    vector<int>B(Number);
    int radix = 1;
    for (int i = 1; i <= d; i++)
    {
        vector<int> Arry(Number, 0);
        vector<int> C(10, 0);
        for (int j = 0; j < Number; j++)
        {
            Arry[j] = (A[j] / radix) % 10;
            C[Arry[j]]++;
        }
        for (int j = 1; j < 10; j++)
            C[j] += C[j - 1];
        for (int j = Number - 1; j >= 0; j--)
        {
            B[C[Arry[j]]-1] = A[j];
            C[Arry[j]]--;
        }
        for (int j = 0; j < Number; j++)
            A[j] = B[j];
        radix = radix * 10;
    }
    return B;
}

测试代码：

int main()
{
    vector<int>arry = { 3, 7, 9, 14, 25, 52, 36, 78, 95, 28, 11, 32, 24, 250, 620, 140, 8, 91, 20,620 };
    cout << "排序前" << endl;
    for (int i = 0; i < 20; i++)
        cout << arry[i] << " ";
    cout << endl;
    vector<int>B =  Radix_Sort(arry, 20);
    cout << "排序后：" << endl;
    for (int i = 0; i < 20; i++)
        cout << B[i] << " ";
    cout << endl;
    cout << "BigThink" << endl;
    system("pause");
    return 0;
}

View Code