Поиск по алгоритму Mergesort с использованием стандартного Java LinkedList

Question

Я хочу отсортировать LinkedList в Java, используя алгоритм Mergesort.
Я искал в Интернете решение, но алгоритмы, которые я нашел, сортируют либо по массиву, либо по самопровозглашенному LinkedList. Как я упоминал ранее, мне нужен алгоритм, который сортирует стандартный java LinkedList (java.util.LinkedList).
В дополнение к своим исследованиям я пытался реализовать их самостоятельно, но я не способен на это. Мне удалось создать часть «деления», но я не смог запрограммировать часть «завоевать» (объединить в отсортированном порядке).
Это мой код:

private void mergeSort(LinkedList<Integer> list) {
        if (list.size() < 2){
            return;
        }
        int middleindex  = list.size()/2;
        LinkedList<Integer> [] listArr = split(list, middleindex);

        LinkedList<Integer> leftList = listArr[0];
        mergeSort(leftList);

        LinkedList<Integer> rightList = listArr[1];
        mergeSort(rightList);

        sortedMerge(rightList, leftList, list);

    }

    private void sortedMerge(LinkedList<E> right, LinkedList<E> left, LinkedList<E> list){
        //sort and merge
    }


    @SuppressWarnings("unchecked") private static <T> LinkedList<T>[] split(LinkedList<T> list, int index) {
        LinkedList<T> left = new LinkedList<>();

        for (int i = 0; i < index; i++) {
            T t = list.removeFirst();
            left.addLast(t);
        }
        return new LinkedList[] {
                left, list
        };
    }

Может ли кто-нибудь помочь мне и создать метод sortedMerge ()?

Answer 1

Пример кода (включая тестовый код в main ()) для сортировки слиянием снизу вверх для Java LinkedList, который использует небольшой массив (32) списков (в отличие от подхода разбиения и переноса списков в стек сверху вниз)).Поскольку Java LinkedList не имеет C ++ эквивалента std :: list :: splice (), который перемещает узлы в списке (или из списка в список), узлы и списки создаются и удаляются, что добавляет значительное количествонакладные расходы.

package llsort;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Random;

public class llsort {

    public static LinkedList<Integer> Merge(LinkedList<Integer> ll0, LinkedList<Integer> ll1){
        LinkedList<Integer> ll = new LinkedList<>();
        if(ll0.isEmpty())               // empty list check
            return (ll1);
        if(ll1.isEmpty())
            return (ll0);
        ListIterator <Integer> ll0i = ll0.listIterator(0);
        ListIterator <Integer> ll1i = ll1.listIterator(0);
        Integer e0;
        Integer e1;
        e0 = ll0i.next();               // merge lists
        e1 = ll1i.next();
        while(true){
            if(e0 <= e1){
                ll.add(e0);
                if(ll0i.hasNext()){
                    e0 = ll0i.next();
                    continue;
                }
                ll.add(e1);
                while(ll1i.hasNext())
                    ll.add(ll1i.next());
                break;
            }else{
                ll.add(e1);
                if(ll1i.hasNext()){
                    e1 = ll1i.next();
                    continue;
                }
                ll.add(e0);
                while(ll0i.hasNext())
                    ll.add(ll0i.next());
                break;
            }
        }
        return ll;
    }

    public static LinkedList<Integer> MergeSort(LinkedList<Integer> src){
        final int NUMLIST = 32; 
        LinkedList<Integer>[] all = new LinkedList[NUMLIST];
        LinkedList<Integer> ll;
        int i;
        // merge nodes into array
        ll = new LinkedList();
        while(!src.isEmpty()){
            ll.add(src.peek());
            src.remove();
            for(i = 0; i < NUMLIST && all[i]!= null; i++){
                ll = Merge(ll, all[i]);
                all[i] = null;
            }
            if(i == NUMLIST)
                i--;
            all[i] = ll;
            ll = new LinkedList();
        }
        // merge array into list
        ll = new LinkedList();
        for(i = 0; i < NUMLIST; i++)
            if(all[i] != null)   
                ll = Merge(ll, all[i]);
        return ll;        
    }

    public static void main(String[] args) {
        final int NUMELEM = 2*1024*1024; 
        LinkedList<Integer> ll = new LinkedList<>();
        Random r = new Random();
        for(int i = 0; i < NUMELEM; i++)
            ll.addLast(r.nextInt());
        long bgn, end;
        bgn = System.currentTimeMillis();
        ll = MergeSort(ll);
        end = System.currentTimeMillis();
        System.out.println("milliseconds " + (end-bgn));
        // check sort
        while(true){
            int i = ll.peek();
            ll.remove();
            if(ll.isEmpty())
                break;
            if(i > ll.peek()){
                System.out.println("error");
                break;
            }
        }
    }
}

Answer 2

Метод Collections.sort () сортирует LinkedList. Это делается путем копирования содержимого LinkedList в массив, сортировки массива и копирования содержимого массива обратно в LinkedList. Вы можете реализовать те же функции, что и метод Collections.sort (), и использовать алгоритм сортировки слиянием для сортировки массива.

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

Шаги:

1. Создать LinkedList 'orginialList'
2. Преобразование 'originalList' в массив Integer 'arr'
3. Преобразование 'arr' в массив int 'intArray'
4. Сортировка intArray с использованием алгоритма сортировки слиянием
5. Преобразовать отсортированный intArray обратно в массив Integer 'arr' (используйте для изменения цикла элементы в 'arr')
6. Создать LinkedList 'newList'
7. Добавить элементы 'arr' в 'newList' (используйте Arrays.asList (arr))

     public static class CollectionsSort {
         public static void main(String[] args) {
               LinkedList<Integer> originalList = new LinkedList<>();
               originalList.add(3);
               originalList.add(2);
               originalList.add(1);

               Integer[] arr = list.toArray(new Integer[list.size()]);
               int[] intArray = new int[arr.length];
               for (int i = 0; i < intArray.length; i++) {
                   intArray[i] = arr[i].intValue();
               }
               mergesort(intArray);
               for (int i = 0; i < arr.length; i++) {
                   arr[i] = new Integer(intArray[i]); 
               }
               LinkedList<Integer> newList = new LinkedList(Arrays.asList(arr));
               Iterator it = newList.iterator();
               while(it.hasNext()) {
                  System.out.print((int)(it.next()) + " ");
               }
         }

         public static int[] mergesort(int[] arr) {
               int low = 0;
               int high = arr.length-1;
               mergesort(arr, low, high);
               return arr;
         }

         public static void mergesort(int[] arr, int low, int high) {
               if (low == high) {
                   return;
               } else {
                   int middle = low + (high-low)/2;
                   mergesort(arr, low, middle);
                   mergesort(arr, middle+1, high);
                   merge(arr, low, middle, high);
               }
         }

         public static void merge(int[] arr, int low, int mid, int high) {
               int[] left = new int[mid-low+2];
               for (int i = low; i <= mid; i++) {
                   left[i-low] = arr[i];
               }
               left[mid-low+1] = Integer.MAX_VALUE;
               int[] right = new int[high-mid+1];
               for(int i = mid+1; i <= high; i++) {
                   right[i-mid-1] = arr[i];
               }
               right[high-mid] = Integer.MAX_VALUE;
               int i = 0, j = 0;
               for(int k = low; k <= high; k++) {
                   if(left[i] <= right[j]) {
                      arr[k] = left[i];
                      i++;
                   } else {
                      arr[k] = right[j];
                      j++;
                   }
               }
         }
     }