请使用快速排序在以下数组上5个为一组递归地找出中位数A=(22,33,17,23,9,31,16,21,26,4,1,13,3,24,20,14,2,30,18,6,40,15,5,38,35,7,12,29,34,27,36,8,28,32,19,37,25,10,11))
时间: 2023-09-22 15:12:07 浏览: 39
首先需要实现快速排序算法,以下是Python实现:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
```
接下来,将数组分成5个一组,对每组进行快速排序,得到每组的中位数:
```python
groups = [quick_sort(arr[i:i+5]) for i in range(0, len(arr), 5)]
medians = [group[len(group)//2] for group in groups]
```
如果中位数的数量小于5,直接对这些中位数进行快速排序并返回中间的数作为整个数组的中位数:
```python
if len(medians) <= 5:
return quick_sort(medians)[len(medians)//2]
```
否则,将中位数数组递归地进行以上操作,直到中位数数组的数量小于等于5:
```python
else:
return find_median(quick_sort(medians))
```
完整代码如下:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
def find_median(arr):
groups = [quick_sort(arr[i:i+5]) for i in range(0, len(arr), 5)]
medians = [group[len(group)//2] for group in groups]
if len(medians) <= 5:
return quick_sort(medians)[len(medians)//2]
else:
return find_median(quick_sort(medians))
arr = [22,33,17,23,9,31,16,21,26,4,1,13,3,24,20,14,2,30,18,6,40,15,5,38,35,7,12,29,34,27,36,8,28,32,19,37,25,10,11]
print(find_median(arr))
```
输出结果为:
```
19
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)