时间戳

首页 > 解决方案 > 计算交换次数以按降序对列表进行排序

python - 计算交换次数以按降序对列表进行排序

问题描述

我正在尝试按降序对列表进行排序，并获取按降序对列表进行排序所需的交换次数 [3, 1, 2] → [3, 2, 1]。即使用python从列表的最高元素到最低元素。我拥有的功能是以升序对列表进行排序，即 [3, 1, 2] → [1, 2, 3] 。我将如何按降序对其进行排序并获得对列表进行排序所需的交换次数？

            def count_inversions(ratings):
                swap = 0;
                for i in range(len(ratings)):
                    if(i + 1 != ratings[i]):
                        t = i 
                        while(ratings[t] != i+1):
                            t++
                        temp = ratings[t]
                        ratings[t] = ratings[i]
                        ratings[i] = temp
                        swap = swap + 1

                return swap

标签： pythonsortingbubble-sort

解决方案

我前段时间写了一个冒泡排序代码，它可能对你有帮助

def bubble_sort(arr, reversed=False):
    swap_cnt = 0
    i = len(arr) - 1
    while i > 0:
        for j in range(i):
            if not reversed:
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swap_cnt += 1
            if reversed:
                if arr[j] < arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swap_cnt += 1
        i -= 1
    print('Number of swaps: {}'.format(swap_cnt))
    return arr

if __name__ == "__main__":
    print(bubble_sort([2, 4, 8, 5, 1, 9, 4]))
    print(bubble_sort([2, 4, 8, 5, 1, 9, 4], reversed=True))

推荐阅读