修改插入排序算法为非递增

Question

请问如何将插入排序的输出变成非递增排序？例如 537 将是 753。此外，与增加（最好和最坏情况）相比，运行时间是否相同？

伪代码：

 INSERTION-SORT(A)
    for j = 2 to A.length
        key = A[j]
        // Insert A[j] into the sorted sequence A[1..j]
        i = j - 1
        while i > 0 and A[i] > key
            A[i +1] = A[i]
            i = i - 1
        A[i + 1] = key

Answer 1

运行时不会受到更改的影响。在计算机科学中谈论数字时，最好说 descending 而不是 non-increasing。增加将是增加。话虽这么说，请参阅下面的代码以了解您正在寻求的更改（特别注意 while 循环）。

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] < key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

修改插入排序算法为非递增

Modify Insertion Sort Algorithm to be Non-increasing

algorithm

pseudocode

insertion-sort