已知一个含有n个记录的序列，其关键字均为介于0和n2之间的整

已知一个含有n个记录的序列，其关键字均为介于0和n2之间的整数。若利用堆排序等方法进行排序，则时间复杂度为O(nlogn)。如果将每个关键字Ki认作Ki =Ki1n+Ki2，其中Ki1和Ki2都是范围[0, n)中的整数，则利用基数排序只需用O(n)的时间。推广之，若整数关键字的范围为[0, nk)，则可得到只需时间O(kn)的排序方法，试讨论如何实现之。