Сортировка слиянием так же проста
Пузырьковая сортировка, сортировка выбором, сортировка вставками и быстрая сортировка были объяснены с начала.Основные темы в этой главе:Сортировка слиянием, я надеюсь, вы сможете понять и написать код сортировки слиянием и быстрой сортировки после прочтения, а затем пройти собеседование! Если я не прав, укажите на это в комментариях.
Введение в сортировку слиянием
Источник Энциклопедия Baidu:
Сортировка слиянием (MERGE-SORT) — это эффективный алгоритм сортировки, основанный на операции слияния.разделяй и властвуйОчень типичное применение (разделяй и властвуй). Объедините упорядоченные подпоследовательности, чтобы получить полностью упорядоченную последовательность, то есть сначала сделайте каждую подпоследовательность упорядоченной, а затем сделайте упорядоченными сегменты подпоследовательности.Если два отсортированных списка объединяются в один отсортированный список, это называется двусторонним слиянием.
Описание процесса:
Процесс слияния: сравнить размер a[i] и b[j], если a[i]≤b[j], затем скопировать элемент a[i] из первого упорядоченного списка в r[k] и добавить 1 к i и k соответственно, в противном случае скопировать элемент b[j] из второго упорядоченного списка в r[k] и добавить 1 к j и k соответственно, и так далее, пока не будет взят отсортированный список After one, остальные элементы в другом отсортированном списке копируются в ячейки от нижнего индекса k до нижнего индекса t в r. Алгоритм сортировки слиянием обычно реализуется рекурсивно: сначала сортируемый интервал [s, t] делится средней точкой, затем сортируется левый подинтервал, затем правый подинтервал и, наконец, левый подинтервал. а правые интервалы объединяются одной операцией Объединение в упорядоченные интервалы [s,t].
принцип:
Операция слияния работает следующим образом:
Шаг 1: Подайте заявку на пространство, чтобы его размер был суммой двух отсортированных последовательностей, и это пространство использовалось для хранения объединенной последовательности.
Шаг 2: Установите два указателя, начальные позиции являются начальными позициями двух отсортированных последовательностей.
Шаг 3: Сравните элементы, на которые указывают два указателя, выберите относительно небольшой элемент, чтобы поместить его в пространство слияния, и переместите указатель в следующую позицию.
Повторяйте шаг 3, пока указатель не превысит конец последовательности.
Скопируйте все оставшиеся элементы другой последовательности непосредственно в конец объединенной последовательности.
Вот небольшое резюме:
- будетдваужеотсортированныймассивсливатьсястатьсанитармассив , называемый сортировкой слиянием
- Шаги: просмотрите два массива и сравните их значения. Тот, кто меньше, будет помещен в больший массив первым, пока обход массива не будет завершен.
1. Процесс сортировки слиянием исчисления
Теперь у меня есть два уже отсортированных массива:int[] arr1 = {2, 7, 8}иint[] arr2 = {1, 4, 9}, у меня также есть большой массив для их загрузкиint[] arr = new int[6];
1.1
Затем я сравниваю значения двух массивов,Тот, у кого меньшее значение, будет помещен в больший массив!
Во-первых, выньтеarr1[0]иarr2[0]для сравнения видимоarr2[0]относительно небольшой, поэтомуarr2[0]в большой массив,в то же времяarr2Указатель на шаг назад
Итак, покаarr = {1}
1.2
Затем взятьarr1[0]иarr2[1]для сравнения видимоarr1[0]относительно небольшой, т.arr1[0]в большой массив,в то же времяarr1Указатель на шаг назад
Итак, покаarr = {1,2}
1.3
Затем взятьarr1[1]иarr2[1]для сравнения видимоarr2[1]относительно небольшой, т.arr2[1]в большой массив,в то же времяarr2Указатель на шаг назад
Итак, покаarr = {1,2,4}
........
В конце обхода будемдваотсортированный массивстатьотсортированный массивarr = {1,2,4,7,8,9}
Во-вторых, анализ предпосылок сортировки слиянием (метод «разделяй и властвуй»).
Из приведенного выше исчисления мы получаем до тех пор, пока, сортировка слияниемПредпосылка заключается в том, что вам нужны два массива, которые были отсортированы,Тотчасто нетНам даются два массива, которые были расположены по порядку,** (обычно массив, который неорганизован)**, так что этот алгоритм очень безвкусен? ?
Не совсем так, во-первыхПредположениеМассив, указанный в заголовке, выглядит следующим образом:int[] arr = {2, 7, 8, 1, 4, 9};
Когда мы собираемся слиться сarr[3]То есть место, где элемент равен 1, отделено. да, тогда используйте指针Lнаправлениеarr[0],Один指针Mнаправлениеarr[3], с指针Rнаправлениеarr[5](последняя цифра массива). С помощью указателей мы можемЭтот массив можно разбить на два упорядоченных массива(Способ работы может быть таким же, как указано выше)
Однако, как упоминалось выше, обычно считается, чтонеорганизованныйМассив , который по-прежнему не соответствует требованиям. Например, для такого массива:int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
На этом этапе мы должны использоватьразделяй и властвуйПродуманный:
- Тогда мы также можем думать о
int[] arr = {2, 7, 8, 1, 4, 9};Массив разбит на части,arr[0]Это упорядоченный «массив»,arr[1]Это также упорядоченный «массив», использующий указатели (L, M, R) длярисунокСортировка аналогична работе с двумя массивами. окончательный синтез{2,7}.......СноваПостоянно разделяйте и объединяйте, наконец, вернемся к нашемуarr = {1,2,4,7,8,9},следовательноСортировка слиянием может сортировать беспорядочные массивы
Это наш метод разделяй и властвуй --->Разделите большую проблему на множество мелких проблем, которые нужно решить, и, наконец, соберите их вместе.
Три, реализация кода слияния
Этапы реализации:
- расколоть
- сливаться
........
public static void main(String[] args) {
int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
mergeSort(arrays, 0, arrays.length - 1);
System.out.println("公众号：Java3y" + arrays);
}
/**
* 归并排序
*
* @param arrays
* @param L 指向数组第一个元素
* @param R 指向数组最后一个元素
*/
public static void mergeSort(int[] arrays, int L, int R) {
//如果只有一个元素，那就不用排序了
if (L == R) {
return;
} else {
//取中间的数，进行拆分
int M = (L + R) / 2;
//左边的数不断进行拆分
mergeSort(arrays, L, M);
//右边的数不断进行拆分
mergeSort(arrays, M + 1, R);
//合并
merge(arrays, L, M + 1, R);
}
}
/**
* 合并数组
*
* @param arrays
* @param L 指向数组第一个元素
* @param M 指向数组分隔的元素
* @param R 指向数组最后的元素
*/
public static void merge(int[] arrays, int L, int M, int R) {
//左边的数组的大小
int[] leftArray = new int[M - L];
//右边的数组大小
int[] rightArray = new int[R - M + 1];
//往这两个数组填充数据
for (int i = L; i < M; i++) {
leftArray[i - L] = arrays[i];
}
for (int i = M; i <= R; i++) {
rightArray[i - M] = arrays[i];
}
int i = 0, j = 0;
// arrays数组的第一个元素
int k = L;
//比较这两个数组的值，哪个小，就往数组上放
while (i < leftArray.length && j < rightArray.length) {
//谁比较小，谁将元素放入大数组中,移动指针，继续比较下一个
if (leftArray[i] < rightArray[j]) {
arrays[k] = leftArray[i];
i++;
k++;
} else {
arrays[k] = rightArray[j];
j++;
k++;
}
}
//如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中(剩下的都是大数字)
while (i < leftArray.length) {
arrays[k] = leftArray[i];
i++;
k++;
}
//如果右边的数组还没比较完，左边的数都已经完了，那么将右边的数抄到大数组中(剩下的都是大数字)
while (j < rightArray.length) {
arrays[k] = rightArray[j];
k++;
j++;
}
}
Когда я отлаживал его в первый раз, было легче понять:
- Разделите первые два большого массива и загрузите его массивом
- Сравните элементы меньшего массива, которые меньше, в зависимости от того, что меньше, сначала поместите его в больший массив
Вышеупомянутые два шага непрерывно зацикливаются, и, наконец, получается упорядоченный массив:
В-четвертых, оптимизация сортировки слиянием
источник:Блог Wooooooo.cn на.com/no king/fear/79…
Здесь я разберу основные моменты, заинтересованные студенты могут прочитать по ссылке выше:
- Когда рекурсия достаточно мала, используйте сортировку вставками
- Перед слиянием определите, нужно ли слияние
- Делайте пробел только один раз перед сортировкой
Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y