不同長度數據項的排序

注：本文改編自windmissing博客，感謝作者整理！

?

題目：

a)給定一個整數數組，其中不同的整數中包含的數字個數可能不同，但是該數組中，所有整數中總的數字數為n。說明如何在O(n)時間內對該數組進行排序

b)給定一個字符串數組，其中不同的串包含的字符個數可能不同，但所有串中總的字符個數為n。說明如何在O(n)時間內對該數組進行排序

（注意此處的順序是指標準的字母順序，例如，a < ab < b）

?

a)先用桶排序方法按數字位數排序O(n)，再用基數排序的方法分別對每個桶中的元素排序O(n)

b)遞歸使用計數排序，先依據第一個字母進行排序，首字相同的放在同一組，再對每一組分別使用計數排序的方法比較第二個字母

見到有人用字典樹，也是可以的

//8-2-a
#include <iostream>
#include <cmath>
using namespace std;

int length_A;
void Print(int *A)
{
  int i;
  for(i = 1; i <= length_A; i++)
      cout<<A[i]<<' ';
  cout<<endl;
}

int Digit(int x)
{
  int ret = 0;
  while(x)
  {
     ret++;
     x = x / 10;
  }

  return ret;
}


//基數排序調用的穩定排序
void Counting_Sort(int *A, int *B, int k)
{
    int i, j;
    //將C數組初始化為0，用于計數
    int *C = new int[k+1];
    for(i = 0; i <= k; i++)
        C[i] = 0;
    int *D = new int[length_A+1];
    for(j = 1; j <= length_A; j++)
    {
        //D[j]表示第[j]個元素有i位數字
        D[j] = Digit(A[j]);
        //C[j]表示數字D[j]在數組A中出現的次數
        C[D[j]]++;
    }
    //C[i]表示所以<=i的數字出現過的次數
    for(i = 1; i <= k; i++)
        C[i] = C[i] + C[i-1];
    //初始化B為0，B用于輸出排序結果
    for(i = 1; i <= length_A; i++)
        B[i] = 0;
    for(j = length_A; j >= 1; j--)
    {
        //如果<=D[j]的數字的個數是x,那么排序后A[j]應該出現在第x個位置，即B[x]=A[j]
        B[C[D[j]]] = A[j];
        C[D[j]]--;
    }
    delete []C;
    delete []D;
}
//基數排序調用的穩定排序
void Stable_Sort(int *A, int *B, int k, int d,int start, int end)
{
    int i, j, radix = 10;
    //將C數組初始化為0，用于計數
    int *C = new int[k+1];
    for(i = 0; i <= k; i++)
        C[i] = 0;
    int *D = new int[length_A+1];
    for(j = start; j <= end; j++)
    {
        //D[j]表示第[j]個元素的第i位數字
        D[j] = A[j] % (int)pow(radix*1.0, d) / (int)pow(radix*1.0, d-1);
        //C[j]表示數字D[j]在數組A中出現的次數
        C[D[j]]++;
    }
    //C[i]表示所以<=i的數字出現過的次數
    for(i = 1; i <= k; i++)
        C[i] = C[i] + C[i-1];
    //初始化B為0，B用于輸出排序結果
    for(i = 1; i <= length_A; i++)
        B[i] = 0;
    for(j = end; j >= start; j--)
    {
        //如果<=D[j]的數字的個數是x,那么排序后A[j]應該出現在第x個位置，即B[x]=A[j]
        B[C[D[j]]+start-1] = A[j];
        C[D[j]]--;
    }
    delete []C;
    delete []D;
}
void Radix_Sort(int *A, int *B, int k ,int digit, int start, int end)
{
    int i, j;
    //依次對每一位進行排序，從低位到高位
    for(i = 1; i <= digit; i++)
    {
        Stable_Sort(A, B, k, i, start, end);
        //輸入的是A，輸出的是B，再次排序時要把輸出數據放入輸出數據中
        for(j = start; j <= end; j++)
        A[j] = B[j];
    }
}
int main()
{
    cin>>length_A;
    int i;
    //產生隨機的測試數據
    int *A = new int[length_A+1];
    for(i = 1; i <= length_A; i++)
        A[i] = rand() % (int)pow(10.0, rand()%5+1);
    Print(A);
    int *B = new int[length_A+1];
    //先進行計數排序，把長度相同的數字排在一起
    Counting_Sort(A, B, 5);
    for(i = 1; i <= length_A; i++)
        A[i] = B[i];
    Print(A);
    int start, end, digit = -1;
    for(i = 1; i <= length_A; i++)
    {
        if(digit == -1)
        {
            digit = Digit(A[i]);
            start = i;
            end = i;
        }
        else
        {
            if(Digit(A[i]) == digit)
                end = i;
            else
            {
                //找到位數相同的一段，從start到end，單獨對這一段進行基數排序
                Radix_Sort(A, B, 9, digit, start, end);
                i--;
                digit = -1;
                Print(A);
            }
        }
    }
    delete []A;
    delete []B;
}

#include <iostream>
#include <string>
using namespace std;

int length_A;
void Print(string *A)
{
    int i;
    for(i = 1; i <= length_A; i++)
        cout<<A[i]<<' ';
    cout<<endl;
}
//基數排序調用的穩定排序，A是輸入，B是中間輸出，C是計數，d表示對第d位字母排序，start和end分別是排序段的起點和終點
void Counting_Sort(string *A, string *B, int *C, int d, int start, int end)
{
    if(start == end)
        return;
    int i, j;
    //將C數組初始化為0，用于計數
    for(i = 0; i <= 26; i++)
        C[i] = 0;
    int *D = new int[length_A+1];
    for(j = start; j <= end; j++)
    {
        //D[j]表示第[j]個元素的第i位數字
        if(A[j].length() <= d)
            D[j] = 0;
        else
            D[j] = A[j][d] - 'a';
        //C[j]表示數字D[j]在數組A中出現的次數
        C[D[j]]++;
    }
    //C[i]表示所以<=i的數字出現過的次數
    for(i = 1; i <= 26; i++)
        C[i] = C[i] + C[i-1];
    //初始化B為0，B用于輸出排序結果
    for(i = 1; i <= length_A; i++)
        B[i] = "";
    for(j = end; j >= start; j--)
    {
        //如果<=D[j]的數字的個數是x,那么排序后A[j]應該出現在第x個位置，即B[x]=A[j]
        B[C[D[j]]+start-1] = A[j];
        C[D[j]]--;
    }
    delete []D;
    //輸出轉為輸入
    for(i = start; i <= end; i++)
        A[i] = B[i];
    char c = 'A';
    int s, e;//進一步的排序以s為起點，e為終點
    //對于排序的這一段，對下一個字母遞歸使用計數排序
    for(i = start; i <= end; i++)
    {
        //如果長度為d，不參與下一步排序
        if(A[i][d] == '\0')
            continue;
        if(c == 'A')
        {
            s = i;
            e = i;
            c = A[i][d];
        }
        else
        {
            if(A[i][d] == c)
            {
                e = i;
                if(e == end)
                    //以第d+1位字母為依據，對s-e段進行計數排序
                    Counting_Sort(A, B, C, d+1, s, e);
            }
            else
            {
                //以第d+1位字母為依據，對s-e段進行計數排序
                Counting_Sort(A, B, C, d+1, s, e);
                i--;
                c = 'A';
            }
        }
    }
}
int main()
{
    int i, j;
    cin>>length_A;
    string *A = new string[length_A+1];
    //構造隨機數據
    for(i = 1; i <= length_A; i++)
    {
        int len = rand()%5+1;
        for(j = 1; j <= len; j++)
            A[i] = A[i] + (char)(rand()%26+'a');
    }
    Print(A);
    string *B = new string[length_A+1];
    int *C = new int[26];
    //計數排序
    Counting_Sort(A, B, C, 0, 1, length_A);
    Print(A);
    delete []A;
    delete []C;
    return 0;
}

?