篡改插入排序比较逻辑为哈希判断，实现三类异常运行效果的方案咨询

背景说明 #

以下是原始插入排序伪代码：

function INSERTIONSORT(A[0..n−1])
for i←1 to n−1 do 
    j←i−1 
    while j≥0 and A[j+1]<A[j] do 
          SWAP(A[j+1],A[j])
          j←j−1

篡改后的插入排序将元素大小比较逻辑替换为HASH函数返回值对比：

function INSERTIONSORT(A[0..n−1])
for i←1 to n−1 do
    j←i−1 
    while j≥0 and HASH(A,j+1) < HASH(A,j) do 
        SWAP(A[j+1],A[j])
        j←j−1

1. 插入排序运行后原数组完全不变的HASH函数设计 #

实现逻辑 #

HASH(A, k) = k

原理说明 #

插入排序的交换触发条件为HASH(A,j+1) < HASH(A,j)，当HASH值直接等于传入的索引k时，对于任意j都满足HASH(A,j+1) = j+1 > j = HASH(A,j)，交换条件永远不成立。整个排序过程不会触发任何一次元素交换，原数组自然完全保持初始状态。 #

2. 插入排序始终触发最坏时间复杂度的HASH函数设计 #

实现逻辑 #

HASH(A, k) = -k

原理说明 #

插入排序的最坏时间复杂度为O(n²)，触发条件为每一轮待插入的元素都需要向前交换到数组最左端。
当HASH值等于-k时，任意j都满足HASH(A,j+1) = -(j+1) < -j = HASH(A,j)，交换条件永远成立。每一轮外层循环i执行时，当前下标为i的元素都会被一路交换到数组下标0的位置，总交换次数为1+2+...+(n-1) = n(n-1)/2，正好达到插入排序的最坏时间复杂度。 #

3. 插入排序将数组按逆序排列的HASH函数设计 #

实现逻辑 #

HASH(A, k) = -A[k]

原理说明 #

原始插入排序的比较逻辑是A[j+1] < A[j]就交换，最终得到升序排列的数组。现在将HASH值设置为数组元素的相反数，比较HASH(A,j+1) < HASH(A,j)等价于-A[j+1] < -A[j]，两边同时乘-1反转不等号后等价于A[j+1] > A[j]。
也就是当后一个元素比前一个元素大的时候触发交换，和升序排序的交换逻辑完全相反，最终排序完成后数组就会按降序（逆序）排列。 #

内容的提问来源于stack exchange，提问作者William Wu