从标准输入中输入一组互不相同的整数(个数不超过100)及排序方式,按照从小到大排序,输出按某种算法排序的结果及元素的比较次数。
时间: 2024-04-29 07:23:06 浏览: 19
我们可以使用各种排序算法来实现这个问题,下面以冒泡排序为例进行讲解。
冒泡排序的基本思想是从前往后比较相邻的元素,如果前一个元素大于后一个元素,则交换这两个元素的位置,直到最后一个元素。这样一趟比较后,最后一个元素一定是序列中的最大值。然后对除了最后一个元素的子序列重复上述操作,直到整个序列有序。
具体实现过程如下:
1. 从标准输入中读入一组互不相同的整数,存储在数组中。
2. 读入排序方式,根据排序方式选择相应的排序算法。
3. 实现排序算法,同时记录比较次数。
4. 输出排序后的结果及比较次数。
代码如下:
```python
# 冒泡排序
def bubble_sort(arr):
n = len(arr)
count = 0
for i in range(n):
for j in range(n-i-1):
count += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr, count
# 读入数据
arr = list(map(int, input().split()))
n = len(arr)
# 读入排序方式
sort_type = input()
# 选择排序算法
if sort_type == 'bubble':
arr, count = bubble_sort(arr)
# 输出结果
print('sorted array:', arr)
print('number of comparisons:', count)
```
示例输入:
```
5 3 8 4 2 1
bubble
```
示例输出:
```
sorted array: [1, 2, 3, 4, 5, 8]
number of comparisons: 15
```