计数排序：

桶排序：www.roading.org/algorithm/introductiontoalgorithm

算法模型：

1，桶排序假设待排的一组数统一分布在一个范围[m....n]，将这一范围划分为几个子范围，也就是桶bucket。

　　例如，如何将0---999范围的数，划分到10个桶中？范围中数的个数用K表示，那么K/10=1000/10=100，就是每个桶装100个元素，即[0..99]装到第一个桶中，[100..199]装到第二个桶中，。。。以此类推。

　　怎么判断一个数组该放到哪个桶中呢？例如整形元素a[i]=342，a[i]/100=342/100=3，就是说342得放到第（3+1）=4桶中

2，将待排序的一组数，分别放到这些子桶中。（可以采用插入排序的过程，在放入桶的过程中进行排序;也可以分配好后，利用stdlib.h中的qsort函数进行快速排序）;

3，最后将各个桶中的数据有序的合并起来。

时间复杂度分析：https://www.byvoid.com/blog/sort-radix

对于整数序列A，元素的最小值不小于0，最大值不大于K。假设我们由M个桶，第i个桶Bucket[i]存储的i*K/M~(i+1)*K/M之间的数字。

如果数据是期望平均分配的，则每个桶中的元素平均个数就N/M。

　　如果对每个桶中的元素采用快速排序，每次排序的的复杂度为O(N/M *  log(N/M))。

则总的时间复杂度为O(N)+O(M)*O(N/M *  log(N/M)) = O(N + Nlog(N/M)) = O(N+NlogN - NlogM)，就是说M越接近N时，桶排序的时间复杂度就可近似认为是O(N)。这时桶的数量也就越多。

 

//伪代码Bucket-Sort(A)    let B[0..n-1] be a new array    n = A.lenghtS    for i = 0 to n - 1        make B[i] an empty list    for i = 1 to n         insert A[i] into list B[nA[i]]    for i = 0 to n - 1        sort list B[i] with insertion sort    concatenate the lists B[0], B[1]....B[n - 1] togather in order

 

　　来自https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F

class A{public： ///    const int BUCKET_NUM = 10;    ListNode *insert(ListNode *head, int val){        ListNode dummyNode(-1);        ListNode *newNode = new ListNode(val);        ListNode *prev,*curr;        dummyNode.next = head;        prev = &dummyNode;        curr = head;        while(curr && curr->val <= val){            prev = curr;            curr = curr->next;        }///find location to insert; prev->next        newNode->next = curr;        prev->next = newNode;        return dummyNode.next;    }    ListNode *mergebucket(ListNode *head1,ListNode *head2){        ListNode dummy(-1);        ListNode *h = &dummy;        while(head1 && head2){            if(head1->val <= head2->val){                h->next = head1;                head1 = head1->next;            }else{                h->next = head2;                head2 = head2->next;            }            h = h->next;        }        if(head1) h->next = head1;        if(head2) h->next = head2;        return dummy.next;    }    void BucketSort(int n,int arr[]){        vector
     
       buckets(BUCKET_NUM,nullptr);        for(int i = 0;i
      
       val;            head = head->next;        }    }///    void test(ListNode *head){        int *a = new int[15];        for(int i = 0;i<15;i++){            a[i] = rand()%15+1;        }        for(int i = 0;i<15;i++){            cout<
       
        <<" ";        }cout<
       
      
     

 

基数排序

 

 

基数排序(Radix Sort)。计数排序和桶排序都只是在研究一个关键字的排序，现在我们来讨论有多个关键字的排序问题。

 

假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相 同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

 

第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

通常计数排序要用到计数排序或桶排序。

下面利用桶排序 对  二元组进行 基数排序。