Вчера я работал над реализацией быстрой сортировки, а затем запустил ее, ожидая более быстрого выполнения, чем сортировка слиянием (которую я также реализовал). Я выполнил оба, и хотя быстрая сортировка была быстрее для небольших наборов данных - 100 элементов (и я действительно убедился, что она работает), сортировка слиянием довольно быстро стала более быстрым алгоритмом. Меня учили, что быстрая сортировка почти всегда «быстрее», чем сортировка слиянием, и я понимаю, что по этой теме ведутся споры, но я, по крайней мере, ожидал, что она будет ближе, чем эта. Для наборов данных> 10000 элементов сортировка слиянием была более чем в 4 раза быстрее. Этого следует ожидать, или в моем коде быстрой сортировки есть ошибка?
Сортировка слиянием:
public static void mergeSort(int[ ] e)
{
if (e.length <= 1) return;
int[] first = new int[e.length/2];
int[] second = new int[e.length - first.length];
System.arraycopy(e, 0, first, 0, first.length);
System.arraycopy(e, first.length, second, 0, second.length);
mergeSort(first);
mergeSort(second);
System.arraycopy(merge(first, second), 0, e, 0, e.length);
}
private static int[] merge(int[] first, int[] second) {
int iFirst = 0;
int iSecond = 0;
int iCombined = 0;
int[] combined = new int[first.length + second.length];
while(iFirst < first.length && iSecond < second.length) {
if (first[iFirst] > second[iSecond]) {
combined[iCombined++] = second[iSecond++];
}
else combined[iCombined++] = first[iFirst++];
}
for(; iFirst < first.length; iFirst++) {
combined[iCombined++] = first[iFirst];
}
for(; iSecond < second.length; iSecond++) {
combined[iCombined++] = second[iSecond];
}
return combined;
}
быстрая сортировка:
public static void quicksort(int[] a, int first, int last) {
if (first >= last) return;
int partitionIndex = partition(a, first, last);
quicksort(a, first, partitionIndex - 1);
quicksort(a, partitionIndex + 1, last);
}
public static int partition(int[] x, int first, int last) {
int left = first;
int right = last;
int pivot = x[first];
int pivotIdx = first;
while(left <= right) {
while(left < x.length && x[left] <= pivot) left++;
while(right >= 0 && x[right] > pivot) right--;
if (left <= right) {
int temp = x[left];
x[left] = x[right];
x[right] = temp;
}
}
pivotIdx = right;
x[first] = x[right];
x[pivotIdx] = pivot;
return pivotIdx;
}
