在排序的最终结果中，各元素的次序依赖于他们之间的比较，我们把这类算法称为比较排序。一般情况下，我们所接触到的排序算法均为比较排序。
这里介绍三种限行时间复杂度排序算法：计数排序、基数排序和桶排序。他们是非比较排序算法。
1、计数排序
计数排序假设n个输入元素中的每一个都是在0-k区间内的一个整数，其中k为某个整数。当k=O(n)时，排序运行时间为
计数的基本思想：对每一个输入元素x，确定小于x的元素个数，利用这个信息，可以直接将元素输出到数组中对应的位置。例如，如果有17个元素小于x，则x就在第18个输出位置上。当几个元素相同时，就把这一策略改动一下，因为不能把它们放到同一个位置上。
// count sort#include <iostream>using namespace std;const int MAX = 100;//k值区间范围void count_sort(int a[], int b[], int n);int main(void){int a[5] = {5, 2, 7, 9, 1};int b[6] = {0};count_sort(a, b, 5);for(int i = 1; i <= 5; i++)cout<<b[i]<<" ";cout<<endl;return 0;}void count_sort(int a[], int b[], int n){int c[MAX];for(int i = 0; i < MAX; i++)c[i] = 0;for(int i = 0; i < n; i++)c[a[i]]++;for(int i = 1; i < MAX; i++)c[i] += c[i-1];for(int i = n-1; i >= 0; i–) //i有大依次减小，保证了排序算法的稳定性，相同元素之间的相对位置不变{b[c[a[i]]] = a[i];c[a[i]]–; //这样保证相同的元素的位置不同}}2、桶排序
假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。
比如：在桶排序的代码中我们假设输入时包含n个元素的数组A，每个A[i]满足0<=A[i]<1，此外，还需要一个临时数组B[n]来存放链表（桶）。
//待排序的元素范围为0-99，因为只开辟了10个"桶"#include <iostream>using namespace std;typedef struct NODE{int data;struct NODE * next;}Node, *pNode;void bucket_sort(int a[], int n);int main(void){int a[7] = {4, 3, 5, 2, 12, 71, 41};bucket_sort(a, 7);for(int i = 0; i < 7; i++)cout<<a[i]<<" ";cout<<endl;return 0;}void bucket_sort(int a[], int n){pNode pb = new Node[10]; //用于存放数据的10个"桶"，每个"桶"的data存放的是该桶中的元素个数for(int i = 0; i < 10; i++){pb[i].data = 0;pb[i].next = NULL;}for(int i = 0; i < n; i++){pb[a[i]/10].data++;if(pb[a[i]/10].next == NULL) //此时该桶中一个元素也没有{pNode t = new Node;t->data = a[i];t->next = NULL;pb[a[i]/10].next = t;}else{pNode p = pb[a[i]/10].next;pNode p_prev = p;while(p != NULL && a[i] >= p->data) //沿着链表遍历{p_prev = p;p = p->next;}if(p == p_prev) //此时该元素应该插在"桶"中的第一个位置{pNode t = new Node;t->data = a[i];t->next = p;pb[a[i]/10].next = t;}else //此时该元素应该插在"桶"中不是第一的位置{pNode t = new Node;t->data = a[i];t->next = p;p_prev->next = t;}}}for(int i = 0, j = 0; i < 10; i++) //依次把"桶"中排好序的元素重新赋值到数组中{if(pb[i].next != NULL){pNode p = pb[i].next;while(p != NULL){a[j++] = p->data;p = p->next;}}}for(int i = 0; i < 10; i++) //释放链表内存{pNode p = pb[i].next;while(p != NULL){pNode t = p;p = p->next;delete t;}}delete []pb; //释放临时链表数组内存}3、基数排序
基数排序与桶排序类似。上述的基数排序和桶排序都只是在研究一个关键字的排序，现在基数排序可以处理有多个关键字的排序问题。
假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。
第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。
基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列：
278、109、063、930、589、184、505、269、008、083
莫找借口失败，只找理由成功。(不为失败找理由，要为成功找方法
