快速排序辅助方法出现Integer与nil比较失败错误求助

问题场景 #

在创建二叉搜索树前，使用快速排序对包含15个元素的随机数组排序时触发错误，错误提示为comparison of Integer with nil failed (ArgumentError)。

错误栈信息 #

C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:197:in `<=': comparison of Integer with nil 
failed (ArgumentError)
        from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:197:in `block in partition'    
        from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:194:in `each'
        from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:194:in `partition'
        from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:181:in `quick_sort'
        from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:185:in `quick_sort'
        from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:10:in `initialize'
        from ./lib/main.rb:5:in `new'
        from ./lib/main.rb:5:in `<main>'

涉事代码 #

快速排序主方法 #

def quick_sort(array, s, e)
    if s < e
      p = partition(array, s, e)
      quick_sort(array, s, p - 1)
      quick_sort(array, p + 1, e)
    end
    array.uniq!
    array
  end

分区辅助方法 #

def partition(array, s, e)
    x = array[e]
    i = s - 1
    (s...e).each do |j|
      next unless array[j] <= x

      i += 1
      swap(array, i, j)
    end
    swap(array, (i + 1), e)
    i + 1
 end

交换方法 #

def swap(array, i, j)
    temp = array[i]
    array[i] = array[j]
    array[j] = temp
    array
  end

问题根源 #

错误触发点在partition方法的array[j] <= x判断，原因如下：

1. 快速排序递归过程中调用了array.uniq!，该方法会直接修改原数组，移除重复元素后数组长度缩短。
2. 但递归传递的s和e是基于原数组的索引范围，当数组长度变短后，e可能超出新数组的有效索引，导致x = array[e]取到nil。
3. 后续遍历中，整数类型的array[j]与nil类型的x进行比较，触发类型错误。

修复方案 #

将array.uniq!移到快速排序完成之后，避免在递归过程中修改数组长度：

def quick_sort(array, s, e)
    if s < e
      p = partition(array, s, e)
      quick_sort(array, s, p - 1)
      quick_sort(array, p + 1, e)
    end
    array
  end

# 调用时先排序再去重
sorted_array = quick_sort(original_array, 0, original_array.length - 1).uniq

另一种方案是在调用快速排序前先去重，确保递归过程中数组长度稳定：

unique_array = original_array.uniq
sorted_array = quick_sort(unique_array, 0, unique_array.length - 1)

额外优化建议 #

• 简化快速排序参数，默认使用数组首尾索引，避免手动传递：

  def quick_sort(array, s = 0, e = array.length - 1)
      # 原有逻辑保持不变
  end
  

• 在partition方法开头添加防御性判断，避免索引越界：

  def partition(array, s, e)
    return s if s >= e
    # 原有逻辑保持不变
  end
  

内容的提问来源于stack exchange，提问作者Ruiyot Abby