各位好，小弟有一個演算法的問題想請教各位大大
有一個陣列，內有若N個不相同且隨機排列的數字
如：2 8 6 1 9 10 13 0
我需要依照陣列順序把排在自己之後而且比自己小的數字印出來
像這樣：
2 1
2 0
8 6
8 1
8 0
6 1
6 0
9 0
10 0
13 0
我知道如果用迴圈一個一個檢查總是有結果的
但是演算法效率是O(n^2)
想請問各位有沒有比O(n^2)更快的做法??
我想了很久，但都沒有比較好的解法...
不好意思麻煩各位了

沒錯 只是要印出來

極端來講，我給你8 7 6 5 4 3 2 1，你光是印出答案就需要O(n^2)，頂多係數可以給你最小化到1/2罷了直接做O(n log n) sort並保留原始順序的link，期待印出步驟的次數期望值落在O(n log n)也許比較實在

考慮merge sort，在merge時加個一兩行就行了

類別二欄位index和value，排序後判斷索引輸出得解。

mergesort怎會變成O(n^2)

回原po，n個都要列出關係起算就n往上了。一樓說得很白。

解的大小本來就Ω(n^2)了 所以merge sort複雜度應該是O(nlogn + k) k是解大小~

比較快的方法應該是hashing/counting sort/位元操作之類的如果只能兩兩比較的話，那麼就是推文一樓說的那樣子，接下來的方向會是隨機算法/平滑分析之類的另外這題有個有趣的性質：當數值（連帶索引值）重新排序之後問題變成找到後方的更大索引值，類似於原本問題，但是索引值的範圍會是連續正整數，成為更簡單一點的問題至於這性質有什麼用...我也不知道 XD

count inversion problem?

看起來超像逆序數對，merge nlogn不會漏判啊為何要掃左右兩邊？