数组的排序算法

0. 辅助工具类

public class SortUtil {

    public static void swap(int[] array, int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }


    public static int[] initArray(int size) {
        int[] array = new int[size];

        for (int i = 0; i < size; i++) {
            array[i] = i + 1;
        }

        /**
         * 随机生成有 size 个元素的数组。
         * 其中无零，且无重复数值，以便于演示。
         */
        Random rand = new Random();

        /* 开始 Knuth 洗牌算法，基本流程是这样的：
         * 从最后一个数开始，往前遍历，每一次，从当前数和第 1 个数之间，随机选择一个数，与当前数字进行交换
         * 这里的随机选择就直接使用程序语言中的 Random 随机一个索引即可。
         */
        int last = array.length - 1;
        for (int i = last; i >= 0; --i) {
            // 从当0~当前索引位之间，选择一个数
            int selection = rand.nextInt(i + 1);

            // 索引位对应的数据交换
            swap(array, i, selection);
        }

        return array;
    }
}

1. 排序算法

public class SelectSort {

    public static void main(String[] args) {
        int[] array = Arrays.copyOf(initArray(40), 20); // 加大数据间隙

        System.out.println("before: " + Arrays.toString(array));

        sort(array);

        System.out.println(" after: " + Arrays.toString(array));
    }

    public static void sort(int[] array) {

        // i 的值是每一轮的【坑位】，
        for (int i = 0; i < array.length; i++) {

            // 用于记录本轮无序部分的最小值的下标索引。
            int minIdx = i;

            // j 的值是数组无序部分的第一个下标。
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIdx]) {
                    minIdx = j;
                }
            }

            // 将最小值【换】到它该待的【坑位】上。
            swap(array, i, minIdx);
        }
    }
}

public class InsertSort {

    public static void main(String[] args) {
        int[] array = initArray(20);
        //int[] array = new int[]{5, 4, 1, 3, 2};

        System.out.println("before: " + Arrays.toString(array));
        sort(array);
        System.out.println(" after: " + Arrays.toString(array));

    }

    public static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {

            int j = i;
            int temp = array[j];
            while (j > 0 && array[j - 1] > temp) {
                array[j] = array[j - 1];
                j--;
            }

            array[j] = temp;
        }
    }
}

public class MergeSort {

    public static void main(String[] args) {
        int array[] = SortUtil.initArray(20);

        //int[] array = new int[]{7, 3};
        System.out.println("before: " + Arrays.toString(array));
        sort(array);
        System.out.println(" after: " + Arrays.toString(array));
    }

    public static void sort(int[] array) {

        tempArray = new int[array.length];

        sort(array, 0, array.length - 1);
    }

    public static void sort(int[] array, int left, int right) {
        if (left >= right)
            return;

        int mid = left + (right - left) / 2;
        sort(array, left, mid);
        sort(array, mid + 1, right);
        merge(array, left, mid, right);
    }

    private static int[] tempArray; // 辅助数组

    /**
     * 数组 array 的左右半区分别有序：array[left, mid] 和 array[mid+1, right]
     * 现在要将这两个半区合并，使他们全区有序：array[left, right]
     */
    public static void merge(int[] array, int left, int mid, int right) {

        int i = left, j = mid + 1;


        for (int k = left; k <= right; k++) {
            tempArray[k] = array[k];
        }

        for (int k = left; k <= right; k++) {
            if (i > mid)                            array[k] = tempArray[j++];
            else if (j > right)                     array[k] = tempArray[i++];
            else if (tempArray[i] < tempArray[j])   array[k] = tempArray[i++];
            else                                    array[k] = tempArray[j++];
        }
    }
}

public class QuickSort {

    public static void main(String[] args) {
        int array[] = SortUtil.initArray(20);

        //int[] array = new int[]{7, 3};
        System.out.println("before: " + Arrays.toString(array));
        sort(array);
        System.out.println(" after: " + Arrays.toString(array));
    }

    public static void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    private static void sort(int[] array, int left, int right) {
        if (left >= right)
            return;

        int j = partition(array, left, right);
        sort(array, left, j - 1);
        sort(array, j + 1, right);
    }

    /**
     * 将数组切分成：array[left...i-1], array[i], array[i+1, right]
     */
    private static int partition(int[] array, int left, int right) {
        int i = left, j = right + 1;

        int pivot = array[left];

        while (true) {
            while (array[++i] < pivot) {    // 从左往右第一个 >= pivot 的数字
                if (i == right)
                    break;
            }

            while (pivot < array[--j]) {    // 从右往左第一个 <= pivot 的数字
                if (j == left)
                    break;
            }

            if (i >= j)
                break;

            SortUtil.swap(array, i, j);
        }

        SortUtil.swap(array, left, j);  // pivot == array[j] 交换位置

        return j;
    }
}