数据结构与算法分析 |
您所在的位置:网站首页 › 排列间接法概念是什么 › 数据结构与算法分析 |
间接排序(indirectionSort): 直接应用基于谢尔排序、快速排序等这些算法的函数模板时,如果要排序的Comparable对象很大时,有时效率是很低的,问题在于,重新排列的Comparable对象时,进行了太多的复制工作,如果Comparable对象很大且难以复制,则代价将是很大的。解决的办法是:生成一个指向Comparable对象的指针数组,然后重新排列这些指针。一旦确定了元素应该在的位置,就可以直接将该元素放在相应的位置上,而不必过多的中间复制操作。这需要使用称为中间置换(in-situ permutation)的算法。【用C++实现的时候需要一些新的语法】 行为描述: 算法描述: 第一步:生成指针数组。令a为要排序的数组,p为指针数组。初始化后p[i]指向a[i]; 第二步:使用p[i]所指的对象的值来确定p[i]的顺序并对p[i]排序[快速排序]。在数组a的对象完全不动,而数组p的指针重新排序。 第三步:移位实现p[i]回填到a[i]中; C++特性: 1)vector不运行 quickSort(p)重新排列指针时,quickSort模板算法为Comparable*,因此需要能够比较两个Comparable* 类型的“ |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |