手写一个ArrayList排序算法

手写一个ArrayList排序算法

Method类

package com.inspire.util;

import java.util.ArrayList;
import java.util.List;

public class Method {
    private List<Integer> list=new ArrayList<Integer>();//保存函数的行信息

    public List<Integer> getList() {
        return list;
    }

}

List排序类

package com.inspire;

import com.inspire.util.Method;

import java.util.Arrays;
import java.util.List;

public class test15 {
    public static void main(String[] args) {
        Method method = new Method();
        int[] testEffiArr = generateRandomArray(100, 100);
        for (int num : testEffiArr) {
            method.getList().add(num);
        }
        listSort(method.getList());
        Arrays.sort(testEffiArr);
        boolean succeed = true;
        for (int i = 0; i < testEffiArr.length; i++) {
            if (method.getList().get(i) != testEffiArr[i]) {
                succeed = false;
            }
        }
        System.out.println(succeed == true ? "Nice!" : "Oh No!");
        System.out.println("list Sort After : " + method.getList());
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static void listSort(List<Integer> methodLineList) {
        int[] methodLineArr = new int[methodLineList.size()];
        for (int i = 0; i < methodLineList.size(); i++) {
            methodLineArr[i] = methodLineList.get(i);
        }
        stableSort(methodLineArr);
        methodLineList.clear();//clear是清空当前集合元素内容
        for (int i = 0; i < methodLineArr.length; i++) {
            methodLineList.add(methodLineArr[i]);
        }
    }

    //非递归方法实现归并排序（稳定性最好的排序算法）
    public static void stableSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        int mergeSize = 1;
        while (mergeSize < N) {
            int L = 0;
            while (L < N) {
                int M = L + mergeSize - 1;
                if (M >= N) {
                    break;
                }
                int R = Math.min(M + mergeSize, N - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            if (mergeSize > N / 2) {
                break;
            }
            mergeSize <<= 1;
        }
    }

    private static void merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= R) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
    }
}