Сортировка слиянием с использованием слияния на месте - PullRequest
Новая
       14

Сортировка слиянием с использованием слияния на месте

1 голос
/ 21 августа 2010

A [] -> 1 3 5 7 2 4 6 8 //

lb = 0, mid-1 = 3, mid + 1 = 4, ub = 7;

a = 3, b = 7, ab = 7;

1-я итерация

a = 3, b = 6, ab = 6;

2-я итерация

swap (A [ab], A [a]) // int t;t я буду использовать для временного хранения

1 3 5 6 2 4 7 8

b = 5, ab = 5;сортировки (A, фунт, середина 1);// с использованием пузырьковой сортировки

3-я итерация

swap (A [ab], A [a])

1 3 5 4 2 6 7 8

b = 5, ab = 4

sort (A, lb, mid-1) // использование пузырьковой сортировки

Это правильный подход для сортировки слиянием с использованием inplaceсращивание.Это моя первая попытка слияния на месте. Если это неправильный подход, кто-то может мне предложить.

1 Ответ

0 голосов
/ 06 марта 2013

Не уверен, что у вас есть алгоритм Mergesort.

При использовании Mergesort на первом этапе вам нужно разбить ваш массив на подмассивы. 

A = [1, 3, 5, 7, 2, 4, 6, 8]

A1 = [1, 3, 5, 7], A2 = [2, 4, 6, 8]

A11 = [1,3], A12 = [5,7], A21 = [2,4], A22 = [6,8]
... // till you have an arrays looks like this:
A1 = [1], A2 = [3], A3 = [5], A4 = [7], A5 = [2], A6 = [4], A7 = [6], A8 = [8]

Затем вы объединяетесь в обратном порядке и сравниваете толькопервые элементы в обоих массивах (поместите самый низкий элемент в новый массив). 

[1,3], [5,7], [2,4], [6,8]
  [1,3,5,7],   [2,4,6,8]
     [1,2,3,4,5,6,7,8]
...