为什么冒泡排序代码中的for循环会报索引越界错误?
报错原因
- 你代码中的for循环使用了
range(len(l))作为遍历范围,当列表长度为n时,i的取值会覆盖0到n-1的所有整数 - 当i等于n-1(也就是最后一个元素的索引)时,代码中访问了
l[i+1],这个索引对应的是列表第n+1个元素,超出了列表的有效索引范围(Python列表有效索引为0到n-1),因此触发IndexError - 从逻辑上看,冒泡排序的每一轮遍历只需要比对到倒数第二个未排序元素即可,因为每次比对都需要拿当前元素和后一个元素做比较,遍历到最后一个元素没有后续元素可以比对,本身就是无效操作
修复方案
基础修复(仅解决越界问题)
直接修改for循环的遍历范围,去掉最后一个元素的遍历即可:
l = [5, 8, 1, 3, 2] still_swapping = True while still_swapping: still_swapping = False # 遍历到倒数第二个元素为止,保证i+1不会越界 for i in range(len(l) - 1): if l[i] > l[i+1]: l[i], l[i+1] = l[i+1], l[i] still_swapping = True print(l)
优化修复(提升冒泡排序效率)
冒泡排序每一轮遍历都会把当前未排序部分的最大值移动到末尾,后续遍历不需要再比对这些已经沉底的有序元素,可以进一步缩小遍历范围:
l = [5, 8, 1, 3, 2] still_swapping = True sorted_tail_length = 0 while still_swapping: still_swapping = False # 遍历范围排除末尾已经有序的元素 for i in range(len(l) - sorted_tail_length - 1): if l[i] > l[i+1]: l[i], l[i+1] = l[i+1], l[i] still_swapping = True sorted_tail_length += 1 print(l)
内容的提问来源于stack exchange,提问作者lostonthecoderoad
相关产品推荐
相关产品推荐

