Алгоритм сортировки слиянием Java ArrayList - PullRequest
Новая
       12

Алгоритм сортировки слиянием Java ArrayList

0 голосов
/ 02 марта 2012

У меня проблемы с алгоритмом сортировки слиянием в Java.Кажется, сейчас происходит много странных вещей, и мне трудно заставить его работать.Я полагаю, что проблема может быть где-то в функции mergeArrayLists, но я не уверен.Любая помощь будет оценена! 

public class MergeSort extends Sort {

   public MergeSort() {
   }

   // Inherited from Sort
   public <T extends Comparable<T>> void sortArrayList(ArrayList<T> arrayList) {
      arrayList = mergeSort(arrayList);
   }

   // Returns the sorted form of the given array list (sorted via the merge sort algorithm)
   public <T extends Comparable<T>> ArrayList<T> mergeSort(
         ArrayList<T> arrayList) {
      if (arrayList.size() <= 1) {
         return arrayList;
      } else {
         ArrayList<T> firstList = new ArrayList<T>();
         ArrayList<T> secondList = new ArrayList<T>();

         for (int i = 0; i < arrayList.size(); i++) {
            T thisValue = arrayList.get(i);
            if (i < arrayList.size() / 2) {
               firstList.add(thisValue);
            } else {
               secondList.add(thisValue);
            }
         }
         //System.out.println(firstList+" "+mergeSort(firstList));
         ArrayList<T> firstSort = mergeSort(firstList);
         ArrayList<T> secondSort = mergeSort(secondList);
         return mergeArrayLists(firstSort, secondSort);
      }
   }

   // Merges two array lists together, in order
   public <T extends Comparable<T>> ArrayList<T> mergeArrayLists(
         ArrayList<T> firstList, ArrayList<T> secondList) {
      ArrayList<T> resultList = new ArrayList<T>();

      int firstIndex, secondIndex = 0;
      for (firstIndex = 0; firstIndex < firstList.size() - 1; firstIndex++) {
         while (secondIndex < secondList.size() - 1) {
            if (firstList.get(firstIndex)
                  .compareTo(secondList.get(secondIndex)) < 0) {
               break;
            } else {
               resultList.set(firstIndex + secondIndex,
                     secondList.get(secondIndex));
               secondIndex++;
            }
         }
         resultList.set(firstIndex + secondIndex, firstList.get(firstIndex));
      }
      System.out.println(firstList + " + " + secondList + " = " + resultList);

      return resultList;
   }
}

1 Ответ

0 голосов
/ 02 марта 2012

У вас отключена одна ошибка.

for(firstIndex=0; firstIndex<firstList.size(); firstIndex++) {
    while(secondIndex < secondList.size()) {
        if(firstList.get(firstIndex).compareTo( secondList.get(secondIndex) ) < 0) {
            break;
        }
        else {
            resultList.set(firstIndex + secondIndex, secondList.get(secondIndex));
            secondIndex++;
        }
    }
    resultList.set(firstIndex + secondIndex, firstList.get(firstIndex));
}

Ваши списки должны быть индексированы <размер, а не размер -1 </p>

...