# 对快速排序和合并排序进行基准测试，可以使合并排序更快

``````static void mergesort(int arr[]) {
int n = arr.length;
if (n < 2)
return;
int mid = n / 2;
int left[] = new int[mid];
int right[] = new int[n - mid];
for (int i = 0; i < mid; i++)
left[i] = arr[i];
for (int i = mid; i < n; i++)
right[i - mid] = arr[i];
mergesort(left);
mergesort(right);
merge(arr, left, right);
}

public static void merge(int arr[], int left[], int right[]) {
int nL = left.length;
int nR = right.length;
int i = 0, j = 0, k = 0;
while (i < nL && j < nR) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < nL) {
arr[k] = left[i];
i++;
k++;
}
while (j < nR) {
arr[k] = right[j];
j++;
k++;
}
}

``````

``````public static void quickSort(int[] arr, int start, int end) {
int partition = partition(arr, start, end);

if (partition - 1 > start) {
quickSort(arr, start, partition - 1);
}
if (partition + 1 < end) {
quickSort(arr, partition + 1, end);
}
}

public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];

for (int i = start; i < end; i++) {
if (arr[i] < pivot) {
int temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
}
}

int temp = arr[start];
arr[start] = pivot;
arr[end] = temp;

return start;
}
``````
chqrlie：

• `mergesort` 在每个递归调用中分配2个新数组，这很昂贵，但是某些JVM在优化这种编码模式方面出奇地有效。
• `quickSort` 使用的支点选择差，即子数组的最后一个元素，这给排序后的子数组（包括那些具有相同元素的子数组）提供了二次时间。

``````public static void quickSort(int[] arr, int start, int end) {
int p1 = partition(arr, start, end);
int p2 = p1;

/* skip elements identical to the pivot */
while (++p2 <= end && arr[p2] == arr[p1])
continue;

if (p1 - 1 > start) {
quickSort(arr, start, p1 - 1);
}
if (p2 < end) {
quickSort(arr, p2, end);
}
}

public static int partition(int[] arr, int start, int end) {
/* choose pivot at 3/4 or the array */
int i = end - ((end - start + 1) >> 2);
int pivot = arr[i];
arr[i] = arr[end];
arr[end] = pivot;

for (i = start; i < end; i++) {
if (arr[i] < pivot) {
int temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
}
}

int temp = arr[start];
arr[start] = pivot;
arr[end] = temp;

return start;
}
``````

`quickSort`由于选择了支点，因此对其他非随机分布的进一步测试表明此实现具有灾难性的性能根据我的基准，通过选择在数组的3/4或2/3处旋转元素，可以大大提高性能（对于50k样本，其性能提高了300倍，比标准合并排序快40％，可比时间缩短`radix_sort`）。

• Mergesort具有对所有分布稳定且可预测的显着优势，但是它需要在数据集大小的50％到100％之间的额外内存。
• 精心实施的Quicksort在许多情况下会更快一些，并且可以就地执行，只需要log（N）堆栈空间即可递归。但是它并不稳定，量身定制的发行版将表现出灾难性的性能，甚至可能崩溃。
• 对于OP的数据集而言，Countingsort将是最有效的，因为它只需要一个128个整数数组即可计算不同值的出现次数，已知范围为0..127。对于任何分布，它将在线性时间内执行。

0 条评论