各位好，小弟有一个算法的问题想请教各位大大
有一个阵列，内有若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不会漏判啊为何要扫左右两边？