1、排序算法汇总-选择、冒泡、插入

发布于 2022年 02月 13日 08:00

1、选择排序

时间的复杂度:O(N²)

  1. 在数组中找出最小的元素,和数组的首位进行交换
  2. 从剩余的元素中找出最小的元素,放到已排序元素的后面
  3. 依次循环第二步


 
    /**
     * @Author Sam
     * @Description 选择排序  按照从小到大的方式进行排序
     * @Date 2020/12/25
     **/
    public static void selectionSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        //1、拿到数组角标为0的数据,依次跟后面的数据比较  0-----N-1
        //2、找出最小的值,放到数组的起始位置,
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            //假设数组角标为0的第一个数据为最小值
            int minIndex = i;
            //根据拿到的值,依次向后比较,找出后面元素最小的角标
            for (int j = i + 1; j < length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            //经过第二个for循环,minIndex是整个数组中最小元素的角标,所以将最小的元素和前面的元素替换一下
            swap(array, i, minIndex);
        }
    }

    /**
     * @Description 数组内两个元素的交换
     * @Date 2020/12/25
     * @Param array  数据
     * @Param i   角标
     * @Param j   角标
     **/
    public static void swap(int[] array, int i, int j) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


2、冒泡排序

时间的复杂度:O(N²)

  1. 比较相邻的两个的元素的大小,如果左边的比右边的大,那么交换,这样比较一次下来,最右边的为最大值

2、循环一次往复


 
     /**
     * @Author Sam
     * @Description 冒泡排序  从小到大
     * @Date 2020/12/25
     **/
    public static void bubblingSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int length = array.length;
        //外层循环控制整个数组的比较的位置
        for (int i = length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
    }

    /**
     * @Description 数组内两个元素的交换
     * @Date 2020/12/25
     * @Param array  数据
     * @Param i   角标
     * @Param j   角标
     **/
    public static void swap(int[] array, int i, int j) {

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


3、插入排序

时间的复杂度:O(N²)

  1. 遍历元素,每个元素都比较它左边的元素,如果比左边的元素小,那么就位置交换
  2. 位置交换后的元素,如果左边有元素,那么继续比较,如果比左边的元素小,那么就位置交换
  3. 循环往复



    /**
     * @Author Sam
     * @Description 插入排序,从小到大
     * @Date 2020/12/28
     **/
    public static void insertSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        for (int i = 1; i < array.length; i++) {
            //如果左边的比右边的元素大,那么位置交换。
            for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
                swap(array, j, j + 1);
            }


        }


    }

    /**
     * @Description 数组内两个元素的交换
     * @Date 2020/12/25
     * @Param array  数据
     * @Param i   角标
     * @Param j   角标
     **/
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

推荐文章