在归并排序的以下算法中,在第3个定义中,第一个while循环中有:
a[k++] = (a[j] < b[i]) ? a[j++] : b[i++].
我理解RHS是一个条件语句,它表明如果第一个操作数得到满足,那么我们应该执行第二个操作数,如果没有得到满足,我们就应该执行第三个操作数。
a[k++]
,a[j++]
和b[i++]
对应哪个元素呢?
根据我的理解,这应该意味着在每个连续的while循环中,元素都会递增。
也就是说,从初始化的值(i=1
,j=m+1
,k=1
)开始进行第一个while循环,下一个while循环将包括(i=2
,j=m+2
,k=2
),以此类推。
以下是整个算法:
# split in half
m = n / 2
# recursive sorts
sort a[1..m]
sort a[m+1..n]
# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
→ invariant: a[1..k] in final position
while i <= m,
a[k++] = b[i++]
→ invariant: a[1..k] in final position