合并排序与快速排序实现

Question

我必须测量使用随机数对文件中的整数进行快速排序和合并排序所花费的时间。

我在网上看到，对于大量数据，合并排序应该比快速排序更快，但我的测量结果恰恰相反，合并排序花费的时间几乎是快速排序的两倍。

是我执行这些算法的问题吗？

测量结果：

快速排序：

5 百万整数 - 715,194,000 纳秒
1000 万整数 - 1,383,187,400 纳秒
5000 万整数 - 6,819,586,800 纳秒
1 亿整数 - 14,159,986,000 纳秒
1.5 亿整数 - 22,431,202,200 纳秒

合并排序：

5 百万整数 - 1,644,349,000 纳秒
1000 万整数 - 2,186,410,800 纳秒
5000 万整数 - 14,427,917,500 纳秒
1 亿整数 - 26,487,337,400 纳秒

1.5 亿整数 - 42,229,109,700 纳秒

 //Quick Sort Implementation
 public static void quickSort(int[] a, int start, int end){
     if(end - start < 2){
        return;
     }

     int pivtIndex = partition(a, start, end);
     quickSort(a, start, pivtIndex);
     quickSort(a, pivtIndex + 1, end);

 }

 public static int partition(int[] a, int start, int end){

     int pivot = a[start];
     int i = start;
     int j = end;

     while(i < j){
         while(i < j && a[--j] >= pivot);
         if(i < j){
             a[i] = a[j];
         }

         while(i < j && a[++i] <= pivot);

         if(i < j){
             a[j] = a[i];
         }
     }

     a[j] = pivot;

     return j;
 }



 //Merge Sort Implementation

 public static void mergeSort(int[] input, int start, int end){
     if(end - start < 2){
         return;
     }

     int mid = (start + end)/2;
     mergeSort(input, start, mid);
     mergeSort(input, mid, end);

     merge(input, start, mid, end);

 }

 public static void merge(int[] input, int start, int mid, int end){
     if(input[mid-1] <= input[mid]){
         return;
     }

     int i = start, j = mid, tempIndex = 0;

     int[] temp = new int[end - start];

     while(i < mid && j < end){
          temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
     }

     System.arraycopy(input, i, input, start + tempIndex, mid - i);
     System.arraycopy(temp, 0, input, start, tempIndex);
 }

Answer 1

在理想世界或真正的随机数字列表中，快速排序应该是最好的，但是当数据出现异常时会出现一些问题。

这看起来像是对原始论文的非常好的实现。我假设您已检查整数确实正确排序。

当您 select 第一个元素作为枢轴时，应该检查 O(N^2) 的一些极端情况。

已经排序，因为您 select 第一个元素作为主元。
管风琴 1,2,3,2,1 也会导致行为不端。
反向排序，如果你取最后一个元素作为主元
很少有唯一性，尝试只有 0,1 的模式
差一点就把几个错位的数字排序了。

对于合并排序，您需要检查 (start + end) 不会导致整数溢出。

在合并排序中，您还可以通过分配的一些智能交换进行优化，这样您只需要分配一次。

当子数组的长度低于某个阈值（通常在 11-32 之间）时，两种算法都可以通过插入排序进行优化。

Answer 2

我认为即使数组的大小在 150 * 10^6 范围内，Quicksort 也一定有优势，原因如下：

假设JAVA中整数的大小为4字节，

(((150 * 10^6 * 4 字节 ) / 1024 字节 ) / 1024 兆字节) ~ 572 MB.

L3 缓存的大小约为 50 MB。

因此，(572 - 50) ~ 522 MB 内存在使用主内存时必须小心（不包括 L1 和 L2，因为它们的大小相对较小）。

现在，对于额外的 522 MB，合并排序必须借助主内存。

因此，很明显归并排序将不得不使用主内存，这是辅助数组所必需的。

访问主内存是一项繁重的操作并且归并排序比快速排序需要更多的内存访问，因为它有附属数组。

合并排序与快速排序实现

Merge Sort vs Quick Sort Implemenation

java

algorithm

mergesort

quicksort