算法之排序

概述

记录排序算法。

1 选择排序

**
     * 选择排序
     * 思路：遍历数组，找出（选择）最小的元素，然后和最左边的元素交换。接下来，再从第二个元素开始遍历整个数组。再找到最小的元素，再和第二个元素交换。
     * 重复该过程，直至遍历完成。
     * 时间复杂度：n^2
     * 空间复杂度：1（原地排序，除了临时变量不需要额外空间）
     * @param arr 数组
     * @return 排好序的数组
     */
    public static int[] selectSort(int[] arr){
        // 边界条件
        if(arr.length < 1){
            return arr;
        }

        // 0 - n
        // 1 - n
        // ...
        // i - n
        for(int i = 0; i < arr.length; i++){
            int minIndex = i;
            // 在i-n范围内找最小的
            for(int j = i+1; j < arr.length; j++){
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            swap(i, minIndex, arr);
        }

        return arr;
    }

    /**
     * 索引i和j位置的元素交换
     * @param i 索引
     * @param j 索引
     * @param arr 数组
     */
    public static void swap(int i, int j, int[] arr){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

2 冒泡排序

/**
     * 2冒泡排序
     * 关键词：两两比较
     * 思路：
     * 第一次遍历，从0到n-1遍历数组。两两比较，大的元素往后排，最后遍历结束时，最大的元素就排在了数组末尾。
     * 第二次遍历，从0到n-2遍历数组。两两比较，大的元素往后排，最后遍历结束时，0到n-2中最大的元素就排在了数组n-1的位置处。
     * ...
     * 时间复杂度：n^2
     * 空间复杂度：1
     * 注意：因为是j+1，为防止越界，添加条件1：j <= i-1；又因为是i-1，添加条件2：i > 0；
     * @param arr 数组
     * @return 排好序的数组
     */
    public static int[] bubbleSort(int[] arr){
        // 边界条件
        if(arr.length < 2){
            return arr;
        }

        for(int i = arr.length - 1; i > 0; i--){
            // 从0到i遍历，两两比较
            for(int j = 0; j <= i-1; j++){
                if(arr[j] > arr[j+1]){
                    swap(j, j+1, arr);
                }
            }
        }

        return arr;
    }

3 插入排序

/**
     * 插入排序
     * 理解：打牌，在发牌时，先整理好手上的牌。拿到新发的牌后，往手上已经整理好的牌中插入。
     * 思路：
     * 从0到0，自己和自己比，不用排序
     * 从0到1，小的往前排，直至排到第一个位置
     * 从0到2，小的往前排，直至拍到第一个位置或者前面的更小
     * @param arr 数组
     * @return 有序数组
     */
    public static int[] insertSort(int[] arr){
        if(arr == null || arr.length < 2){
            return arr;
        }

        for(int i = 0; i < arr.length; i++){
            for(int j = i; j >= 0; j--){
                if(j-1 < 0){
                    continue;
                }
                if(arr[j-1] > arr[j]){
                    swap(j, j-1, arr);
                }
            }
        }

        return arr;
    }