Подсказка. Дан массив целых чисел, отсортируйте этот массив, не используя встроенный метод сортировки.
Ввод:[1,5,0,6,3]
Вывод:[0,1,3,5,6]
Первые мысли:
- Массивы из 1 или менее элементов уже отсортированы. Возможно, рекурсивно разделить входной массив на более мелкие массивы.
- Сравните массивы из 1 элемента, чтобы увидеть, какой из них больше, а затем объедините
- Продолжайте сравнивать, пока не объединитесь обратно в один массив.
Логика:
- Реализуйте вспомогательную функцию, которая объединяет два массива.
- Алгоритм mergeSort вызовет помощника после того, как он разделит массивы на сортировку по 1 элементу.
- Входные массивы в уже должны быть отсортированы.
Псевдокод для объединения помощников
- Создайте пустой массив для хранения наименьших значений в каждом входном массиве.
- в то время как есть еще ценности, на которые мы не смотрели…
- Если значение в первом массиве меньше, чем во втором, вставьте его в результат и перейдите к следующему значению в первом массиве.
- Если значение в первом массиве больше, чем во втором, вставьте второе в результат и перейдите к следующему значению во втором массиве.
- Как только мы исчерпаем один массив, поместим все остальные значения в массив результатов.
Вспомогательная функция слияния
функция слияния (arr1, arr2) {
пусть результат = []
пусть я = 0
пусть j = 0
в то время как (i‹ arr1.length && j‹arr2.length){
если (приб1[i] ‹ приб2[j]){
результат.push(arr1[i])
i++
}
еще{
результат.push(arr2[j]);
j++
}
}
в то время как (i‹ arr1.length) {
результат.push(arr1[i])
)i++
}
в то время как (j‹ обр2.длина) {
результат.push(arr2[j])
j++
}
вернуть результат
}
объединить([1,10,50], [2,14,99,100]
Псевдокод слияния
- Рекурсивно разрезать массивы пополам до длины 1
- базовый случай, когда длина меньше или равна единице
Комбинированная сортировка слиянием
функция mergeSort(arr){
if(arr.length ‹= 1) return arr;
пусть середина = Math.floor (arr.length / 2)
пусть осталось = mergeSort (arr.slice (0, середина))
пусть вправо = mergeSort (arr.slice (середина))
вернуть слияние (слева, справа)
}
Сортировка слиянием ([1,5,0,6,3])
Большое О
Временная сложность и пространственная сложность равны O(nlogn), функция слияния — log(n), а остальная часть mergeSort, за исключением помощника слияния, — O(n). Пространство может быть в лучшем случае O (n)
