我正试图使用XSLT编写一个堆排序算法。但很难交换用于存储标记化值的变量的值。我创建了用于比较值的方法heapify，并将较大的值交换到当前索引。任何人请帮助指导我交换父列表的值。

<xsl:template match="/">
<xsl:variable name="tokenizedSample" select="tokenize(.,' ')">             
</xsl:variable>
<!--<xsl:value-of select="."/>-->
<xsl:call-template name="BuildHeap">
<xsl:with-param name="intList" select="$tokenizedSample"/>
</xsl:call-template>
</xsl:template>

<xsl:template name="BuildHeap">
<xsl:param name="intList"/>
<xsl:for-each select="$intList">
<xsl:call-template name="Heapify">
<xsl:with-param name="newintList" select="$intList"/>
<xsl:with-param name="index"  select="position()"/>
</xsl:call-template>
</xsl:for-each>
</xsl:template>

<xsl:template name="Heapify">    
<xsl:param name="newintList"/>
<xsl:param name="index"/>
<xsl:variable name="stringval">
<xsl:text></xsl:text>
</xsl:variable>
<xsl:variable name="vIndex">
<xsl:number value="$index" />
</xsl:variable>
<xsl:variable name="stringval" select="concat(($stringval),'is')"/>
<xsl:if test="$newintList[$vIndex*2] &gt; $newintList[$vIndex*1]  and $newintList[$vIndex*2] &gt; $newintList[($vIndex*2)+1] ">
<!—swap the values of ith position with 2ith position-->
<xsl:for-each select="$newintList">
<xsl:if test="position()=$vIndex">
<xsl:value-of select="$newintList[$vIndex*2]"/>
<xsl:value-of select="$stringval"/>
<xsl:variable name="stringval" select="concat(($stringval),'is',$newintList[$vIndex*2])"/>
<xsl:value-of select="$stringval"/>
</xsl:if>
<xsl:if test="position()=($vIndex*2)">
<xsl:value-of select="$stringval"/>
<xsl:variable name="stringval" select="concat(($stringval),'is')"/>
<xsl:value-of select="$stringval"/>
<xsl:variable name="stringval" select="concat(($stringval),'is',$newintList[$vIndex*1])"/>
</xsl:if>
</xsl:for-each>
<xsl:value-of select="$stringval"/>
</xsl:if>

<xsl:if test="$newintList[($vIndex*2)+1] &gt; $newintList[$vIndex*1]  and $newintList[($vIndex*2)+1] &gt; $newintList[$vIndex*2] ">
<!—swap the values of ith position with 2i+1th position-->
</xsl:if>
</xsl:template>

I。下面是一个XSLT2.0解决方案:

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:my="my:my" xmlns:xs="http://www.w3.org/2001/XMLSchema">
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:template match="/">
<xsl:sequence select="my:swap(/*/*, 3, 7)"/>
</xsl:template>
<xsl:function name="my:swap" as="item()*">
<xsl:param name="pSeq" as="item()*"/>
<xsl:param name="pPos1" as="xs:integer"/>
<xsl:param name="pPos2" as="xs:integer"/>
<xsl:sequence select=
"$pSeq[position() lt $pPos1],
$pSeq[$pPos2],
$pSeq[position() gt $pPos1 and position() lt $pPos2],
$pSeq[$pPos1],
$pSeq[position() gt $pPos2]
"/>
</xsl:function>
</xsl:stylesheet>

当此转换应用于以下XML文档时：

<nums>
<num>01</num>
<num>02</num>
<num>03</num>
<num>04</num>
<num>05</num>
<num>06</num>
<num>07</num>
<num>08</num>
<num>09</num>
<num>10</num>
</nums>

生成所需的正确结果：

<num>01</num>
<num>02</num>
<num>07</num>
<num>04</num>
<num>05</num>
<num>06</num>
<num>03</num>
<num>08</num>
<num>09</num>
<num>10</num>

II。等效的XSLT 1.0解决方案:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:template match="/">
<xsl:call-template name="swap">
<xsl:with-param name="pSeq" select="/*/*"/>
<xsl:with-param name="pPos1" select="3"/>
<xsl:with-param name="pPos2" select="7"/>
</xsl:call-template>
</xsl:template>
<xsl:template name="swap">
<xsl:param name="pSeq"/>
<xsl:param name="pPos1"/>
<xsl:param name="pPos2"/>
<xsl:copy-of select="$pSeq[$pPos1 > position()]"/>
<xsl:copy-of select="$pSeq[$pPos2]"/>
<xsl:copy-of select="$pSeq[position() > $pPos1 and $pPos2 > position()]"/>
<xsl:copy-of select="$pSeq[$pPos1]"/>
<xsl:copy-of select="$pSeq[position() > $pPos2]"/>
</xsl:template>
</xsl:stylesheet>

当此转换应用于同一XML文档(如上)时，会产生相同的正确结果：

<num>01</num>
<num>02</num>
<num>07</num>
<num>04</num>
<num>05</num>
<num>06</num>
<num>03</num>
<num>08</num>
<num>09</num>
<num>10</num>

这里是对Dimitre的XSLT2.0解决方案的调整。它在规模上并不高效，但有些人可能更喜欢改进的可读性

将xsl:sequence指令修改为…

<xsl:sequence select="
for $i in $pSeq,
$p in index-of( $pSeq, $i) return
$pSeq[
if ($p eq $pPos1) then
$pPos2
else if ($p eq $pPos2) then
$pPos1
else
$p]" />
</xsl:function>

注意事项：

为了实现这一点，它需要$pSeq完全由唯一的项组成。如果序列包含重复的节点或相同值的原子项，它将不起作用。但从问题的背景来看，这可能是一个安全的假设。

更新：

这是一个更好的。

<xsl:sequence select="
for $p in 1 to count($pSeq) return
$pSeq[
if ($p eq $pPos1) then
$pPos2
else if ($p eq $pPos2) then
$pPos1
else
$p]" />
</xsl:function>

更新#2

Dimitre和我对OP问题的回答都是绝对正确的。OP回答说，他的答案不知何故没有给出想要的结果，但无法阐明与这一结果错误有关的任何相关细节。很难帮助那些不愿澄清的海报，所以我认为我在这里能做的最有帮助的事情就是为OP试图开发的HeapSort提供一个完整的解决方案。

正如其他人所说，在现实世界的环境中，只需要使用xsl:sort。事实上，即使作为一个学术问题，它也不是一个好的学术问题，因为它与现实世界的解决方案有必要的距离，这可能会误导和混淆学生。我向您展示了Heapsort的XSLT2.0实现(使用这个维基百科页面上的算法)。

(更新说明)

请参阅Dimitre关于效率的评论。与本机排序(xsl:sort)相比，任何自定义的排序都将效率低下。真的没有充分的理由这样做，除非作为一种学术活动被迫这样做。

由于OP忘记提供一个用例，我将在这里提供一个。

用例1:

有了这个输入

<t>6 5 3 1 8 7 2 4</t>

目标是对整数进行排序并生成此输出

<t>
<n>1</n>
<n>2</n>
<n>3</n>
<n>4</n>
<n>5</n>
<n>6</n>
<n>7</n>
<n>8</n>
</t>

此XSLT2.0样式表将使用Heap排序算法对整数数组进行排序

(更新说明)

这个样式表中有一个错误。我正在纠正它。

<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:fn="http://www.w3.org/2005/xpath-functions"
xmlns:so="http://stackoverflow.com/questions/13445906"
exclude-result-prefixes="xsl xs fn so">
<xsl:output omit-xml-declaration="yes" indent="yes" />
<xsl:template match="/*">
<xsl:copy>
<xsl:for-each select="so:heapsort( for $x in tokenize(.,' ') return xs:integer($x))">
<n><xsl:value-of select="." /></n>
</xsl:for-each>
</xsl:copy>   
</xsl:template>
<xsl:function name="so:heapsort" as="xs:integer*">
<xsl:param name="a" as="xs:integer*" />
<xsl:sequence select="so:one-heapsort( so:heapify( $a, count($a) idiv 2), count($a))" />
</xsl:function>
<xsl:function name="so:one-heapsort" as="xs:integer*">
<xsl:param name="a" as="xs:integer*" />
<xsl:param name="end" as="xs:integer" />
<xsl:choose>
<xsl:when test="$end gt 0">
<xsl:sequence select="so:one-heapsort(
so:siftDown( so:swap( $a, 1, $end), 1, $end - 1),
$end - 1)" />
</xsl:when>
<xsl:otherwise>
<xsl:sequence select="$a" />
</xsl:otherwise>
</xsl:choose>
</xsl:function>
<xsl:function name="so:heapify" as="xs:integer*">
<xsl:param name="a" as="xs:integer*" />
<xsl:param name="start" as="xs:integer" />
<xsl:choose>
<xsl:when test="$start gt 0">
<xsl:sequence select="so:heapify(
so:siftDown( $a, $start, count($a)),
$start - 1)" />
</xsl:when>
<xsl:otherwise>
<xsl:sequence select="$a" />
</xsl:otherwise>
</xsl:choose>
</xsl:function>
<xsl:function name="so:siftDown" as="xs:integer*">
<xsl:param name="a" as="xs:integer*" />
<xsl:param name="start" as="xs:integer" />
<xsl:param name="end" as="xs:integer" />
<xsl:sequence select="
subsequence( $a, 1, $start - 1),
so:one-siftDown( subsequence( $a, $start, $end - $start + 1), 1),
subsequence( $a, $end+1, count($a)-$end)
" />
</xsl:function>
<xsl:function name="so:swap" as="xs:integer*">
<xsl:param name="a" as="xs:integer*" />
<xsl:param name="x" as="xs:integer" />
<xsl:param name="y" as="xs:integer" />
<xsl:sequence select="
for $p in 1 to count($a) return $a[
if ($p eq $x) then $y
else if ($p eq $y) then $x
else $p]" />
</xsl:function>
<xsl:function name="so:one-siftDown" as="xs:integer*">
<xsl:param name="a" as="xs:integer*" />
<xsl:param name="root" as="xs:integer" />
<xsl:variable name="left-child" select="$root * 2" as="xs:integer" />
<xsl:variable name="right-child" select="$left-child + 1" as="xs:integer" />
<xsl:variable name="palette" select="($a[$root], $a[$left-child], $a[$right-child])" />
<xsl:choose>
<xsl:when test="exists( $palette)">
<xsl:variable name="max-pos" select="index-of($palette,max($palette))[1]" />
<xsl:choose>
<xsl:when test="($left-child le count($a)) and ($max-pos eq 2)">
<xsl:sequence select="so:one-siftDown(
so:swap( $a, $root, $left-child),
$left-child)" />
</xsl:when>
<xsl:when test="($right-child le count($a)) and ($max-pos eq 3)">
<xsl:sequence select="so:one-siftDown(
so:swap( $a, $root, $right-child),
$right-child)" />
</xsl:when>
<xsl:otherwise>
<xsl:sequence select="$a" />
</xsl:otherwise>
</xsl:choose>
</xsl:when>
<xsl:otherwise>
<xsl:sequence select="$a" />
</xsl:otherwise>
</xsl:choose>
</xsl:function>
</xsl:stylesheet>

注释

swap()函数是OP在问题中要求的交换函数，只是它专门用于整数，而不是项
你可以使用Dimitre的交换或我的实现。我很想知道OP对哪一个更具可读性的意见。甚至还有第三种方法——您可以将subsequence()和concatination运算符(,)组合起来
作为一个学术讨论点，这个样式表在2012年7月10日的XSLT3.0工作草案中会简单得多，因为该算法非常适合新的fn:fold-left()函数。如果这个问题被概括为按任何函数对任何事物进行排序，那么这个任务将是XSLT3.0草案的一个很好的展示案例。IMHO，XSLT3.0草案的用例任务少得令人不安。我一直在努力收集它们

按顺序交换项目

注意事项：

更新：

更新#2

(更新说明)

(更新说明)

注释

相关内容

最新更新

热门标签：