Блог

Я работаю над методом сортировки слиянием, который сортирует элементы на месте без выделения дополнительной памяти. Однако на данный момент это не работает, и мне было интересно, может ли кто-нибудь мне помочь, поскольку я понимаю, что это относительно простая операция. Заранее благодарю вас.

Мой метод сортировки слиянием:

       RegisterClass[] runMergeSort()
  {
     RegisterClass[] mergeSorted = new RegisterClass[capacity];
     
     for (int counter = 0; counter < size; counter  )
        {
           mergeSorted[counter] = registerArray[counter];
        }
     
     runMergeSortHelper(mergeSorted, 0, size - 1);
     
     return mergeSorted;
  }
  

Мой вспомогательный метод, который использует рекурсию:

       private void runMergeSortHelper(RegisterClass[] workingArray,
                                  int lowIndex,
                                  int highIndex)
  {
     int midIndex = (lowIndex   highIndex) / 2;
     
     if (lowIndex < highIndex)
        {
           
           runMergeSortHelper(workingArray, lowIndex, midIndex);
           runMergeSortHelper(workingArray, midIndex 1, highIndex);
                          
           runMerge(workingArray, lowIndex, midIndex, highIndex);
        }
              

  }
  

И, наконец, мой метод слияния, который ДОЛЖЕН приводить все в порядок, однако, он делает это только частично.

       private void runMerge(RegisterClass[] workingArray,
                        int lowIndex,
                        int midIndex,
                        int highIndex)
  {
     int counterJay = midIndex;
     int counterAye = lowIndex;
     int counterKay = lowIndex - 1;
              
     while (counterAye < midIndex amp;amp; counterJay <= highIndex)
        {
           counterKay  ;
           
           if (workingArray[counterAye].compareTo(workingArray[counterJay]) <= -1)
              {
                 counterAye  ;
              }
           
           else
              {
                 swapValues(workingArray, counterAye, counterJay);
                 counterJay  ;
                 counterAye  ;
              }
           
        }
     
     while (counterAye < midIndex)
        {
           counterKay  ;
           swapValues(workingArray, counterAye, counterKay);
           counterAye  ;
        }
     
     while (counterJay <= highIndex)
        {
           counterKay  ;
           swapValues(workingArray, counterJay, counterKay);
           counterJay  ;
        }
  }
  

Любой совет вообще был бы высоко оценен. Я посмотрел онлайн, но, похоже, ничего не помогает. Пожалуйста, не отсылайте меня к решению, которое НЕ является решением на месте.

Замена не будет работать с логикой, используемой функцией слияния. Когда происходит замена, элемент, который заменяется с левой стороны на правую, теперь выходит из строя и будет меньше (или равен) всем оставшимся элементам с левой стороны.

Всякий раз, когда обнаруживается, что элемент с правой стороны меньше элемента с левой стороны, требуется поворот вправо этой части массива, чтобы поместить элемент с правой стороны на место.

Не прибегая к более сложной реализации, можно выполнить небольшую оптимизацию, просканировав правую сторону на наличие k = количество начальных элементов, меньших, чем текущий элемент с левой стороны, затем выполните поворот вправо на k элементов. Для случайных данных это не сильно поможет, но для данных с обратной сортировкой это помогло бы совсем немного.