fh-2022算法考试编程题-2

小A有一套特殊的卡牌，他们是1-N的数字的排列，每个数字有且仅有一张卡。

小A在洗牌之后，会把卡牌并排放在地上。

小A总是在通过卡牌的交换位置来获得1,2,3....N的序列。假如初始序列是2、3、5、4、1，我们就可以按照以下方式对它们进行排序： 

初始状态：2 3 5 4 1

第一次后：1 3 5 4 2

第二次后：1 3 2 4 5

第三次后：1 2 3 4 5 

所以，这里小A对卡牌进行了三次交换。

那么我们的问题是，给定一个特定卡牌序列，小A最少需要进行多少次互换才能达成她的目标。

测试用例：

[1]、输入 2,3,5,4,1 输出 3

[2]、输入 1,2,4,3,6,5,7 输出 2

# -*- coding:utf-8 -*-
# file: fun2.py
# author: 
# datetime: 2022/9/17
# software: PyCharm

def alg_sort(seq: list) -> int:
    """
    问题：按规定方式进行排序，例如
    由以上例子可知，该排序为选择排序的变种。
    首先，在未排序序列中找到最小值，放到排序序列的起始位置。然后，在未排序序列中找到最大值，放到排序排序的末端位置。
    以此规律对未排序序列继续排序，直至所有元素排序完毕。
    :param seq:待排序的序列，[a,b,c,d,e,...]
    :return: 排序所需次数
    """
    # 计数
    times = 0
    n_seq = len(seq)
    # 初始化起始和结束位置
    start = 0
    end = n_seq
    for i, _ in enumerate(seq):
        # 偶数位置找最小值
        if i % 2 == 0:
            # 未排序序列
            tmp_seq = seq[start:end]
            # 获取最小值和索引位置，此处min函数也可以自己使用for循环来判断
            mn = min(tmp_seq)
            ind = tmp_seq.index(mn)+start
            # 更新位置
            if start != ind:
                seq[ind] = seq[start]
                seq[start] = mn
                # print(seq)
                # 更新一次
                times += 1
            # 起始位置更新
            start += 1
        # 奇数位置找最大值
        else:
            # 未排序序列
            tmp_seq = seq[start:end]
            # 获取最小值和索引位置，此处max函数也可以自己使用for循环来判断
            mx = max(tmp_seq)
            ind = tmp_seq.index(mx)+start
            # 更新位置
            index_end = end - 1
            if index_end != ind:
                seq[ind] = seq[index_end]
                seq[index_end] = mx
                # print(seq)
                # 更新一次
                times += 1
            # 结束位置更新
            end -= 1
    print(times)
    return times


if __name__ == '__main__':
    # 测试用例
    # input_1 = [2, 3, 5, 4, 1]
    input_2 = [1, 2, 4, 3, 6, 5, 7]
    output = alg_sort(input_2)