对下列数组应用线性时间选择算法找出第4小的元素:80+20+55+43+78+26+90+65+15+30+给出每步过程
时间: 2023-10-02 11:07:32 浏览: 67
对下列数组应用线性时间选择算法找出第4小的元素的每步过程如下:
1. 将数组分成大小为5的子数组:[80, 20, 55, 43, 78], [26, 90, 65, 15, 30].
2. 对每个子数组进行插入排序并找出中位数:[20, 43, 55, 78, 80], [15, 26, 30, 65, 90].
3. 在找到的中位数数组中,找到中位数的中位数:55.
4. 将原始数组根据中位数的中位数分成三个部分:小于55的数组,等于55的数组,大于55的数组。
5. 根据第4小的元素在这三个部分中的位置,选择进行下一步操作。
6. 重复步骤1-5直到找到第4小的元素。