变长数据项的排序 算法导论8.3 8.3.4(e)

第一步，先按数据的长度排序，计算出数据的长度（一般大小为正整数），然后按计数排序的方法排序

第二步，对相同长度的数据进行基数排序。基数排序采用计数排序作为稳定排序。

这里遇到了一个问题， 第二问对字符串按字典序排列(a<ab<b)，这样的话按上面的方法就有问题，因为这个方法先按字符串长度划分字符串数组，排序之后是(a,b,ab)，不知道怎么用这个章节的方法解题（知道可以用trie）?

debug总结：

1) 参数取名很重要，temp和temp1搞混就会程序崩溃，所以名字需要易于辨别和理解

2) 如果岔开了思路，待会再继续的话最好重新理一遍。

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 10;
const int M = 26;
//计数排序假设输入的元素都是0-k之间的整数，k为自然数
void Counting_Sort_Origin(int *a,int n, int *b, int k){
    int *p = new int[k+1];             //new int[k+1]() 值初始化，所以的都为0.
    for (int i = 0; i < k + 1; ++i)    //内置类型默认初始化的值是不确定的。
        p[i] = 0;
    for (int i = 0; i < n; ++i){
        ++p[a[i]];
    }
    for (int i = 1; i < k + 1; ++i)
        p[i] += p[i - 1];
    for (int i = n-1; i >= 0; --i){
        b[p[a[i]]-1] = a[i]; 
        --p[a[i]];
    }
    delete []p;
}

void Exer_834(int *a,int *b,int *c, int n){
    int *p = new int[n]();//计数数组
    //三次循环，把整数看成3位数，每位从0到n-1
    for (int m = 0; m < 3; ++m){
        //每个数可以拆为三个关键字，每个关键词进行计数排序
        for (int i = 0; i < n; ++i){
            c[i] = (a[i] / (int)pow(n, m)) % n;
        }
        cout << endl;
        for (int i = 0; i < n; ++i){
            p[i] = 0; 
        }
        for (int i = 0; i < n; ++i){
            ++p[c[i]];
        }
        for (int i = 1; i < n; ++i)
            p[i] += p[i - 1];
        for (int i = n - 1; i >= 0; --i){
            b[p[c[i]] - 1] = a[i];
            --p[c[i]];
        }
        for (int i = 1; i < n; ++i)
            a[i] = b[i];
    }
    delete[]p;
}
//原址版计数排序，但是不稳定
void O_Counting_S(int *a,int n,int k){
    int *p = new int[k + 1]();
    int *loc = new int[k + 1]();
    for (int i = 0; i < n; ++i){
        ++p[a[i]];
    }
    for (int i = 1; i < k + 1; ++i){
        p[i] += p[i - 1];
        loc[i] = p[i];
    }
    //for (int i = 0; i < 10; i++)
    //    cout << p[i] << " ";
    int count = 0;
    while(count<n){
        if (p[a[count] - 1] <= count&&count < p[a[count]])
            ++count;
        else{
            int temp = a[count];
            swap(a[count], a[loc[a[count] - 1]]);
            ++loc[temp-1];
        }
    }
}


int Bits(int num);
int Nth_digit(int num, int i);

//基数排序中的计数排序模块，多一个参数表示依据哪个位在排序
//这里把每个位可能取值的可能性省去，用全局变量N表示，即为10
void Counting_Sort(int *a, int n,int ith){
    int *p = new int[N]();             
    int *temp = new int[n];
    int *temp1 = new int[n];
    for (int i = 0; i < n; ++i)  { temp[i] = a[i]; }   //copy数组
    for (int i = 0; i < n; ++i)  { temp1[i] = Nth_digit(a[i], ith); }
    for (int i = 0; i < n; ++i)  {++p[temp1[i]]; }
    for (int i = 1; i < N; ++i)  { p[i] += p[i - 1]; }
        
    for (int i = n - 1; i >= 0; --i){
        a[p[temp1[i]] - 1] = temp[i];
        --p[temp1[i]];
    }
    delete[]p;
    delete[]temp;
    delete[]temp1;
}


void Radix_Sort(int *a, int n, int k){
    if (n == 0)
        return;
    for (int i = 0; i < k; ++i){
        Counting_Sort(a, n,i);
    }
}

void Partition_Bybit(int *a,int n,int *group,int k){
    int *temp = new int[n];
    int *temp1 = new int[n];
    int *p = new int[k + 1]();
    for (int i = 0; i < n; i++)      {temp[i] = Bits(a[i]);}
    for (int i = 0; i < n; ++i)      { ++p[temp[i]]; }
    for (int i = 1; i < k + 1; ++i)  { p[i] += p[i - 1]; }
    for (int i = 0; i < k + 1; ++i)  { group[i] = p[i]; }
    for (int i = 0; i < n; ++i)      { temp1[i] = a[i]; }

    for (int i = n-1; i >=0; --i){
        a[p[temp[i]] - 1] = temp1[i];
        --p[temp[i]];
    }
    delete[]p;
    delete[]temp;
    delete[]temp1;
}


void Ex_83_a(int *a, int n){
    int *temp = new int[n];
    int max_bit = 0;
    for (int i = 0; i < n; i++){
        temp[i] = Bits(a[i]);
        if (temp[i]>max_bit)
            max_bit = temp[i];
    }
    int *group = new int[max_bit + 1]();
    Partition_Bybit(a, n, group, max_bit);
    for (int i = 0; i < max_bit;++i){
        Radix_Sort(a + group[i], group[i + 1] - group[i], i+1);
    }
}
//把每个数字的位数记录下来

int Nth_digit(int num,int i){
    return (num / (int)pow(N, i)) % N;
}


int Bits(int num){
    int count = 1;
    while (num / 10){
        ++count;
        num /= 10;
    }
    return count;
}

void Counting_Sort_S(int *a, int n, int *b, int ith){
    int *p = new int[N]();
    int *temp = new int[n];
    int *temp1 = new int[n];
    for (int i = 0; i < n; ++i)  { temp[i] = a[i]; }   //copy数组
    for (int i = 0; i < n; ++i)  { temp1[i] = Nth_digit(a[i], ith); }
    for (int i = 0; i < n; ++i)  { ++p[temp1[i]]; }
    for (int i = 1; i < N; ++i)  { p[i] += p[i - 1]; }

    for (int i = n - 1; i >= 0; --i){
        a[p[temp1[i]] - 1] = temp[i];
        --p[temp1[i]];
    }
    delete[]p;
    delete[]temp;
    delete[]temp1;
}


int main(){
    int a[15] = { 555, 444, 333, 222, 111,5, 4, 3, 2, 1, 11, 22, 33, 44, 55 };

    Ex_83_a(a, 15);

    for (int i = 0; i < 15; i++)
    cout << a[i]<<" ";

}