算法实习报告(一种新颖的排序算法介绍)

一种新型的排序算法吕日辉、郝志刚、潘知才、邹锋、杨海强汇报人：吕日辉目录1问题的由来2算法思想及其实现2.1该算法在整数排序的应用及结果对比本文目录结构3算法的优缺点2.2该算法在浮点数据排序的应用及结果对比4总结和展望问题由来几个问题问题2：谁能给一个方案，能够快速的把在座的各位按照身高排个序？问题1：我们班大概有120多人，老师给定我们成绩后，怎样排成绩会比较快？1问题的由来1问题的由来算法的核心思想543210根据范围申请数组并初始化3524435201100504030201002算法核心思想的演示165432711111对原素组遍历赋值给原数组554433221100已排好数组待排序数组具体的算法实现根据获得的范围申请一段数组空间，进行必要的初始化对待排数组进行一次遍历，记录下每个值所处的位置对新申请的数组进行一次遍历，把已经排好的重新赋给待排序数组2.1该算法在整数排序的应用2.1该算法在整数排序的应用申请一段空间：int*index=newint[high-low+1];进行必要的初始化：for(inti=0;i!=high-low+1;++i)index[i]=0;这一段算法复杂度为range，既数组取值范围对新申请的数组进行一次遍历，把已经排好的重新赋给待排序数组intmark=0;for(inti=0;i!=high-low+1;++i)if(index[i]!=0)for(intj=0;j!=index[i];++j)array[mark++]=i+low;这一段复杂度为N。对待排序数组进行一次遍历：for(inti=0;i!=num;++i)index[array[i]-low]++;这一段复杂度为2N，(N是数组个数)算法复杂度分析2.1该算法在整数排序的应用从上面的分析可知，算法复杂度为：F(n)=3n+range······式子1从上面这个表达式可以很清晰的看出来，在range不超过n很多的情况下，该算法是具有大on的效果的。特别的，在rangen的情况下，算法可以高效的达到3n的效果，这样的复杂度还是非常高效的。对于浮点类型数据的实现2.2算法在double类型数据排序上的应用2.2算法在double类型数据排序上的应用整形数据部分小数部分Double类型2.2算法在double类型数据排序上的应用21051.241.030.422.312.100.7待排序数组申请一个新的数组整数排序标准排序22.12.311.01.200.40.7依次往回赋值52.342.131.221.010.700.4已排好数组这里使用标准库里的算法0.72.10.41.01.22.3专有的数据结构structdouble_dear{intnums;//用来记录具有相同整//数部分的个数double*dou;//存放具有相同整数部//的double类型数据};2.2算法在double类型数据排序上的应用这个过程我们可以分四步：//必要的初始化：复杂度为rangedouble_dear*dou_index=newdouble_dear[high-low+1];for(inti=0;i!=high-low+1;++i)dou_index[i].nums=0;//进行第一次遍历，对每一个子数组申请相应的空间，复杂度O(n)for(inti=0;i!=num;++i)dou_index[(int)array[i]-low].nums++;for(inti=0;i!=high-low+1;++i)dou_index[i].dou=newdouble[dou_index[i].nums];//把相应的值添加到对应的子数组中,复杂度O(n)for(inti=0;i!=num;++i){intk=0;dou_index[(int)array[i]-low].dou[k++]=array[i];}//对每一个子数组进行标准排序，然后往回写值，复杂度range*(n/range)lg(n/range)。intmark=0;for(inti=0;i!=high-low+1;++i)if(dou_index[i].nums!=0){sort(dou_index[i].dou,ou_index[i].dou+dou_index[i].nums);for(intj=0;j!=dou_index[i].nums;++j)array[mark++]=dou_index[i].dou[j];}由上面的分析可知，该算法复杂度是（这里省略各项系数）：n*lgn-n*lg(range)+range+n2.2算法在double类型数据排序上的应用2.2算法在double类型数据排序上的应用3算法的优缺点1）当待排数据时整数时，而且不是特别稀疏，该算法远快于传统快速排序2）对于double类型数据，当数据较为稠密时，效果也优于传统快速排序优点1）所需空间较大2）对于非常稀疏的跨度极大的数据处理显得太低效；缺点4总结和展望该算法是出自我们小组内部讨论，来自于我们小组成员对一些问题的细致思考，显然，这想法是非常棒的。该算法对于一般的整数数据而言具有极好的效果，这源自于计算机数据的离散型。而这对于非整数类型显然就缺少那种天然优越性。于是，我们曾设想，也希望，对于所有的实数而言，能够找到这样一把标尺，对所有的数据，像我们测量身高一样在上面留下标记，那么，这个算法将会对于任意不过分稀疏的数据具有高效性。