Java常见的排序算法

几种常见排序算法的时间复杂度

由此可见，在最好情况下，插入排序和冒泡排序最快，在平均情况下，快速排序最快，最坏情况下堆排序和归并排序最快。

稳定性比较

• 稳定性算法包括：插入排序，冒泡排序，归并排序；

• 非稳定性算法包括：堆排序，快速排序，简单选择排序；

---

main方法:

public static void main(String[] args) {
        int[] array = new int[] { 2, 4, 3, 6, 5, 8, 1 };
        // bubbleSort(array); // 调用冒泡排序算法
        // selectSort(array); // 调用选择排序算法
        // insertSort(array); // 调用插入排序算法
        // int[] mergeSort = mergeSort(array); // 调用归并排序算法
        quickSort(array, 0, array.length - 1);
        for (int n : array) {
            System.out.println(n);
        }
    }

冒泡排序:

/**
     * 冒泡排序，把大的元素向后移
     */
    public static void bubbleSort(int[] array) {
        if (array.length == 0)
            return;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

选择排序:

/**
     * 选择排序算法：每次都找到未排序的最小的数，将其调换到前面
     */
    public static void selectSort(int[] array) {
        if (array.length == 0)
            return;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            // 开始找最小值，保存其下标到minIndex中
            for (int j = i; j < array.length; j++) {
                if (array[minIndex] < array[j]) // 这样是从大到小
                    minIndex = j;
            }
            // 找完就开始交换
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }

插入排序:

/**
     * 插入排序：把一个数拿出来，和前一个数比较，如果小于前一个数，继续移动，直到找到大于数组中的数，插在那个数后面
     */
    public static void insertSort(int[] arr) {
        if (arr.length == 0)
            return;
        for (int i = 0; i < arr.length - 1; i++) {
            int current = arr[i + 1]; // 把这个数拿出来
            int preIndex = i; // 前一个数的下标
            // 如果当前数一直比前一个数小，将前一个数向右移动
            while (preIndex >= 0 && current < arr[preIndex]) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            // 找到比自己小的数，插入当前位置
            arr[preIndex + 1] = current;
        }
    }

归并排序:

/**
     * 归并排序：利用递归将数组分为多段进行排序
     */
    public static int[] mergeSort(int[] arr) {
        if (arr.length < 2)
            return arr;
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        int[] merge = merge(mergeSort(left), mergeSort(right));
        return merge;
    }

    /**
     * 将两个数组进行合并
     */
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)
                result[index] = right[j++]; // 左边已经遍历完了，右边的直接放进数组中
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }

        return result;
    }

快速排序:

/**
     * 快速排序算法实现
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left > right)
            return;
        int base = arr[left];
        int i = left, j = right;
        // 从右往左找，找比base小的数，找到就停止
        while (i < j) {
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 从左往右找，找到比base大的数，找到就停止
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 两个都找到了，交换两个位置
            if (i < j) {

                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

                // swap(arr, i, j);
            }
        }
        // 最后将base的位置和i的位置互换
        arr[left] = arr[j];
        arr[j] = base;
        // swap(arr, left, j);
        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        quickSort(arr, j + 1, right);
        quickSort(arr, left, j - 1);

    }