网站导航菜单代码/百度快照网址

基数排序

缺点：空间复杂度大；不能有重复的数字
对于b[a[i]] = a[i];的理解
比如在循环赋值的过程中，对于大小为3的数组a[3],有
a[0] = 2,a[1]=5,a[2]=9;
那么有b[2]=2, b[5]=5, b[9] = 9，其余的b[0],b[1],b[3],b[4],b[6],b[7],b[8]均为初值-1，见代码。

#include<vector>
#include <tchar.h> 
#include<iostream>
void radix_sort(int* a, int len, int max)
{ //1.创建临时数组 int* b = new int[max + 1];    //因为要当下标用，所以下标为max的数组长度为max+1  //2.初始化临时数组 for (int i = 0; i <= max; i++){b[i] = -1;}//3.排序for (int i = 0; i < len; i++){b[a[i]] = a[i];     //i=10}//4.把b数组元素赋值回a数组（因为b数组中有很多为-1的值）int j = 0;for (int i = 0; i <= max; i++){if (b[i] != -1){a[j++] = b[i];          //将a[j] = b[i]后，j自加; }}//5.释放临时数组delete[] b;
}
int _tmain(int argc, _TCHAR* argv[])
{int a[10] = { 9, 5, 7, 3, 4, 1, 0, 6, 8, 2 };int length = sizeof(a) / sizeof(int);radix_sort(a, length,9);for (int i = 0; i < length; i++){printf("%3d",a[i]);}system("pause");
}

未完待续。。。。。