快速排序枢轴元素处理错误致数组越界及死循环问题排查

咱先拆解下你代码里的问题根源，主要集中在partition函数的循环边界和交换逻辑上：

1. 数组越界的直接原因 #

你的两个do-while循环都没做边界限制：

• 第一个循环do { i += 1 } while(arr(i) <= pivot)：如果数组里所有元素都小于等于基准值pivot，i会一直递增到arr.length（也就是9），这时候访问arr(i)就会触发索引越界（数组最大索引是8）。
• 第二个循环do { j -= 1 } while(arr(j) > pivot)：如果所有元素都大于pivot，j会一直递减到-1，访问arr(j)自然也会越界。

2. 死循环的诱因 #

当你盲目添加边界条件时，比如只加i < high但没调整循环逻辑，会导致指针无法正常交叉，或者交换后递归区间重复，进而触发死循环。

修正后的完整代码 #

下面是调整后的代码，我会标注关键修改点：

object Quick {
  def main(args: Array[String]): Unit = {
    var arr = Array[Int](10,16,8,12,15,6,3,9,5)
    val low = 0 // 用val更符合Scala不可变风格
    val high = arr.length - 1
    quickSort(low, high)
    arr.foreach(println)

    def quickSort(low: Int, high: Int): Unit = {
      if (low < high) {
        val j = partition(low, high)
        quickSort(low, j - 1) // 调整递归区间，基准值已在正确位置无需重复处理
        quickSort(j + 1, high)
      }
    }

    def partition(low: Int, high: Int): Int = {
      val pivot = arr(low) // 基准值用val，避免意外修改
      var i = low
      var j = high + 1 // 关键修改：初始j设为high+1，配合后续先减再判断的逻辑

      while (true) {
        // 给循环加边界i <= high，防止越界
        do { i += 1 } while (i <= high && arr(i) <= pivot)
        // 给循环加边界j >= low，防止越界
        do { j -= 1 } while (j >= low && arr(j) > pivot)

        if (i >= j) {
          // 指针交叉，把基准值放到正确位置
          swap(low, j)
          return j // 返回基准值的索引
        }
        // 交换找到的不符合顺序的元素
        swap(i, j)
      }
      j // 占位，实际上面已经return
    }

    def swap(ai: Int, aj: Int): Unit = {
      val tmp = arr(ai)
      arr(ai) = arr(aj)
      arr(aj) = tmp
    }
  }
}

关键修改说明 #

1. 循环边界检查：给两个do-while循环加上i <= high和j >= low的限制，彻底避免数组越界。
2. 基准值交换逻辑：最后交换的是low（基准值初始位置）和j的位置，而不是你原来的i和j——因为j最终指向的是小于等于基准值的最后一个位置，这才是基准值应该在的正确位置。
3. 递归区间调整：修正后的quickSort递归区间是low到j-1和j+1到high，因为j位置已经是排好序的基准值，不需要再处理。
4. 变量风格优化：把不需要修改的变量改成val，更符合Scala的函数式编程习惯。

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