如何实现只执行“K”次的冒泡排序

Question

我正在解决下面的冒泡排序算法。你知道吗

但是，该算法似乎不是常见的冒泡排序实现。我已经实现了以下代码，但它将超时。原因是我的代码的时间复杂度仍然是O（n^2）。你知道吗

如何编写气泡排序的代码来正确理解和解决问题？你知道吗

解决方案

Bubble sorting is an algorithm that sorts sequences of length N in such a way that two adjacent elements are examined to change their positions. Bubble sorting can be performed N times as shown below.

1. Compare the first value with the second value, and change the position if the first value is greater.

2. Compares the second value with the third value, and changes the position if the second value is greater.

...

3. Compare the N-1 and N-th values, and change the position if the N-1th value is greater. I know the result of bubble sorting, so I know the intermediate process of bubble sorting. However, since N is very large, it takes a long time to perform the above steps K times. Write a program that will help you to find the intermediate process of bubble sorting.

输入

N and K are given in the first line.

The second line gives the status of the first sequence. That is, N integers forming the first sequence are given in turn, with spaces between them.

1 <= N <= 100,000 1 <= K <= N Each term in the sequence is an integer from 1 to 1,000,000,000.

输出

The above steps are repeated K times and the status of the sequence is output.

命令行

Example input
4 1
62 23 32 15
Example output
23 32 15 62

我的代码

n_k = input()  # 4 1
n_k_s = [int(num) for num in n_k.split()]

progression = input()  # 62 23 32 15 => 23 32 15 62
progressions = [int(num) for num in progression.split()]


def bubble(n_k_s, progressions):
    for i in range(0, n_k_s[1]):
        for j in range(i, n_k_s[0]-1):
            if (progressions[j] > progressions[j+1]):
                temp = progressions[j]
                progressions[j] = progressions[j+1]
                progressions[j+1] = temp
    for k in progressions:
        print(k, end=" ")


bubble(n_k_s, progressions)

Answer 1

据我所知，您已经实现了所请求的算法。它已经涵盖了我输入的基本原理。你知道吗

是的，您可以设置一个标志来指示您是否在此通行证上进行了任何交换。这不会改变任何复杂度，除了最佳情况，尽管在许多其他情况下它确实减少了常数因子。你知道吗

我认为加快进程的一种可能性是使用更有效的值交换：使用Python习惯用法a, b = b, a。在您的情况下，内部循环可能会变成：

done = True
for j in range(i, n_k_s[0]-1):
    if progressions[j] > progressions[j+1]:
        progressions[j], progressions[j+1] = progressions[j+1], progressions[j]
        done = False
if done:
    break

Answer 2

我不明白你为什么说“原因是我的代码的时间复杂度仍然是O（n^2）”

时间复杂度始终为O（n²），除非添加一个标志来检查列表是否已排序（如果列表在程序开始时排序，则复杂度现在将为0（n））