给定n个数,并按从小到大的顺序,以列表的形式输出这n个数中前m小的数(m<n)。输入格式:第一行输入两个数n和m,用逗号隔开; 第二行输入n个数,用逗号隔开。 输出形式:输出一个列表。python实现用插入排序、选择排序、冒泡排序三种方法实现该排序。
时间: 2024-03-14 12:43:24 浏览: 61
栈的出栈顺序问题
4星 · 用户满意度95%
1. 插入排序实现:
```python
def insert_sort(nums, m):
for i in range(1, len(nums)):
j = i - 1
while j >= 0 and nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
j -= 1
if i == m:
return nums[:m]
return nums[:m]
n, m = map(int, input().split(","))
nums = list(map(int, input().split(",")))
res = insert_sort(nums, m)
print(res)
```
2. 选择排序实现:
```python
def select_sort(nums, m):
for i in range(len(nums)):
min_idx = i
for j in range(i+1, len(nums)):
if nums[j] < nums[min_idx]:
min_idx = j
nums[i], nums[min_idx] = nums[min_idx], nums[i]
if i == m-1:
return nums[:m]
return nums[:m]
n, m = map(int, input().split(","))
nums = list(map(int, input().split(",")))
res = select_sort(nums, m)
print(res)
```
3. 冒泡排序实现:
```python
def bubble_sort(nums, m):
for i in range(len(nums)-1):
flag = False
for j in range(len(nums)-1-i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
flag = True
if not flag:
break
if i == m-1:
return nums[:m]
return nums[:m]
n, m = map(int, input().split(","))
nums = list(map(int, input().split(",")))
res = bubble_sort(nums, m)
print(res)
```
以上三种方法的时间复杂度均为O(n^2),如果数据规模较大,建议使用更高效的排序算法。
阅读全文