Нашел специфический алгоритм, называется "Circle Sort". Он сравнивает крайние элементы массива, постепенно доходя до середины, а потом рекурсивно сортирует свои меньшие части. Правда, за раз он не всегда все делает, поэтому нужно пройтись несколько раз. Согласно рекомендации, его можно оптимизировать, если после 0,5 log(n) кругов все добить сортировкой вставками. Скорость, конечно, так себе, но выглядит интересно. Но можно ли из него выжать еще больше, допустим, избавившись от рекурсии? (И сильно ли рекурсия влияет на скорость?)
public void sort(int[] array) {
int numOfSwaps = 0;
for (int i = (int) (0.5 * Math.log(array.length)); i >= 0; i--) {
numOfSwaps = circleSort(array, 0, array.length - 1, 0);
}
if (numOfSwaps != 0) {
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i;
while (j > 0 && array[j - 1] > temp) {
array[j] = array[j - 1];
j = j - 1;
}
array[j] = temp;
}
}
}
private int circleSort(int[] array, int lowerBound, int higherBound, int numOfSwaps) {
if (lowerBound == higherBound) return numOfSwaps;
int low = lowerBound;
int high = higherBound;
int middle = (higherBound - lowerBound) / 2;
while (lowerBound < higherBound) {
if (array[lowerBound] > array[higherBound]) {
int temp = array[lowerBound];
array[lowerBound] = array[higherBound];
array[higherBound] = temp;
numOfSwaps++;
}
lowerBound++;
higherBound--;
}
if (lowerBound == higherBound && array[lowerBound] > array[higherBound + 1]) {
int temp = array[lowerBound];
array[lowerBound] = array[higherBound + 1];
array[higherBound + 1] = temp;
numOfSwaps++;
}
numOfSwaps = circleSort(array, low, low + middle, numOfSwaps);
numOfSwaps = circleSort(array, low + middle + 1, high, numOfSwaps);
return numOfSwaps;
}
Средний
