算法导论练习8.3-4

2012-08-13

算法导论习题8.3-4对0到n^2-1范围内的数字进行排序，要求时间复杂度为O(n)。可以直接采用基数排序法对其排序

算法导论习题8.3-4

对0到n^2-1范围内的数字进行排序，要求时间复杂度为O(n)。

可以直接采用基数排序法对其排序，但是这些数字为已知范围，所以有更进一步的优化，即将所有的数字转换成n进制，这样这些数在n进制下只有两位，即只需要比较2O(n)即可。转换成n进制消耗2O(n)，所以对于比较的数字为四位以上时，该算法较普通的基数排序有优势。

具体代码如下：

修改：此处的插入排序应该改为计数排序。因为插入排序时间复杂度太高

//习题 8.3-4采用改进的基数排序，所选择的稳定的排序算法为插入排序。

//对所要比较的数进行转换，对于范围从0到n^2-1的数字，将所有元素转换成n进制//此时只需比较两位。当比较的数字位数比较多时时间效率比较高。#include<iostream>using namespace std;//使用插入排序作为稳定的排序算法//******************//******************//*******************void Insert_sort(int a[],int (*b)[2],int n,int length)  {      int i,j,key;      for(i=1;i<length;i++)      {          key=b[i][n];          j=i-1;          while(key<b[j][n])          {              int temp;              temp=a[j+1];              a[j+1]=a[j];              a[j]=temp;  temp=b[j+1][0];  b[j+1][0]=b[j][0];  b[j][0]=temp;temp=b[j+1][1];  b[j+1][1]=b[j][1];  b[j][1]=temp;            j=j-1;              if(j<0)              {                  break;              }          }      }  }  //**********//***********//**********//将数组中的数转换成n进制，这样只需要比较两位即可。void Divide(int a[],int (*b)[2],int n,int length){int i,j;int c[100]={0};for(i=0;i<length;i++){c[i]=a[i];}for(i=0;i<length;i++){//b[i][0]存放低位b[i][0]=c[i]%n;//b[i][1]存放高位b[i][1]=c[i]/n;}}void RadixSort(int a[],int (*b)[2],int n,int length){int i;Divide(a,b,n,length);for(i=0;i<=1;i++){Insert_sort(a,b,i,length);}}int main(){int a[10],b[10][2];int i;for(i=0;i<10;i++){a[i]=rand()%100000;cout<<a[i]<< ' ';}cout<<endl;RadixSort(a,b,1000,10);for(i=0;i<10;i++){cout<<a[i]<<' ';}cout<<endl;}

热点排行

编程

算法导论练习8.3-4