数据结构与算法分析

您所在的位置:网站首页 排列间接法概念是什么 数据结构与算法分析

数据结构与算法分析

2024-07-13 07:06| 来源: 网络整理| 查看: 265

间接排序(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