<p>我正在解决下面的冒泡排序算法。你知道吗</p>
<p>但是,该算法似乎不是常见的冒泡排序实现。我已经实现了以下代码,但它将超时。原因是我的代码的时间复杂度仍然是O(n^2)。你知道吗</p>
<p>如何编写气泡排序的代码来正确理解和解决问题?你知道吗</p>
<p><strong>解决方案</strong></p>
<blockquote>
<p>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.</p>
<ol>
<li><p>Compare the first value with the second value, and change the position if the first value is greater.</p></li>
<li><p>Compares the second value with the third value, and changes the position if the second value is greater.</p></li>
</ol>
<p>...</p>
<ol start="3">
<li>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.</li>
</ol>
</blockquote>
<p><strong>输入</p>
<blockquote>
<p>N and K are given in the first line.</p>
<p>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.</p>
<p>1 <= N <= 100,000
1 <= K <= N
Each term in the sequence is an integer from 1 to 1,000,000,000.</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>The above steps are repeated K times and the status of the sequence is output.</p>
</blockquote>
<p><strong>命令行</p>
<pre><code>Example input
4 1
62 23 32 15
Example output
23 32 15 62
</code></pre>
<p><strong>我的代码</strong></p>
<pre><code>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)
</code></pre>