Dart实现快速排序频繁抛出‘not in inclusive range’异常，偶现正常运行求排查

我来帮你排查这个问题！你遇到的not in inclusive range异常，本质是数组索引越界了，而且时好时坏的原因完全取决于随机生成的列表元素分布——当出现某些极端元素分布时，你的循环会让索引超出列表的合法范围。

具体问题点 #

你的partition函数里的两个while循环没有做边界限制：

1. 第一个循环：while (list[i] <= list[pivot]) {++i;}
   如果从i=l开始，所有元素都小于等于pivot的值，i会一直递增到list.length（甚至更大），这时候访问list[i]就会超出列表的最大合法索引（list.length-1），直接触发异常。
2. 第二个循环：while (list[j] > list[pivot]) {--j;}
   如果所有元素都大于pivot的值，j会一直递减到-1，访问list[j]同样会越界报错。

修复后的代码 #

只需要给两个while循环加上边界判断，确保i不超过h，j不小于l即可：

import 'dart:math';
List<int> list = [];
void main() {
 randomize();
 quickSort(0, list.length - 1);
 print(list);
}
void randomize() {
 for (int i = 0; i < 100; ++i) {
 list.add(Random().nextInt(100));
 }
}
void quickSort(int l, int h) {
 if (l < h) {
 int mid = partition(l, h);
 quickSort(l, mid - 1);
 quickSort(mid + 1, h);
 }
}
int partition(int l, int h) {
 int pivot = l;
 int i = l;
 int j = h;
 while (i < j) {
 // 增加i <= h的边界判断，防止索引越界
 while (i <= h && list[i] <= list[pivot]) {
 ++i;
 }
 // 增加j >= l的边界判断，防止索引越界
 while (j >= l && list[j] > list[pivot]) {
 --j;
 }
 if (i < j) {
 int temp = list[i];
 list[i] = list[j];
 list[j] = temp;
 }
 }
 int temp = list[pivot];
 list[pivot] = list[j];
 list[j] = temp;
 return j;
}

验证说明 #

修改后，无论随机生成的列表元素如何分布（比如全是相同值、完全逆序等极端情况），快速排序都能正常执行，不会再出现索引越界的异常。

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