(C言語)8大ソート之:基数ソート

1655 ワード

reference:ベースソートhttp://blog.csdn.net/hitwhylz/article/details/9970451
8つのソートhttps://www.cnblogs.com/RainyBear/p/5258483.html
基数ソートradixSort:バケツbucketで割り当て、収集を行います.
バケツ:0-9 10バケツ
割当て:1ビットから0~9バケツにデータを割当てます.
収集:0~9バレルのデータを元の配列に順次収集します.
時間複雑度:O(d(r+n))空間複雑度:O(rd+n).
ここで、nはキーワードの個数、dはキーワードの最大長、rはキーワードの基数であるバケツの数である
基数ソートの空間複雑度が高く、2つの配列の空間オーバーヘッドがあります.1つはソート対象の配列を格納し、1つはいわゆるバケツです.
  1 #include 
  2 #include 
  3 
  4 void radixSort(int a[], int len);
  5 void display(int a[], int len);
  6 
  7 int main(void)
  8 {
  9         int a[] = {8,4,2,3,5,1,6,9,0,7};
 10         int len = sizeof(a)/sizeof(a[0]);
 11         radixSort(a, len);
 12 
 13         display(a, len);
 14         return 0;
 15 }
 16 //          
 17 int maxlength(int a[], int len)
 18 {
 19         int bits = 1, p = 10, i;
 20         for(i=0; i=p)
 23                 {
 24                         p = p * 10;
 25                         bits++;
 26                 }
 27         }
 28         return bits;
 29 }
 30 
 31 //   num  pos    ,pos=1   
 32 int getdigit(int num, int pos)
 33 {
 34         int temp = 1, i;
 35         for(i=0; i