在oj系統上用Python做題顯示超時，有沒有可能是因為性能的問題？

在MOOC學習數據結構，浙大PTA系統，有個是考察排序演算法的（地址：程序設計類實驗輔助教學平台），題目很簡單，但我發現數量級一大就顯示超時，是不是因為Python性能的問題？沒覺得我的排序代碼有什麼大問題，附上我的冒泡排序代碼：

def Bubble_Sort(lst):
lenth = len(lst)
for j in range(lenth - 1):
is_changed = 0
for i in range(lenth - j -1):
if lst[i] &> lst[i + 1]:
lst[i], lst[i + 1] = lst[i + 1], lst[i]
is_changed = 1
if is_changed == 0:
break
return lst

N = int(raw_input())
a = map(int, raw_input().split())
for i in Bubble_Sort(a):
print i,

結果如下，很容易發現達到10^4這個級別就超時了


---

顯然題主是對O(n^2)的複雜度有多慢沒有概念

你自己用不同規模的數據試試看

---

你都冒泡了，超時不很正常？

---

這一看就是沒聽課直接做題的。。。。

---

O(n^2)的演算法 10^4的數據量 C++下 大約在1秒

python 10s也超時 的確python的性能比C++低

lz的結論沒錯 好多強答的 似乎沒有理解lz 以及沒有看題目中的那句話

"本題旨在測試各種不同的排序演算法在各種數據情況下的表現。"

---

我也是醉了。。中國大學mooc和雲課堂既然是一個東西，他們為什麼還要繞來繞去！！！我還以為沒有開課，一直在看以前講的內容。雲課堂里只有第一次講的。今天才發現這個平台。。沒跟上大部隊啊::&>_&<:: 氣死人了！

---

看到問題想進來說是可能的，有的題真得用C++才能過。

後來看到了你的代碼，你這明顯不是語言的性能問題。

---

冒泡也好，快排也好，不知道PTA對時間要求怎麼樣，pat基本都用c/c++

---

你就是拿c寫冒泡也會超時

堆排大法好

---

因為冒泡排序時間複雜度為O(n2)。

1s的話一般1e8的數據量，也就是n&>10000的話，基本就不要用O(n2)的演算法了。

---

推薦閱讀：