编写两个程序分别用来求逆序数和判定序数
时间: 2023-07-15 17:10:58 浏览: 64
求逆序数的程序:
```python
def merge_sort(arr):
if len(arr) == 1:
return arr, 0
mid = len(arr) // 2
left, inv_left = merge_sort(arr[:mid])
right, inv_right = merge_sort(arr[mid:])
merged, count = merge(left, right)
return merged, inv_left + inv_right + count
def merge(left, right):
result = []
count = 0
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
count += len(left) - i
result += left[i:]
result += right[j:]
return result, count
arr = [2, 4, 1, 3, 5]
result, inv_count = merge_sort(arr)
print(inv_count)
```
判定序数的程序:
```python
def is_sorted(arr):
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
return True
arr = [1, 2, 3, 4, 5]
print(is_sorted(arr)) # True
arr = [2, 1, 3, 4, 5]
print(is_sorted(arr)) # False
```
第一个程序使用归并排序算法来求逆序数,它的基本思想是将数组分成两部分进行排序,然后将两部分合并。在合并的过程中,如果左半部分的元素大于右半部分的元素,那么就要计算逆序数,具体的计算方法是左半部分剩余的元素个数。最终,逆序数等于左半部分的逆序数加上右半部分的逆序数加上合并时计算得到的逆序数。
第二个程序很简单,只需要遍历整个数组,判断相邻的两个元素是否有逆序即可。如果有逆序,就说明数组是无序的。
相关推荐
![](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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)