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

《算法实习报告(一种新颖的排序算法介绍).pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一种新型的排序算法吕日辉、郝志刚、潘知才、邹锋、杨海强汇报人：吕日辉目录1问题的由来2算法思想及其实现2.1该算法在整数排序的应用及结果对比本文目录结构3算法的优缺点2.2该算法在浮点数据排序的应用及结果对比4总结和展望问题由来几个问题问题2：谁能给一个方案，能够快速的把在座的各位按照身高排个序？问题1：我们班大概有120多人，老师给定我们成绩后，怎样排成绩会比较快？1问题的由来1问题的由来计算机上如何实现呢？算法的核心思想543210根据范围申请数组并初始化352443520110050403

2、0201002算法核心思想的演示165432711111对原素组遍历赋值给原数组554433221100已排好数组待排序数组具体的算法实现根据获得的范围申请一段数组空间，进行必要的初始化对待排数组进行一次遍历，记录下每个值所处的位置对新申请的数组进行一次遍历，把已经排好的重新赋给待排序数组2.1该算法在整数排序的应用2.1该算法在整数排序的应用申请一段空间：int*index=newint[high-low+1];进行必要的初始化：for(inti=0;i!=high-low+1;++i)ind

3、ex[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是数组个数)算法复杂度分

4、析2.1该算法在整数排序的应用从上面的分析可知，算法复杂度为：F(n)=3n+range······式子1从上面这个表达式可以很清晰的看出来，在range不超过n很多的情况下，该算法是具有大on的效果的。特别的，在range<

5、类型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算

6、法在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!=

7、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+

8、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类型数据排序上的应用VS改进的无敌排序法传统快速排序法