Ответ 1
элементы массива имеют число от 1 до 10.
С этим ограничением подсчет сортировки будет намного более эффективным, чем любой алгоритм сортировки общего назначения - он O (n)
В соответствии с заголовком вопроса, если массив имеет нечетную длину, а элементы массива пронумерованы 1 - 10.
Пример,
3 6 8 1 3 7 7 9 4 1
Я думал об использовании heapsort? Поскольку это массив, сортировка сортировки и вставки сортировки требует смещения и не будет настолько эффективной.
элементы массива имеют число от 1 до 10.
С этим ограничением подсчет сортировки будет намного более эффективным, чем любой алгоритм сортировки общего назначения - он O (n)
Это мой пример сортировки подсчета
static int[] countingSort(int[] numbers) {
int max = numbers[0];
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] > max)
max = numbers[i];
}
int[] sortedNumbers = new int[max+1];
for (int i = 0; i < numbers.length; i++) {
sortedNumbers[numbers[i]]++;
}
int insertPosition = 0;
for (int i = 0; i <= max; i++) {
for (int j = 0; j < sortedNumbers[i]; j++) {
numbers[insertPosition] = i;
insertPosition++;
}
}
return numbers;
}
Если есть только 10 элементов, вам не стоит даже беспокоиться об этом. Если есть миллион, это может стать значительным.
Редактировать. Сортировка подсчета, вероятно, оптимальна с учетом ограничения того, что элементы варьируются от 1 до 10. Сортировка, применяемая к этой проблеме, будет выполняться в O (n) времени. Сортировка слияния (как я рекомендовал ниже) будет работать не лучше, чем O (nlogn). Параллельность сортировки может быть интересной. Просто назначьте подрамник с n/p элементами для каждого процессора. Каждый процессор будет иметь свой собственный массив count размером 9. Этот шаг должен принимать время O (n/p). Затем объедините все массивы count в единый массив, который должен занять время O (p). Я не продумал последний шаг в сортировке подсчета, где элементы упорядочены, но кажется, что элементы массива count являются атомарными, вы можете назначить n/p-секции исходного массива индивидуальным процессоров и добиться некоторой распараллеливания. Было бы возражение на отдельные элементы массива count, однако потенциально существенно уменьшилось бы concurrency. Возможно, вы сможете назначить подразделы массива count на p-процессоры, и вы вернетесь к O (n/p) времени выполнения, если элементы распределены достаточно равномерно, но вы ограничены 10 процессорами. Если элементы распределены равномерно, один или несколько процессоров могут выполнять большую часть работы. Это большой вопрос; можете ли вы выполнить сортировку в O (n/p) времени?
Quicksort - отличный алгоритм сортировки на месте, который быстро работает и сохраняет память. Однако, учитывая, что элементы имеют диапазон от 1 до 10, если вы сортируете большое количество элементов, вы получите большие прогоны того же числа, либо изначально, либо в промежуточные моменты времени во время сортировки. Массивы или суб-массивы в порядке могут портить производительность Quicksort.
Если вы не заботитесь о памяти, достаточно простого Mergesort. Mergesort работает с самыми быстрыми стандартными алгоритмами сортировки.
Стандартная реализация Collections.sort() по умолчанию в Java 7 - это алгоритм Mergesort, адаптированный из "TimSort". По умолчанию реализация Arrays.sort() в Java 7 представляет собой двойной скремблер Quicksort.
Если вы хотите пойти параллельно, Parallel Quicksort может добиться хороших результатов на больших массивах с небольшим количеством процессоров, но с теми же ограничениями, что и последовательный Quicksort. PSRS может помочь масштабировать большее количество процессоров.
Вы должны рассмотреть этот график сложности Таблица сравнения сложности.
Сравнение алгоритма сортировки основано на их наилучшем, среднем, худшем сценарии для временной и пространственной сложности. На этой диаграмме вы можете увидеть Counting Sort лучше всего подходит как по сложности, так и по времени. Другим сопоставимым методом является сортировка Radix.
Худшая [Время, Пространство] сложность "Counting Sort": - [O (n + k), O (k)].
Худшая [время, пробел] сложность "Radix Sort": - [O (nk), O (n + k)].
это пример простой сортировки (сортировка вставки)
private static void insertionSort(int[] a) {
// [230, 23, 45, 34, 98]
for (int j = 2; j < a.length; j++) {
int key = a[j];
int i = j - 1;
while (i > 0 && a[i] > key) {
a[i + 1] = a[i];
i--;
}
a[i + 1] = key;
}
System.out.println("sorted array: " + Arrays.toString(a));
}
Сортировка сортировки будет лучше всего в этом сценарии.
Предполагая, что данные являются целыми числами, в диапазоне 0-k. Создайте массив размера K, чтобы отслеживать, сколько элементов отображается (3 элемента со значением 0, 4 элемента со значением 1 и т.д.). Учитывая этот счет, вы можете указать позицию элемента - все 1 должны появиться после 0, из которых 3. Следовательно, 1-е начало начинается с элемента №4. Таким образом, мы можем сканировать элементы и вставлять их в правильное положение.
Создание массива count - это O (N) Вставка элементов в их правильное положение - O (N) Я упростил здесь - суммирование счетчиков и упорядочение с наименьшим наименьшим порядком, которое сохраняет стабильную сортировку.