欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基数排序+桶排序

程序员文章站 2022-03-24 15:32:36
...

基数排序

缺点:空间复杂度大;不能有重复的数字
对于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");
}

未完待续。。。。。