为某些数组寻找最快的排序算法

Question

我有一些已被排序的短数组。然后，我想将它们合并成一个大数组，并需要保持顺序。因此，如何在最快的时间和最简单的复杂性中实现这一点。

例如，我有三个短数组：

1. 1 2 3 5 9
2. 4 6 8 10 11
3. 7 12 15 20 21

合并结果为:1 2 3 4 5 6 7 8 10 11 12 15 20 21

当然，上面的例子很简单。事实上，我的最终结果可能是100万个整数在一起，可能是一些简单的算法可以应用到工作中，如气泡排序、快速排序或堆排序等等，但我想要最佳的有效算法。你能给出一些决心或好建议吗？

谢谢大家在下面回答这个问题。我只是在写一些测试的例程。我将使用插入排序算法，并比较STL快速排序，这是我的旧版本项目，所以我想看看哪个更快？

在我看来，插入排序将增强处理，因为所有短数组的预排序特性。我需要将其他短数组逐一插入到第一个短数组中。另一件更有帮助的事情是，其他短数组的第一个元素可以告诉您在第一个观察者之后的基本插入位置，因此在处理后一个元素时避免访问整个数组。你能听懂我在说什么吗？伙计们，等我的测试结果。谢谢!

Answer 1

当对所有三个数组进行排序时，我们可以有一个简单的algo，它合并了O(n)中的三个数组，其中n是数组的长度。这种想法类似于合并排序中的合并部分。

• 从每个数组的开头开始，将这些元素进行比较，以找到这3个数组中的最小值。将最小值添加到结果中。
• 从已采用最小元素的数组中增加索引。
• 重复这个过程。

Java代码：

public int[] sort(int[][] data) {
    int n = 0;//Total length of all arrays
    for(int i = 0; i < data.length; i++){
        n += data[i].length;
    }
    int[] index = new int[data.length];//Array to hold the index of each arrays
    int []result = new int[n];
    for (int i = 0; i < n; i++) {
         int min = -1;
         for (int j = 0; j < data.length; j++) {//Find the smallest element in all arrays
              if (index[j] < data[j].length){
                  if(min == -1 || data[min][index[min]] > data[j][index[j]]){
                     min = j;
                  }                    
              }
         }
         result[i] = data[min][index[min]];
         index[min]++;
    }
    return result;
 }

编辑：如果数组的数量是变化的，那么上面的algo是O(m*n)，而m是数组的数目。

另一种改进该方法的方法是引入一个min heap data - structure，它的堆大小总是<= m，当有一个元素从堆中弹出时，来自同一个数组的一个元素将被带回堆中，这使得algo的时间复杂度为O(n log m)。