用顺序比较的方式求n个元素序列中第2大的元素的代码
时间: 2024-05-02 07:19:34 浏览: 15
以下是一个用快速选择算法(QuickSelect)求解 n 个元素序列中第 2 大的元素的 Python 代码:
```
def find_second_largest(arr):
def quick_select(arr, left, right, k):
if left == right:
return arr[left]
pivot_index = choose_pivot_index(left, right)
pivot_new_index = partition(arr, left, right, pivot_index)
if k == pivot_new_index:
return arr[k]
elif k < pivot_new_index:
return quick_select(arr, left, pivot_new_index - 1, k)
else:
return quick_select(arr, pivot_new_index + 1, right, k)
def choose_pivot_index(left, right):
return (left + right) // 2
def partition(arr, left, right, pivot_index):
pivot_value = arr[pivot_index]
arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
store_index = left
for i in range(left, right):
if arr[i] > pivot_value:
arr[i], arr[store_index] = arr[store_index], arr[i]
store_index += 1
arr[right], arr[store_index] = arr[store_index], arr[right]
return store_index
n = len(arr)
return quick_select(arr, 0, n - 1, n - 2)
```
这个算法的思想是:每次选择一个基准值(pivot),将数组分成两个部分,然后根据第 k 大的元素出现在哪个部分,递归地在该部分中寻找目标元素。时间复杂度为 O(n),其中 n 为数组长度。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)