Сорт -сортировка - это эффективный алгоритм сортировки, основанный на операции слияния. Этот алгоритм является очень типичным применением разделения и завоевания.
Метод сортировки слияния состоит в том, чтобы объединить две (или более двух) упорядоченных таблиц в новую упорядоченную таблицу, то есть разделить последовательность, которая будет сортирована на несколько последствий, каждая подпоследовательность упорядочена. Затем упорядоченные последующие последствия объединяются в общую упорядоченную последовательность.
Сортировка слияния - это эффективный алгоритм сортировки, основанный на операции слияния. Этот алгоритм является очень типичным применением разделения и завоевания. Объедините упорядоченные последующие последствия, чтобы получить полностью упорядоченную последовательность; Если две заказанные таблицы объединены в одну упорядоченную таблицу, это называется 2-й пустого слияния.
Процесс работы слияния выглядит следующим образом:
1. Подайте заявку на пространство, чтобы его размер была суммой двух отсортированных последовательностей, которая используется для хранения объединенных последовательностей
2. Установите два указателя, начальная позиция - начальная позиция двух сортированных последовательностей соответственно
3. Сравните элементы, указанные двумя указателями, выберите относительно небольшие элементы и поместите их в пространство слияния и перенесите указатель в следующую позицию
4. Повторите шаг 3, пока указатель не достигнет конца последовательности
5. Скопируйте все оставшиеся элементы другой последовательности непосредственно до конца последовательности слияния
Пример 1:
Кода -копия выглядит следующим образом:
/**
* Merge, также известный как алгоритм слияния, относится к операции объединения двух отсортированных последовательностей в одну последовательность.
* Алгоритм сортировки слияния зависит от операции слияния.
*
* Процесс работы слияния выглядит следующим образом:
*
* 1. Подайте заявку на пространство так, чтобы его размер была суммой двух отсортированных последовательностей, которая используется для хранения объединенных последовательностей
* 2. Установите два указателя, начальные позиции являются исходными позициями двух отсортированных последовательностей соответственно
* 3. Сравните элементы, указанные двумя указателями, выберите относительно небольшие элементы и поместите их в пространство слияния и переместите указатель в следующую позицию
* 4. Повторите шаг 3, пока указатель не достигнет конца последовательности
* 5. Скопируйте все оставшиеся элементы другой последовательности непосредственно до конца объединенной последовательности
*
*/
функция Mergesort (элементы) {
if (item.length <2) {
вернуть предметы;
}
var middle = math.floor (item.length / 2),
слева = item.slice (0, middle),
right = items.slice (середина),
params = merge (mergesort (слева), mergesort (справа));
params.unshift (0, item.length);
items.splice.apply (элементы, параметры);
вернуть предметы;
функция слияние (слева, справа) {
var result = [],
il = 0,
ir = 0;
while (il <left.length && ir <right.length) {
if (left [il] <right [ir]) {
result.push (слева [il ++]);
} еще {
result.push (справа [ir ++]);
}
}
return result.concat (left.slice (il)) .concat (right.slice (ir));
}
}
// тест
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
Mergesort (Arr);
Пример 2:
Кода -копия выглядит следующим образом:
<script type = "text/javascript">
//document.write("------------------------------------------------ ------------------------------------------------------ -------------------------------------);
// var array = новый массив (12, 25, 32, 16, 18, 27, 59, 69, 36);
var count = 0;
// Вызовите метод сортировки для сортировки
// MSORT (массив, массив, 0, array.length - 1);
// Массив источника источника
// Dest Target Array
// s Start Sptipcr
// TTARGET SPOPCRE
Функция MSORT (Source, Dest, S, T) {
var result = "";
var m;
var dest2 = new Array ();
if (s == t) {
dest [s] = источник [s];
}
еще {
m = math.floor ((s + t) / 2);
MSORT (Source, Dest2, S, M);
MSORT (Source, Dest2, M+1, T);
Merge (Dest2, Dest, S, M, T);
/* Результат вывода*/
Результат += "<Br /> Think" +++ count +"Результат упорядочения прохода:";
for (var n = 0; n <dest.length; n ++) {
Результат + = массив [n] + ",";
}
/* Результат вывода заканчивается*/
}
результат возврата;
}
/* Результат вывода заканчивается*/
// сплатили два массива по порядку от маленького до большого
// Источник оригинального массива
// dest отсортирован массив
// STHE First Script
// m Следующая таблица второго массива
// ntotal длина
слияние функции (Source, Dest, S, M, N) {
for (var j = m+1, k = s; j <= n && s <= m; k ++) {
if (source [s] <source [j]) {
dest [k] = источник [s ++];
}
еще {
dest [k] = источник [j ++];
}
}
// Добавить оставшиеся упорядоченные массивы в конце DEST
if (s <= m) {
for (var l = 0; l <= m - s; l ++) {
dest [k + l] = источник [s + l];
}
}
if (j <= n) {
for (var l = 0; l <= n - j; l ++) {
dest [k + l] = источник [j + l];
}
}
}
//document.write("<br /> <br /> ")
</script>