你曾經嘗試過哪些大數據排序方案，這些方法各自有哪些優劣勢？

02-13

非特定需求型問題，請大家走過路過隨手留個答案

內存裝得下用三向切分快速排序，內存裝不下用歸併排序。

重複元素不多是普通的快速排序即可，重複元素很多時三向切分快速排序性能更佳。

空間複雜度

歸併排序的空間複雜度不是最優的，需要另外一個數組來存放排序結果。對於大數據可以考慮用輸入輸出流。

快速排序是原地排序。

時間複雜度

歸併排序比快速排序穩定，二者理性情況下的時間複雜度都是 $NlgN$ 。

快速排序的平均時間複雜度是 $2NlnNapprox 1.39NlgN$ ，最壞情況 $N^{2} /2$ 。

歸併排序一般都比較趨向於 $NlgN$

求MAX(N)或者MIN(N)

如果僅僅是尋找大數據中最大或者最小的N個元素，不需要全局排序，採用優先隊列即可。

語言內置的排序演算法

java.util.Arrays.sort()

對於原始類型使用（三向切分的）快速排序，對於引用類型使用歸併排序

python sort

早期版本採用快速排序，2.3版本以後採用了timsort（一種適應性歸併排序）

Ruby Array.sort

採用native實現的快速排序

請用mapreduce然後根據不同的業務需求做一定修改就OK.不然就自己擼個集群的合併排序即可！