Ruby实现插入排序算法及进阶的二路插入排序代码示例（ruby 数组操作）满满干货

文章摘要

这篇文章介绍了名为`two_way_sort`的排序算法。伪代码中定义了该算法的基本逻辑，该算法通过两个指针`first`和`final`来分割数组，并通过比较当前元素与中间值的大小，将其插入到相应的子数组中。整个过程类似于插入排序，但通过分段处理提升效率。伪代码中还提到了数组的操作，例如复制结果到`result`数组，并通过示例展示了算法的使用方法，其中`data`数组经过`shuffle`后作为输入，排序后的结果被输出。该算法的时间复杂度为O(n²)，适合处理较小规模的数据。

def two_way_sort data
first,final=0,0
temp=[]
temp[0]=data[0]
result=[]
len=data.length

for i in 1..(len-1)
if data[i]>=temp[final]
final +=1
temp[final]=data[i]
elsif data[i]<=temp[first]
first=(first -1 + len)%len
temp[first]=data[i]
else
if data[i]<temp[0]
low=first
high=len -1

while low <=high do
m=(low + high)>>1
if data[i]>temp[m]
low=m + 1
else
high=m -1
end
end

j=first – 1
first -=1
while j < high do
temp[j]=temp[j+1]
j +=1
end

temp[high]=data[i]
else
low=0
high=final

while low <=high do
m=(low + high)>>1

if data[i]>=temp[m]
low=m + 1
else
high=m – 1
end
end

j=final + 1
final +=1

while j > low do
temp[j]=temp[j-1]
j -=1
end

temp[low]=data[i]
end
end
p temp
end

i=0
for j in first..(len – 1)
result[i]=temp[j]
i +=1
end

for j in 0..final
result[i]=temp[j]
i +=1
end

return result
end

data=[4,1,5,6,7,2,9,3,8].shuffle