Posts pythonTip 103 输出交换次数
Post
Cancel

pythonTip 103 输出交换次数

题目描述: 给你一个list L, 如 L=[2,8,3,50], 对L进行选择排序并输出交换次数, 如样例L的结果为1

示例: 输入: L = [4, 2, 25, 7777777, 100, 3, 77777777, 77777777, 77777777, 77777777] 输出:4

分析:

选择排序 这是一个关键。首先要明白选择排序的步骤是什么?

选择排序

选择排序 可以分为两个数组,第一个数组为 已排序数组, 第二个数组为 待排序数组

选择排序算法步骤:

  • 初始化时,已排序数组为空
  1. 找到待排序数组中的最小元素 和 待排序数组中的第一个元素交换。(如果第一个元素就是最小元素,则不用交换)
  2. 将 待排序数组中的第一个元素拿出来,放到已排序数组的末尾。
  • 依次重复 1, 2 直到 待排序数组为空

例如:1234 76895, 前一个数组为 已排序数组,后一个为 待排序数组。此时待排序数组最小元素为 5。 然后把 5 和 9交换,再加入到 已排序数组中。结果为: 12345 6897

代码:

1
2
3
4
5
6
7
8
9
ans = 0

for i in range(len(L)):
    minn = min(L[i:])
    pos = L[i:].index(minn)
    if pos != 0:
        L[pos+i], L[i] = L[i], L[pos+i]
        ans += 1
print(ans)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 102 又是字符串

pythonTip 104 Python之殇

Trending Tags