插入排序 快速排序 归并排序

import java.util.Arrays;
import java.util.Random;

/**
 * Created by paul on 2020/1/5.
 */
public class Test {
    public static void main(String[] args) {
        for (int count = 0; count < 10000; count++) {
            int random = -1;
            if (count % 3 == 0) {
                random = 200;
            } else if (count % 3 == 1) {
                random = 201;
            } else {
                random = 202;
            }
            int[] original = randow(random);
            //int[] original = {10, 8, 4, 17, 10, 13, 11, 19, 16, 11, 7, 17, 7, 18, 1, 17, 2, 4, 9, 17};

            int[] a = Arrays.copyOf(original, original.length);
            quickSort1(a, 0, a.length - 1);
            int[] b = Arrays.copyOf(original, original.length);
            mergeSort(b, 0, b.length - 1);
            int[] c = Arrays.copyOf(original, original.length);
            insertSort(c, 0, c.length - 1);

            int[] d = Arrays.copyOf(original, original.length);
            insertSort(d, 0, d.length - 1);
            if (Arrays.equals(a, b) && Arrays.equals(b, c) && Arrays.equals(c, d)) {
            } else {
                System.out.println("==========================");
                System.out.println(Arrays.toString(original));
                System.out.println(Arrays.toString(a));
                System.out.println(Arrays.toString(b));
                System.out.println(Arrays.toString(c));
            }
        }
    }


    public static int[] randow(int num) {
        if (num < 1) {
            assert false;
        }
        Random random = new Random();
        random.nextInt(num);
        int[] result = new int[num];
        for (int i = 0; i < num; i++) {
            result[i] = random.nextInt(num);
        }
        return result;
    }

    public static void insertSort(int[] arr, int left, int right) {
        for (int i = left, j = i; i < right; j = ++i) {
            int ai1 = arr[i + 1];
            while (ai1 < arr[j]) {
                arr[j + 1] = arr[j];
                if (j-- == left) {
                    break;
                }
            }
            if (j != i) {
                arr[j + 1] = ai1;
            }
        }
    }

    public static void quickSort1(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int key = a[left];
        int i = left;
        int j = right;
        for (; i < j; ) {
            //注意顺序
            for (; a[j] > key && i < j; j--) ;
            for (; a[i] <= key && i < j; i++) ;
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        a[left] = a[i];
        a[i] = key;
        if (left < i - 1) quickSort1(a, left, i - 1);
        if (i + 1 < right) quickSort1(a, i + 1, right);
    }

    public static void quickSort2(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int key = a[left];
        int i = left;
        int j = right;
        for (; i < j; ) {
            for (; a[j] > key && i < j; j--) ;
            if (i < j) a[i] = a[j];

            for (; a[i] <= key && i < j; i++) ;
            if (i < j) a[j] = a[i];
        }
        a[i] = key;
        if (left < i - 1) quickSort2(a, left, i - 1);
        if (i + 1 < right) quickSort2(a, i + 1, right);

    }

    public static void mergeSort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int middle = (left + right) / 2;
        mergeSort(a, left, middle);
        mergeSort(a, middle + 1, right);

        arrSort2to1(a, left, middle, right);
    }

    public static void arrSort2to1(int a[], int left, int middle, int right) {
        if (left >= right) {
            return;
        }
        int[] temp = new int[right - left + 1];
        int tempLeft = left;
        int start = middle + 1;
        for (int i = 0; i < temp.length; i++) {
            if (left <= middle && start <= right) {
                if (a[left] <= a[start]) {
                    temp[i] = a[left++];
                } else {
                    temp[i] = a[start++];
                }
            } else if (left <= middle) {
                temp[i] = a[left++];
            } else {
                temp[i] = a[start++];
            }
        }

        //System.arraycopy(temp, 0, a, tempLeft, temp.length);
        for (int i = 0; i < temp.length; i++) {
            a[tempLeft + i] = temp[i];
        }

    }


    public static int[] arrSort2to1(int a[], int b[]) {
        int startA = 0;
        int startB = 0;

        int endA = a.length;
        int endB = b.length;
        int[] c = new int[endA + endB];
        int endC = c.length;
        for (int i = 0; i < endC; i++) {
            if (startA < endA && startB < endB) {
                if (a[startA] <= b[startB]) {
                    c[i] = a[startA++];
                } else {
                    c[i] = b[startB++];
                }
            } else if (startA < endA) {
                c[i] = a[startA++];
            } else {
                c[i] = b[startB++];
            }
        }
        return c;

    }
}