java - 使用Java标准LinkedList搜索Mergesort算法

Question

我想使用合并排序算法对 Java 中的 LinkedList 进行排序。
我在互联网上研究了一个解决方案，但我发现的算法对数组或自声明的 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

Collections.sort() 方法对 LinkedList 进行排序。它通过将 LinkedList 的内容复制到数组，对数组进行排序，然后将数组的内容复制回 LinkedList 来实现这一点。您可以实现与 Collections.sort() 方法相同的功能，并使用合并排序算法对数组进行排序。

下面我详细介绍了使用合并排序算法对 Java 标准 LinkedList 进行排序的步骤和正确代码。

步骤:

1. 创建一个 LinkedList 'orginialList'
2. 将“originalList”转换为整数数组“arr”
3. 将 'arr' 转换为 int 数组 'intArray'
4. 使用合并排序算法对“intArray”进行排序
5. 将排序后的“intArray”转换回整数数组“arr”(使用 for 循环更改'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++;
                   }
               }
         }
     }