Сначала рассмотрим, как объединить две упорядоченные последовательности. Это очень просто. Просто сравните первое число из двух последовательностей и сначала возьмите меньшее. Взяв его, удалите число в соответствующей последовательности. Затем сравните их. Если один из столбцов пуст, просто вынимайте данные из другого столбца по одному.
Скопируйте код кода следующим образом:
Посмотреть код
//Объединяем упорядоченные массивы a[] и b[] в c[]
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
интервал я, j, к;
я = j = к = 0;
в то время как (i < n && j < m)
{
если (a[i] < b[j])
с[к++] = а[я++];
еще
с[к++] = б[j++];
}
в то время как (я < п)
с[к++] = а[я++];
в то время как (j < m)
с[к++] = б[j++];
}
Видно, что эффективность объединения упорядоченной последовательности относительно высока и может достигать O(n).
После решения описанной выше проблемы слияния упорядоченных последовательностей давайте рассмотрим сортировку слиянием. Основная идея состоит в том, чтобы разделить массив на две группы A и B. Если все данные в этих двух группах упорядочены, то это можно легко разделить на эти два набора. данных сортируются. Как сохранить данные в этих двух группах в порядке?
Группы А и Б можно разделить на две группы. По аналогии, когда в отделенной группе есть только одни данные, можно считать, что группа достигла порядка, и тогда две соседние группы можно объединить. Таким образом, сортировка слиянием завершается сначала рекурсивным разложением массива, а затем его объединением.
Скопируйте код кода следующим образом:
Посмотреть код
//Объединим две упорядоченные последовательности a[first...mid] и a[mid...last].
void mergearray(int a[], int first, int middle, int Last, int temp[])
{
int я = первый, j = середина + 1;
int m = середина, n = последний;
интервал к = 0;
в то время как (i <= m && j <= n)
{
если (a[i] <= a[j])
temp[k++] = а[i++];
еще
temp[k++] = а[j++];
}
в то время как (я <= м)
temp[k++] = а[i++];
в то время как (j <= n)
temp[k++] = а[j++];
для (я = 0; я <к; я++)
а[первый + я] = темп[я];
}
void mergesort(int a[], int first, int Last, int temp[])
{
если (первый <последний)
{
int Mid = (первый + последний)/2;
mergesort(a, first, middle, temp); //Левая сторона сортируется;
mergesort(a, Mid + 1, Last, Temp); //Правая часть сортируется;
mergearray(a, first,mid,last,temp); //Объединяем два упорядоченных массива;
}
}
bool MergeSort(int a[], int n)
{
int *p = новый int[n];
если (p == NULL)
вернуть ложь;
mergesort(a, 0, n - 1, p);
удалить [] р;
вернуть истину;
}
Эффективность сортировки слиянием относительно высока. Предположим, что длина последовательности равна N. Для разделения последовательности на десятичные последовательности требуется logN шагов. Каждый шаг представляет собой процесс слияния упорядоченной последовательности. Временную сложность можно записать как O(. N), поэтому общая сумма равна O(N*logN). Поскольку сортировка слиянием каждый раз оперирует соседними данными, несколько методов сортировки слиянием (быстрая сортировка, сортировка слиянием, сортировка Хилла, сортировка кучей) за O(N*logN) также относительно эффективны.