LC1491.去掉最低工资和最高工资后的工资平均值

【用本题复习一下408的各种内部排序算法】
【先发出来，后续补充各种】

直接插入排序

呃呃呃 一开始…平均值忘了分母是size-2

还有j应该是>0，一开始的时候写的是>=0，错的

临界条件就是：
比如 2357891
扫描到1的时候
1记录为temp
i是1的下标
j=i
然后往前看
每一个都比1大，要往后移动一个
最后判断的是salary0>temp（1）
这个时候j是1，j也只需要是1
因为j代表的是
若j-1往后移动之后的下标

纠正后的代码

double average(int* salary, int salarySize) {int i, j, temp;// 插入排序for (i = 1; i < salarySize; i++) {temp = salary[i];for (j = i; j > 0 && salary[j - 1] > temp; j--) {salary[j] = salary[j - 1];}salary[j] = temp;}// 计算去掉最高和最低工资后的平均值double sum = 0;for (i = 1; i < salarySize - 1; i++) {sum += salary[i];}double avg = sum / (salarySize - 2);return avg;
}

力扣有了这个功能诶

知识点复习

最好情况
外循环是要执行的

但是这个内循环不需要进去，所以是O(n)，本题n是salarySize

平均

在平均情况下，数组元素是随机排列的。每次插入时，当前元素在已经排序部分的平均插入位置大约在中间。因此，内层循环在第i次插入时平均执行i/2次比较。

外层循环执行n-1次。
内层循环在第i次插入时平均执行i/2次比较。
总的比较次数为：
$$[T_{\text{avg}}(n)=\sum _{i=1}^{n-1}\frac{i}{2}=\frac{1}{2}\sum _{i=1}^{n-1}i=\frac{1}{2}\cdot \frac{(n-1)n}{2}=\frac{(n-1)n}{4}]$$

因此，平均情况下的时间复杂度为：$O(n^2)$

在最坏情况下，数组是逆序的。每次插入时，都需要将所有已经排序的元素向后移动一位。

外层循环执行n-1次。
内层循环在第i次插入时执行i次比较。
总的比较次数为： $[T_{\text{worst}}(n)={\sum }_{i=1}^{n-1}i=\frac{(n-1)n}{2}]$

因此，最坏情况下的时间复杂度为： [ O(n^2) ]