1回答

liuyubobobo

2022-02-14

在最差的情况下，每一轮遍历的范围只比上一轮少 1。即第 1 轮需要遍历 n 个元素；第 2 轮需要遍历 n - 1 个元素；第 3 轮需要遍历 n - 2 个元素 ... 第 n 轮需要遍历 1 个元素。

所以，其总共需要的操作数是 n + (n - 1) + (n - 2) + ... + 1，这是一个等差数列，用等差数列求和之后，扔掉系数和低阶项，就是 O(n^2)，实际上，这个式子是和选择排序法，插入排序法等等，一致的。

继续加油！：）

0