(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つはいわゆるバケツです.
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