十大排序算法学习总结(C++)

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 排序算法
• 一、插入排序
• • 直接插入排序
  • 折半插入排序
  • 希尔排序
• 二、交换排序
• • 冒泡排序
  • 快速排序
• 三、选择排序
• • 简单选择排序
  • 堆排序
• 四、归并排序
• 五、计数排序
• 六、桶排序
• 七、基数排序
• 总结
• • 时间性能
  • 空间性能
  • 排序方法的稳定性能
  • 关于“排序方法的时间复杂度的下限”

---

排序算法

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

关于时间复杂度：

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n(1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序基数排序，此外还有桶、计数排序。

关于稳定性:

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

• n：数据规模
• k："桶"的个数
• In-place：占用常数内存，不占用额外内存
• Out-place：占用额外内存
• 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

按排序依据原则：

插入排序：直接插入排序、折半插入排序、希尔排序

交换排序：冒泡排序、快速排序

选择排序：简单选择排序、堆排序

归并排序：2-路归并排序、多路归并排序

基数排序、计数排序、桶排序

一、插入排序

基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

即边插入边排序，保证子序列随时都是排好序的。

直接插入排序

直接插入排序——采用顺序查找法查找插入位置

#include
using namespace std;
void insertion_sort(int arr[],int len){
    int i,j;
    for(int i=1;i
        if(arr[i]
            int key = arr[i];
            for(j=i-1;j>=0 && key
                arr[j+1]=arr[j];
            }
            arr[j+1]=key;
        }
    }
}
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(arr)/sizeof(arr[0]);
    insertion_sort(arr,len);
    printarr(arr,len);
    return 0;
}

折半插入排序

#include
using namespace std;
void half_insertion_sort(int arr[],int len){
    int i,j;
    for(int i=1;i
        int key=arr[i];
        if(arr[i]>arr[i-1]){
            arr[i] = key;
        }else{
        int low = 0;int high = i-1;
        while(low<=high){
            int mid = low+(high-low)/2;
            if(key
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
   		for(j=i-1;j>=high+1;--j) arr[j+1]=arr[j];
    	arr[high+1]=key;
        }
    }
     
}
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(arr)/sizeof(arr[0]);
    half_insertion_sort(arr,len);
    printarr(arr,len);
    return 0;
}

希尔排序

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

特点：

• 缩小增量
• 多遍插入排序

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

#include
using namespace std;
void shellinsert(int arr[],int dk,int length){//dk:增量值
    int i,j;
    // int size = sizeof(arr)/sizeof(arr[0]); arr做函数参数，传的是数组的地址，所以不在函数内部使用sizeof
    //对顺序表arr进行一趟增量为dk的shell排序，dk为步长因子
    for(i=dk;i
        if(arr[i]
            int key = arr[i];
            for(j=i-dk;j>=0&&(key
                arr[j+dk]=arr[j];
            }
            arr[j+dk]=key;
        }
    }
}
void shellsort(int arr[],int dlta[],int t,int length){ //arr:待排序数组，dlta：增量数组，t:增量数组元素个数，length：待排序数组长度
    //按增量序列dlta[0...t-1]对顺序表作希尔排序
    for(int i=0;i
        shellinsert(arr,dlta[i],length);//一趟增量为dlta[i]的插入排序
    }
}
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int dlta[] = {5,3,1};
    int t = sizeof(dlta)/sizeof(dlta[0]);
    int len = sizeof(arr)/sizeof(arr[0]);
    shellsort(arr,dlta,t,len);
    printarr(arr,len);
    return 0;
}

希尔排序算法效率与增量序列的取值有关。

希尔排序法是一种不稳定的排序算法。

二、交换排序

冒泡排序

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。冒泡一趟，一个最大数就升上去了，经常n-1趟后全部元素就排序好了。

#include
using namespace std;
void bubble_sort(int arr[],int length){
    int i,j;
    for(i=0;i //i代表冒泡的趟数，从0开始
        for(j=0;j //每趟比较的次数
            if(arr[j]>arr[j+1]){
                int key = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = key;
            }
        }
    }
}
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(arr)/sizeof(arr[0]);
    bubble_sort(arr,len);
    printarr(arr,len);
    return 0;
}

如何提高效率？可以对冒泡进行改进：一旦某一趟比较时不出现记录交换，说明已经排好序了，就可以结束本算法。

#include
using namespace std;
void bubble_sort(int arr[],int length){ //改进的冒泡排序
    int i,j;
    int flag = 1;//用来标志是否有元素进行交换
    for(i=0;i //i代表冒泡的趟数，从0开始
        flag = 0;
        for(j=0;j //每趟比较的次数
            if(arr[j]>arr[j+1]){
                flag = 1;  //发生交换，flag置1，若本趟没有发生交换，flag保持为0
                int key = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = key;
            }
        }
    }
}
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(arr)/sizeof(arr[0]);
    bubble_sort(arr,len);
    printarr(arr,len);
    return 0;
}

快速排序

——改进的交换排序

快速排序是由东尼·霍尔所发展的一种排序算法。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序应该算是在冒泡排序基础上的递归分治法。

算法步骤

• 任取一个元素（如：第一个）为中心点，pivot：枢轴，中心点
• 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表
• 对各子表重新选择中心元素并依此规则调整——递归思想
• 直到每个子表的而元素只剩一个

#include
using namespace std;
int Parttition(int arr[],int low,int high){
    int pivot = arr[low]; //确定中心点位置
    while(low
        while(low=pivot){
            high--;
        }
        arr[low] = arr[high];
        while(low
            low++;
        }
        arr[high]=arr[low];
    }
    arr[low]=pivot;
    return low;
}
void quick_sort(int arr[],int low,int high){//对顺序表进行快速排序
    if(low//长度大于1
        int pivotloc = Parttition(arr,low,high);//将arr一分为2
        quick_sort(arr,low,pivotloc-1);
        quick_sort(arr,pivotloc+1,high);
    }
}
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(arr)/sizeof(arr[0]);
    int low = 0;
    int high = len-1;
    quick_sort(arr,low,high);
    printarr(arr,len);
    return 0;
}

快速排序的时间复杂度为O(nlogn)；

空间复杂度：快速排序不是原地排序，由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。

在平均情况下：需要O(logn)的栈空间。

快速排序时一种不稳定的排序方法。

{90，85，79，74，68，50，46}进行快速排序划分，由于每次枢轴记录的关键字都是大于其他所有记录的关键字，致使一次划分之后得到的子序列（1）的长度为0，这时已经退化成为没有改进的措施的冒泡排序。

快速排序不适于对原本有序或基本有序的记录序列进行排序。

输入次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序。

（自然排序指的是输入顺序越有序，排序越快的方法。）

三、选择排序 简单选择排序

基本思想：在待排序的数据中选出最大（最小）的元素放在其最终的位置。

算法步骤：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

#include
using namespace std;
void selection_sort(int arr[],int length){
    for(int i=0;i //总共进行的趟数
        int min = i; //记录最小值的位置
        for(int j=i+1;j
            if(arr[j]
                min = j;
            } 
        }
        if(min!=i){
            int key = arr[min];
            arr[min] = arr[i];
            arr[i] = key;
        }
    }
}
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(arr)/sizeof(arr[0]);
    selection_sort(arr,len);
    printarr(arr,len);
    return 0;
}

简单选择排序是不稳定排序。

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

这里用的树的编号的性质，在数组，双亲节点的编号若为i，则它的左孩子的编号为2i，右孩子的编号为2i+1。

堆排序：若在输出堆顶的最小值（最大值）之后，使得剩余n-1个元素的序列重又建成了一个堆，则得到n个元素的次小值（次大值）…如此反复，便能得到一个有序序列，这个过程叫做堆排序。
实现推排序主要需要解决两个问题：

• 如何由一个无序序列建成一个堆
• 如何在输出堆顶元素后，调整剩余元素为一个新的堆

堆的调整

大根堆的话，每次就与其中大者进行交换。

void HeapAdjust(int arr[],int strat,int end){
//已知arr[start...end]中记录的关键字除arr[start]之外均满足堆的定义，本函数调整R[start]的关键字，使得arr[start...end]成为一个大根堆
//对于二叉树来说，编号是从1开始的，但是数组是从0开始，所以我们虽然是使用的二叉树性质，但程序改成了从0开始编号。
	int rc = arr[start];
    int j;
    for(j = 2*start+1;j<=end;j=j*2+1){//沿着值较大的孩子节点向下筛选
        if(j
            j++; //比较两个孩子节点，选择最大的,这样建成大跟堆
        }
        if(rc>=arr[j]) break;
        arr[start] = arr[j];
        start = j;
    }
    arr[start] = rc;
}

可以看出：对于一个无序序列反复“筛选”就可以得到一个堆；即从一个无序序列建堆的过程就是一个反复“筛选”的过程。

那么：如何由一个无序序列建成一个堆？

堆的建立


将初始无序的arr[0]到[n-1]建成一个大根堆，可以用以下语句实现：

for(int i=n/2-1;i>0;i--){//这里也是因为从0开始的缘故
	HeapAdjust(arr,i,n);
}

堆排序

void heap_sort(int arr[],int len){
    int i;
    //初始化建堆
    for(i=len/2-1;i>=0;i--){
        HeapAdjust(arr,i,len-1); //建立成大根堆
    }
    for(i=len-1;i>0;i--){//进行n-1趟排序
        swap(arr[0],arr[i]); //根与最后一个元素交换，这样最大值就到了最后一个位置，使得从后向前依次减小，最终得到升序结果
        HeapAdjust(arr,0,i-1);//对arr[0]到arr[i-1]重新建堆
    }
}

堆排序的完整程序：

#include
using namespace std;
//堆的调整
void HeapAdjust(int arr[],int start,int end){
    int rc = arr[start];
    int j;
    for(j = 2*start+1;j<=end;j=j*2+1){//沿着值较大的孩子节点向下筛选
        if(j //j=arr[j]) break;
        arr[start] = arr[j];
        start = j;
    }
    arr[start] = rc;
}
//堆排序
void heap_sort(int arr[],int len){
    int i;
    //初始化建堆
    for(i=len/2-1;i>=0;i--){
        HeapAdjust(arr,i,len-1); //建立成大根堆
    }
    for(i=len-1;i>0;i--){//进行n-1趟排序
        swap(arr[0],arr[i]); //根与最后一个元素交换，这样最大值就到了最后一个位置，使得从后向前依次减小，最终得到升序结果
        HeapAdjust(arr,0,i-1);//对arr[0]到arr[i-1]重新建堆
    }
}
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int arr[]={61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(arr)/sizeof(arr[0]);
    heap_sort(arr,len);
    printarr(arr,len);
    return 0;
}

堆排序不是一种稳定的排序方法，他不适合于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。

四、归并排序

基本思想：将两个或两个以上的有序子序列”归并“为一个有序序列，该算法是采用分治法（Divide and Conquer）。

在内部排序中，通常采用的是2-路归并排序。

即将两个位置相邻的有序子序列R[0…m]和R[m+1,n]归并为一个有序序列。

归并排序关键问题：如何将两个有序序列合并成一个有序序列？

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。
   
   
   

#include
using namespace std;
//归并排序的递归实现
const int MAXN = 12;
int nums[MAXN]={61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };//待排序数组
int temp[MAXN];   //辅助数组

void _merge(int low,int mid,int high){
    int left = low;   //左边部分数组指针
    int right = mid+1;//右边部分数组指针
    int k = low; //对temp数组操作的指针
    while(left
        if(nums[left]>nums[right]){
            temp[k++]=nums[right++];
        }else{
            temp[k++]=nums[left++];
        }
    }
    //查看左边序列是否为空
    while(left
        temp[k++]=nums[left++];
    }
    //查看右边序列是否为空
    while(right
        temp[k++]=nums[right++];
    }
    //移动回原数组
    for(int i=low;i<=high;i++){
        nums[i]=temp[i];
    }
}
//归并排序
void mergesort(int low,int high){
    //递归终止条件
    if(low>=high){
        return;
    }
    int mid = low +((high-low)>>1);
    //分
    mergesort(low,mid);
    mergesort(mid+1,high);
    //治
    _merge(low,mid,high);
}
int main(){
    mergesort(0,10);
    for(int i=0;i<=10;i++){
        cout< 
#include
using namespace std;
//归并排序的非递归实现
void mergesort(int *a,int n){
      int* tmp =new int[n];
      int groupNum = 1;
      while(groupNum
          for(int i=0;i
            // [begin1][end1] [begin2,end2] 
			// 归并
            int begin1 = i,end1 = i+groupNum-1;
            int begin2 = i+groupNum,end2=i+groupNum*2-1;
            int index = begin1;
            // 数组数据个数，并不一定是按整数倍，所以划分的分组可能越界或者不存在
			// 1、[begin2,end2] 不存在, 修正为一个不存在的区间
            if(begin2>=n){
                begin2 = n;
                end2 = n-1;
            }
            // 2、end1越界,修正一下
            if(end1>=n){
                end1 = n-1;
            }
            // 3、end2越界，需要修正后归并
            if(end2>=n){
                end2=n-1;
            }
            while(begin1<=end1 && begin2<=end2){
                if(a[begin1]
                    tmp[index++]=a[begin1++];
                }else{
                    tmp[index++]=a[begin2++];
                }
            }
            while(begin1<=end1){
                tmp[index++]=a[begin1++];
            }
            while(begin2<=end2){
                tmp[index++]=a[begin2++];
            }
          }
          //拷贝回原数组
          for(int i=0;i
              a[i] = tmp[i];
          }
          groupNum *=2;
      }
      delete(tmp);
}
int main(){
    int nums[]={61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };//待排序数组
    int *a = nums;
    int len = sizeof(nums)/sizeof(nums[0]);
    mergesort(a,len);
    for(int i=0;i
        cout< 
归并排序的算法分析：
 
时间效率:O(nlogn)
空间效率:O(n)
 
因为需要一个与原始序列同样大小的辅助序列temp。
 
归并算法是一个稳定的算法。
 
五、计数排序 
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
 
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
 
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
 
算法的步骤如下：
 
（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
 
#include
#include
using namespace std;
void printarr(int arr[],int len){
    for(int i=0;i
        cout< //ini_arr代表原数组，sorted代表排好序的数组，n代表数组元素个数
    //找数组的最大值和最小值
    int max = ini_arr[0];//记录数组的最大值
    int min = ini_arr[0];//记录数组的最小值
    int i,j,k;
    for(i=0;i
        if(ini_arr[i]>max){
            max = ini_arr[i];
        }
        if(ini_arr[i]
            min = ini_arr[i];
        }
    }
    int l = max-min+1;//计算计数数组的长度
    int* count_arr = new int[l];
    //初始化计数数组
    for(k=0;k
        count_arr[k]=0;
    }
    //统计数字个数
    for(i=0;i
        count_arr[ini_arr[i]-min]++;
    }
    //对计数做累加，得到对应下标的排序
    for(k=1;k
        count_arr[k]+=count_arr[k-1];
    }
    //从后往前遍历
    for(j=n-1;j>=0;j--){
        sorted_arr[--count_arr[ini_arr[j]-min]] = ini_arr[j];
    }
    delete(count_arr);
}
int main(){
    int array[] = {94,90,93,92,91,99,98,97};
    int n=sizeof(array)/sizeof(array[0]);
    int *arr = array;
    int *sorted_arr = new int[n];
    cout<<"ini_array:"< 
 
六、桶排序 
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
 
在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
 
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
 
示意图：
 
 需要考虑的问题，桶还是用数组存储的话，桶的大小难以确定。用链表的话，就可以动态分配内存，但是对链表进行排序非常麻烦。
 
 桶排序的两个特例就是计数排序和基数排序，看了很多地方讲桶排序，讲的都是这两个特例，有实现普通的桶排序，使用的是链表，但是链表排序的话，它的时间效率非常低。
 
#include
#include
#include
using namespace std;
//桶排序 使用容器来模拟存储桶
void bucket_sort(int arr[],int len){
    //找原数组中的最大值
    int max = arr[0]; //记录最大值
    int min = arr[0]; //记录最小值
    int i,j,k;
    for(i=0;i
        if(arr[i]>max){
            max = arr[i];
        }
        if(arr[i]
            min = arr[i];
        }
    }
    //得到桶的数量
    int bucketcounts = (max-min)/len+1;

    vector> bucketarrays;
    //初始化桶
    for(i=0;i
        vector bucket;
        bucketarrays.push_back(bucket);
    }
    //将数分到每个桶里面
    for(j=0;j
        int num = (arr[j]-min)/len;
        bucketarrays[num].push_back(arr[j]);
    }
    //对每个桶进行排序
    int index = 0;
    for(i=0;i
        sort(bucketarrays[i].begin(),bucketarrays[i].end());
    }
    //收集每个桶的数据
    for(j=0;j
        for(k=0;k
            arr[index++]=bucketarrays[j][k];
        }
    }
}
//打印数组
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int array[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(array)/sizeof(array[0]);
    bucket_sort(array,len);
    printarr(array,len);
    return 0;
}
 
七、基数排序 
基本思想：分配+收集
 
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
 
基数排序有两种方法：
 
LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
 
MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序
 
 
#include
using namespace std;
//求数据中的最大位数
int maxbit(int arr[],int n){
    int d=1;//保存最大位数
    int p=10;
    for(int i=0;i
        while(arr[i]>=p){
            p *=10;
            ++d;
        }
    }
    return d;
}
void radix_sort(int arr[],int n){//基数排序
    int d = maxbit(arr,n);//返回最大位数
    int *tmp = new int[n];//开辟n个数组空间
    int *count = new int[10];//开辟10个计数空间，数组0-9
    int i,j,k;
    int radix = 1;
    for(int i=1;i<=d;i++){//进行d趟排序
        for(j = 0;j<10;j++){
            count[j] = 0;//每次分配前情况计数器
        }
        for(j=0;j
            k = (arr[j]/radix)%10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j=1;j<10;j++){
            count[j] += count[j-1]; //通过累加实现统计每个桶的排序，跟计数排序一个道理
        }
        for(j=n-1;j>=0;j--){//将所有桶中的记录依次收集到tmp中
            k = (arr[j]/radix)%10;
            tmp[--count[k]] = arr[j];
            
        }
        for(j=0;j//将临时数组的内容复制到arr
            arr[j]=tmp[j];
        }
        radix *= 10;
    }
    delete tmp;
    delete count;
}
//打印数组
void printarr(int arr[],int len){
    for(int i=0;i
        cout<
    int array[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = sizeof(array)/sizeof(array[0]);
    radix_sort(array,len);
    printarr(array,len);
    return 0;
}
 
时间效率O(k*(n+m))
 
k:关键字的个数
 
m：关键字取值范围为m个值（桶的个数）
 
空间效率：O(n+m)
 
稳定性：稳定
 
计数排序、基数排序、桶排序，本质上都涉及到了桶的概念，只是在桶的处理上有所不同，基数排序是根据每个键值的每位数字来分配桶，计数排序是每个桶只存储单一键值，而桶排序是存储一个范围的数值（一个桶代表一个范围区间）。计数排序和基数排序其实是桶排序的特例。
 
总结 
排序算法在面试中经常会问道，需要掌握不同排序算法的时间复杂度以及空间复杂度，排序算法分析时尽量多去画画图进行模拟，然后学习完以后多结合具体的题目进行巩固。
 
时间性能 
1.按平均的时间性能来分，有三类排序方法：
 
 
时间复杂度为O(nlogn)的方法有：
 
  
快速排序、堆排序和归并排序，其中以快速排序为最好：
 
 
时间复杂度为O(n2)的有：
 
  
直接插入排序、冒泡排序和简单选择排序，其中以直接插入为最好；
特别是对那些对关键字近似有序的记录序列尤为如此；
 
 
时间复杂度为O(n)的排序方法有：基数排序、计数排序、桶排序
 
 
2.当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到O(n)的时间复杂度，而对于快速排序而言，这是最不好的情况，此时的时间性能退化为O(n2),因此是应该尽量避免的情况。
 
3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
 
空间性能 
指的是排序过程中所需的辅助空间大小
 
1.所有的简单排序方法(包括：直接插入、冒泡和简单选择)和堆排序的空间复杂度为O(1)
 
2.快速排序为O(logn),为栈所需的铺助空间
 
3.归并排序所需辅助空间最多，其空间复杂度为O(n)
 
4.链试基数排序需附设队列首尾指针，则空间复杂度为O(rd)
 
排序方法的稳定性能 
稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。
 
当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。(比如成绩表：按数学成绩先排，再按总分先排，这样排出来，总分相同时，数学高的排名靠前)
 
对于不稳定的排序方法，只要能举出一个实例说明即可。
 
快速排序和堆排序是不稳定的排序方法。简单选择排序也能举例说明不是稳定的。
 
关于“排序方法的时间复杂度的下限” 
讨论的各种排序方法，除桶排序系列外，其它方法都是基于“比较关键字”进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn).
 
（基数排序不是基于“比较关键字”的排序方法所以它不受这个限制。）
 
可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。