Блог

Главная - Вопросы по программированию - Правильная сортировка слиянием

Правильная сортировка слиянием

#javascript

#javascript

Вопрос:

Итак … если я введу:

4 1 5 3

ВМЕСТО 1,3,4,5

Я ПОЛУЧАЮ [ 4, 1, 5, 3]

Ниже приведен код для сортировки слиянием, но для последнего сравнения программа не извлекает обновленное (1,4) (3,5) значение, а (4,1) (5,3), что дает неверный результат.

  var a = [4, 1, 5, 3];
    q(a);
    function q(a) {
      var start = 0;
      var n = a.length;
      var length = parseInt(n / 2);
      if (n < 2) {
        return n;
      }
      var l = [], r = [];
      for (i = 0; i < length; i  ) {
        l[i] = a[i];  //left array
      }
      for (i = 0, j = length; j < n; i   , j  ) {
        r[i] = a[j];   //right array
      }
      q(l);           //merge sort left array
      q(r);           //merge sort right array
      comp(l, r);
    }
    
    function comp(l, r) {
      var k = [], m = 0, i = 0, j = 0;
      while (i < ((l.length)) amp;amp; j < ((r.length))) {
        if (l[i] < r[j]) {
          k[m] = l[i];
          i  ;
          m  
        }
        else {
          k[m] = r[j];
          j  ;
          m  
        }
      }
      while (i != (l.length)) {
        k[m] = l[i];
        m  ;
        i  ;
      }
      while (j != (r.length)) {
        k[m] = r[j];
        m  ;
        j  ;
      }
      console.log(k); //for final output it is [ 4, 1, 5, 3 ] instead of [1,3,4,5]

    }

Комментарии:

1. Я не понимаю, что вам нужно. Для сортировки массива? a.sort() — если имеется несколько массивов, затем объедините их, затем mergedArrays.sort()

2. да, я хочу отсортировать массив, но с помощью сортировки слиянием, реализацию которой я пытаюсь написать. @DarrenSweeney

3. Кстати, вы возвращаете что-либо из функции.

4. Можете ли вы привести лучший пример ТОГО, с чего именно вы начинаете и каким вы хотите получить конечный результат?

5. существует один массив, и я сортирую его с помощью сортировки слиянием, в которой используется повторная сортировка (сначала подмассив сортировки слева, затем подмассив сортировки справа, наконец, объединение) ввод 4, 1, 5, 3 вывод: 1,3,4,5

Ответ №1:

У вас есть пара небольших проблем. Основной из них заключается в том, что вы возвращаете неправильную вещь из своего граничного условия:

 if (n < 2) {
    return n; // n is just a length; doesn't make sense to return it.
}

n это длина, вы действительно хотите вернуть небольшой массив здесь:

   if (n < 2) {
    return a;  // return the array instead
  }

Кроме того, вам необходимо передать результат рекурсивного вызова вашей функции comp. Прямо сейчас вы просто возвращаете исходные списки с:

  comp(l, r)

Что-то подобное будет работать лучше:

   let l_sort = q(l);           //merge sort left array
  let r_sort = q(r);           //merge sort right array
  return comp(l_sort, r_sort); // merge the arrays when recursion unwinds.

И вам нужно return что-то для работы рекурсии.

Собрать все вместе:

 function q(a) {
  var start = 0;
  var n = a.length;
  var length = parseInt(n / 2);
  if (n < 2) {
    return a;
  }
  var l = [],
    r = [];
  for (i = 0; i < length; i  ) {
    l[i] = a[i]; //left array
  }
  for (i = 0, j = length; j < n; i  , j  ) {
    r[i] = a[j]; //right array
  }
  let l_sort = q(l); //merge sort left array
  let r_sort = q(r); //merge sort right array
  return comp(l_sort, r_sort);
}

function comp(l, r) {
  var k = [],
    m = 0,
    i = 0,
    j = 0;
  while (i < ((l.length)) amp;amp; j < ((r.length))) {
    if (l[i] < r[j]) {
      k[m] = l[i];
      i  ;
      m  
    } else {
      k[m] = r[j];
      j  ;
      m  
    }
  }
  while (i != (l.length)) {
    k[m] = l[i];
    m  ;
    i  ;
  }
  while (j != (r.length)) {
    k[m] = r[j];
    m  ;
    j  ;
  }
  return k
}

console.log(q([4, 1, 5, 3]).join(','));
console.log(q([5, 4, 3, 2, 1]).join(','));
console.log(q([2, 3]).join(','));
console.log(q([3, 2]).join(','));
console.log(q([1]).join(','));