常见排序算法

冒泡排序

 /**
     * 冒泡排序：相邻元素两两比较，左边小右边大。每轮遍历找出最小的元素
     * 时间复杂度: O(N^2)
     * 空间复杂度: O(1)
     * 稳定性：稳定
     */
    public void bubbleSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        elementPrint("排序前", array);
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        elementPrint("排序后", array);
    }

    private void elementPrint(String msg, int[] array) {
        StringBuilder sb = new StringBuilder();
        for (int i : array) {
            sb.append(i);
        }
        String result = sb.toString();
        System.out.println("==TAG==>" + msg + "  --  " + result);
    }

选择排序

    /**
     * 选择排序
     *
     * @param array 传入的数组
     *              <p>
     *              每轮循环的目标是寻找最小的元素索引下标
     */
    public void selectSort(int[] array) {
        if (array == null) return;
        elementPrint("排序前", array);
        for (int i = 0; i < array.length; i++) {
            // 假定当前的最小
            int minIndex = i;

            for (int j = i; j < array.length - 1; j++) {
                if (array[j] > array[j + 1]) {
                    minIndex = j + 1;
                }
            }

            // 交换元素
            int tem = array[minIndex];
            array[minIndex] = array[i];
            array[i] = tem;
        }
        elementPrint("排序后", array);
    }

插入排序

    /**
     * 选择排序
     *
     * @param array 传入的数组
     *              <p>
     *              每轮循环的目标是寻找最小的元素索引下标
     */
    public void selectSort(int[] array) {
        if (array == null) return;
        elementPrint("排序前", array);
        for (int i = 0; i < array.length; i++) {
            // 假定当前的最小
            int minIndex = i;

            for (int j = i; j < array.length - 1; j++) {
                if (array[j] > array[j + 1]) {
                    minIndex = j + 1;
                }
            }

            // 交换元素
            int tem = array[minIndex];
            array[minIndex] = array[i];
            array[i] = tem;
        }
        elementPrint("排序后", array);
    }

快速排序

    /**
     * 快速排序：选定基准元素，记录当前的索引下标，从右往左找比基准元素小的，找到后放置左边；从左往右找比基准元素大的，找到后放置在右边
     *
     * @param array 数组
     * @param l     left
     * @param r     right
     */
    public void testQuick(int[] array, int l, int r) {
        if (l < r) {
            int leftIndex, rightIndex, x;
            // 左边界下标
            leftIndex = l;
            // 右边界下标
            rightIndex = r;
            // 基准元素
            x = array[leftIndex];
            while (leftIndex < rightIndex) {
                // 从右边往左边找小于基准元素的值
                while (leftIndex < rightIndex && array[rightIndex] > x) {
                    // 继续找
                    rightIndex--;
                }
                // 找到了
                if (leftIndex < rightIndex) {
                    int index = leftIndex++;
                    array[index] = array[rightIndex];
                }
                // 从左边往右边找大于基准元素的值
                while (leftIndex < rightIndex && array[leftIndex] < x) {
                    // 继续找
                    leftIndex++;
                }
                // 找到了
                if (leftIndex < rightIndex) {
                    int index = rightIndex--;
                    array[index] = array[leftIndex];
                }
            }
            array[leftIndex] = x;
            // 递归调用
            testQuick(array, l, leftIndex - 1);
            testQuick(array, leftIndex + 1, r);
        }
    }