桶排序

  1 #include<iostream>
  2 using namespace std;
  3 
  4 struct node
  5 {
  6     node *next;
  7     double n;
  8 };
  9 
 10 
 11 struct list
 12 {
 13     node *head;
 14     int n = 0;
 15 };
 16 
 17 void addlist(list *t, double i)
 18 {
 19     if (t->n == 0)
 20     {
 21         t->head = new node;
 22         t->head->n = i;
 23         t->head->next = NULL;
 24         t->n++;
 25     }
 26     else
 27     {
 28         node *x = new node;
 29         x->n = i;
 30         x->next = t->head;
 31         t->head = x;
 32         t->n++;
 33     }
 34 }
 35 
 36 
 37 void insertion(list *b)
 38 {
 39     int flag = 1;
 40     if (b->n < 2)
 41         ;
 42     else
 43     {
 44         node *m1;
 45         node *m=b->head;
 46         node *q = b->head->next;
 47         node *p = b->head;
 48         while (flag)
 49         {
 50             if (q->next == NULL)
 51                 flag = 0;
 52             double t = q->n;
 53             while (p->n < t)
 54             {
 55                 if (p == b->head)
 56                 {
 57                     m1 = b->head;
 58                 }
 59                 else m1 = m1->next;
 60                 p = p->next;
 61                 
 62             }
 63             m->next = q->next;
 64             if (m1 != NULL)
 65             m1->next = q;
 66             q->next = p;
 67             q = m->next;
 68         }
 69     }
 70 }
 71 
 72 void Radix_Sort(double a[], int n)
 73 {
 74     list b[10];
 75     int j;
 76     for (int i = 1; i <= n; i++)
 77     {
 78         
 79         j = n*a[i];
 80         addlist(&b[j], a[i]);
 81     }
 82     for (int i = 0; i < n; i++)
 83     {
 84         insertion(&b[i]);
 85     }
 86     for (int i = 0; i < n; i++)
 87     {
 88             for (int j = 1; j <= b[i].n; j++)
 89             {
 90                 cout << b[i].head->n << endl;
 91                 b[i].head = b[i].head->next;
 92             }
 93     }
 94 }
 95 
 96 
 97 
 98 void main()
 99 {
100     double a[11];
101     for (int i = 1; i <= 10; i++)
102         a[i] = 1.0 - 0.06*i;
103     Radix_Sort(a, 10);
104 
105 
106     
107     
108     
109 }

桶排序先把要排的小数乘一个整数，按得到整数的整数部分，放入list[整数部分]。

在用成熟的排序算法把list中的小数进行排序，因为数列较少，降低了比较的次数，从而提高效率。

缺点减少了时间，但却消耗了较多的内存。