11、数据结构与算法 - 实战:冒泡排序、选择排序、插入排序

前言

一、冒泡排序

1.1 基本介绍

冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始), 依次比较相邻元素的值,若发现逆序则交换 ,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。

因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序 ,因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化,可以在冒泡排序写好后,在进行)

1.2 演示冒泡过程的例子(图解)

小节下面的冒泡排序的图解过程:

1、 一共进行**【数组的大小-1】大的循环**;
2、 每一趟排序的次数在逐渐的减少
3、 如果我们发现在某趟排序中,没有发生一次交换,可以提前结束冒泡排序这个就是优化
 

1.3 代码实现

  • 时间复杂度:O(n^2)
  • 实现对一位数组{3, 9, -1, 10, -2}的排序
  • 代码实现是分为三部分学习的

1、 对每一步的循环进行分析、推导,其方法为deductionBubbleSort(int[]array)
2、 对第一步的推导找出规律,合成两个for循环其方法为bubbleSort(int[]array)
3、 测试80000个数据排序所需要的时间其方法为testTime()方法,26S左右;

package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 冒泡排序
 * 时间复杂度为 O(n^2)
 * 分为三步:
 * 1、每一步进行推导。 deductionBubbleSort(int[] array)方法
 * 2、找到规律,合成两个for循环。 bubbleSort(int[] array)方法,并进行优化:比较后没有交换的不进行循环一趟
 * 3、测试 80000 个数据排序所需要的时间。 testTime()方法         26S 左右
 * */
public class S1_BubbleSort {
   
     
    public static void main(String[] args) {
   
     
        int[] array = {
   
     3, 9, -1, 10, -2};

        System.out.println("排序前:");
        System.out.println(Arrays.toString(array));

        System.out.println();
        System.out.println("排序后:");
//        deductionBubbleSort(array);  // 推导的方法。
        int[] ints = bubbleSort(array); // 推导后的方法
        System.out.println(Arrays.toString(ints));

        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用冒泡排序 所用的时间:");
        testTime();
    }

    /*
     * 测试一下 冒泡排序的速度O(n^2), 给 80000 个数据,测试一下
     * */
    public static void testTime() {
   
     
        // 创建一个 80000个的随机的数组
        int array2[] = new int[80000];
        for (int i = 0; i < 80000; i++) {
   
     
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印,耗费时间太长
        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要,但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        bubbleSort(array2);

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要,但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为:" + ((end - start) / 1000) + "秒");
    }

    /*
     * 推导后,合成的方法【重点掌握】
     * */
    public static int[] bubbleSort(int[] array) {
   
     
        int temporary = 0; // 临时变量
        boolean flag = false;
        for (int i = 0; i < array.length - 1; i++) {
   
      // 总共为 4 趟 大遍历。
            for (int j = 0; j < array.length - 1 - i; j++) {
   
     
                // 如果前面的数比后面的数大,则交换
                if (array[j] > array[j + 1]) {
   
     
                    flag = true;
                    temporary = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temporary;
                }
            }
//            System.out.println("第" + (i + 1) + "躺排序后的数组");
//            System.out.println(Arrays.toString(array));
            if (!flag) {
   
      // 在一趟排序中,一次交换都没有发生过
                break;
            } else {
   
     
                flag = false; // 重置flag!!!, 进行下次判断
            }
        }
        return array;
    }

    /*
     * 推导的方法
     * */
    public static int[] deductionBubbleSort(int[] array) {
   
     
        /*
         * 为了容易理解,把冒泡排序的演变过程展示一下:
         * */
        //1、第一趟排序,就是将最大的数排在最后
        int temporary = 0; // 临时变量
        for (int i = 0; i < array.length - 1 - 0; i++) {
   
      // 总共为 4次 大循环遍历
            // 如果前面的数比后面的数大,则交换
            if (array[i] > array[i + 1]) {
   
     
                temporary = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temporary;
            }
        }

        System.out.println("每步演练的过程::");
        System.out.println("第一趟排序后的数组:");
        System.out.println(Arrays.toString(array));

        // 第二趟排序,就在将第二大的数排在倒数第二位
        for (int i = 0; i < array.length - 1 - 1; i++) {
   
      // 总共为 4次 大循环遍历
            // 如果前面的数比后面的数大,则交换
            if (array[i] > array[i + 1]) {
   
     
                temporary = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temporary;
            }
        }
        System.out.println("第二趟排序后的数组:");
        System.out.println(Arrays.toString(array));

        // 第三趟排序,就在将第二大的数排在倒数第三位
        for (int i = 0; i < array.length - 1 - 2; i++) {
   
      // 总共为 4次 大循环遍历
            // 如果前面的数比后面的数大,则交换
            if (array[i] > array[i + 1]) {
   
     
                temporary = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temporary;
            }
        }
        System.out.println("第三趟排序后的数组:");
        System.out.println(Arrays.toString(array));

        // 第四趟排序,就在将第二大的数排在倒数第四位
        for (int i = 0; i < array.length - 1 - 3; i++) {
   
      // 总共为 4次 大循环遍历
            // 如果前面的数比后面的数大,则交换
            if (array[i] > array[i + 1]) {
   
     
                temporary = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temporary;
            }
        }
        System.out.println("第四趟排序后的数组:");
        System.out.println(Arrays.toString(array));

        return array;
    }
}

1.4 测试结果

 

二、选择排序

2.1 基本介绍

选择式排序也属于 内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。

2.2 思路分析

2.2.1 选择排序思想

选择排序(select sorting)也是一种简单的排序方法。它的 基本思想是
第一次从arr[0]~ arr[n-1]中选取最小值,与arr[0]交换,
第二次从arr[1]~ arr[n-1]中选取最小值,与arr[1]交换,
第三次从arr[2]~ arr[n-1]中选取最小值,与arr[2]交换,…,
第i次从arr[i-1]~ arr[n-1]中选取最小值,与arr[i-1]交换,…,
第n-1次从arr[n-2]~arr[n-1]中选取最小值,与arr[n-2]交换,
总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

2.2.2 思路分析图

对一个数组的选择排序再进行讲解
 
对图解的说明:
说明:

1、 选择排序一共有**【数组大小-1】轮排序;
2、 每1轮排序,又是一个循环,循环的规则(代码)
2、 1
先假定**当前这个数是最小数;
2、 2然后和后面的每个数进行比较,如果发现有比当前数更小的数,就重新确定最小数,并得到下标;
2、 3当遍历到数组的最后时,就得到本轮最小数和下标;
2、 4交换[代码中再继续说];

 

2.3 代码实现

  • 时间复杂度:O(n^2)
  • 实现对一位数组{101, 34, 119, 1}的排序
  • 代码实现是分为三部分学习的

1、 对每一步的循环进行分析、推导,其方法为deductionSelectSort(int[]array)
2、 1首先定义两个变量,minIndex、min,分别表示最小值下标、最小值;
2、 2假定第一个数据为最小值,然后拿着这个数据和其他数据比较(使用遍历);
2、 3找到最小值后,将其与数组的第一个值进行互换(默认排序是从小到大);
2、 对第一步的推导找出规律,合成两个for循环其方法为selectSort(int[]array)
3、 测试80000个数据排序所需要的时间其方法为testTime()方法,5S左右,比冒泡快;

package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 选择排序
 * 时间复杂度: O(n^2)
 * 分为三步:
 * 1、每一步进行推导。 deductionSelectSort(int[] array)方法
 *    1.1 首先定义两个变量,minIndex、 min,分别表示 最小值下标、最小值
 *    2.1 假定第一个数据为最小值,然后拿着这个数据和其他数据比较(使用遍历)
 *    1.2 找到最小值后,将其与数组的第一个值进行互换(默认排序是从小到大)
 * 2、找到规律,合成两个for循环。 selectSort(int[] array)方法,并进行优化:
 * 3、测试 80000 个数据排序所需要的时间。 testTime()方法         5S 左右, 比冒泡快
 * */
public class S2_SelectSort {
   
     
    public static void main(String[] args) {
   
     
        int array[] = new int[]{
   
     101, 34, 119, 1};
        System.out.println("排序前:");
        System.out.println(Arrays.toString(array));

        System.out.println();
        System.out.println("排序后:");
//        deductionSelectSort(array); // 推导 的过程
        int[] ints = selectSort(array); // 推导后的方法
        System.out.println(Arrays.toString(ints));

        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用选择排序 所用的时间:");
        testTime();
    }

    /*
     * 测试一下 冒泡排序的速度O(n^2), 给 80000 个数据,测试一下
     * */
    public static void testTime() {
   
     
        // 创建一个 80000个的随机的数组
        System.out.println();
        int array2[] = new int[80000];
        for (int i = 0; i < 80000; i++) {
   
     
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印,耗费时间太长
        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要,但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        selectSort(array2);

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要,但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为:" + ((end - start) / 1000) + "秒");
    }

    /*
     * 推导后,合成的方法【重点掌握】
     * */
    public static int[] selectSort(int[] array) {
   
     
        /*
         * 在 deductionSelectSort()方法 推导的过程,发现了规律,因此,可以使用for循环解决。
         * 4个数据, 每次循环比较,找到最小值,放到最前面。共需要 3 次。  而每次找的时候 需要比较循环 3 次。正好为 【数据的大小-1】
         * */
        for (int i = 0; i < array.length - 1; i++) {
   
     
            int minIndex = i;
            int min = array[i];
            for (int j = i + 1; j < array.length; j++) {
   
     
                if (min > array[j]) {
   
       // 说明假定的最小值,并不是最小
                    minIndex = j; // 重置 min
                    min = array[j]; // 重置 minIndex
                }
            }
            // 将最小值,放在 array[i], 即交换: 交换时 做一个判断,如果 比较后,不需要赋值,那么下面两行不在执行,否则就重复了
            if (minIndex != i) {
   
     
                array[minIndex] = array[i];
                array[i] = min;
            }
//            System.out.println("第一轮后:");
//            System.out.println(Arrays.toString(array));
        }
        return array;
    }

    /*
     * 推导的方法
     * */
    public static void deductionSelectSort(int[] array) {
   
     
        /*
         * 使用逐步推导的方式来,讲解选择排序
         * 第1轮
         * 原始的数组;101, 34, 119, 1
         * 第一轮排序:[1, 34, 119, 101]
         * 算法 先简单--》做复杂,就是可以把一个复杂的算法,拆分成简单的问题-》逐步解决
         * */

        // 第一轮排序后:
        int minIndex = 0;
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
   
     
            if (min > array[i]) {
   
       // 说明假定的最小值,并不是最小
                minIndex = i; // 重置 min
                min = array[i]; // 重置 minIndex
            }
        }
        // 将最小值,放在 array[0], 即交换: 交换时 做一个判断,如果 比较后,不需要赋值,那么下面两行不在执行,否则就重复了
        if (minIndex != 0) {
   
     
            array[minIndex] = array[0];
            array[0] = min;
        }
        System.out.println("第一轮后:");
        System.out.println(Arrays.toString(array));
        // 第二轮排序后:
        minIndex = 1;
        min = array[1];
        for (int i = 1 + 1; i < array.length; i++) {
   
     
            if (min > array[i]) {
   
       // 说明假定的最小值,并不是最小
                minIndex = i; // 重置 min
                min = array[i]; // 重置 minIndex
            }
        }
        // 将最小值,放在 array[0], 即交换: 交换时 做一个判断,如果 比较后,不需要赋值,那么下面两行不在执行,否则就重复了
        if (minIndex != 1) {
   
     
            array[minIndex] = array[1];
            array[1] = min;
        }

        System.out.println("第二轮后:");
        System.out.println(Arrays.toString(array));

        // 第三轮排序后:
        minIndex = 2;
        min = array[2];
        for (int i = 2 + 1; i < array.length; i++) {
   
     
            if (min > array[i]) {
   
       // 说明假定的最小值,并不是最小
                minIndex = i; // 重置 min
                min = array[i]; // 重置 minIndex
            }
        }
        // 将最小值,放在 array[0], 即交换: 交换时 做一个判断,如果 比较后,不需要赋值,那么下面两行不在执行,否则就重复了
        array[minIndex] = array[2];
        array[2] = min;
        System.out.println("第三轮后:");
        System.out.println(Arrays.toString(array));
    }
}

2.4 测试结果

 

三、插入排序

3.1 基本介绍

插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。

3.2 思路分析

3.2.1 插入排序思想

插入排序(Insertion Sorting)的基本思想是
把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

3.2.2 插入排序思路图

 

3.3 代码实现

  • 时间复杂度:O(n^2)
  • 实现对一位数组{101, 34, 20, 1}的排序
  • 代码实现是分为三部分学习的

1、 对每一步的循环进行分析、推导,其方法为deductionSelectSort(int[]array)
2、 1先定义两个变量:insertValue、insertIndex,分别代表待插入的值(从数组第二个值开始)、待插入的下标;
2、 2先保存数组第二个值,进行循环,每次循环判断第二值(当前值)与第一个值(前一个值)的大小,若小则将第一个值(前一个值)后移,;
2、 3进行循环,循环一次,便将保存的当前值插入到所应该在的前面的位置;
2、 对第一步的推导找出规律,合成两个for循环其方法为selectSort(int[]array)
3、 测试80000个数据排序所需要的时间其方法为testTime()方法,5S左右,比冒泡快;

package com.feng.ch09_sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/*
 * 插入排序
 * 时间复杂度: O(n^2)
 * 分为三步:
 * 1、每一步进行推导。 deductionInsertSort(int[] array)方法
 *      1.1 先定义两个变量:insertValue、insertIndex,分别代表 待插入的值(从数组第二个值开始)、待插入的下标
 *      1.2 先保存数组第二个值,进行循环,每次循环判断第二值(当前值)与第一个值(前一个值)的大小,若小则将第一个值(前一个值)后移,
 *      1.3 进行循环,循环一次,便将 保存的当前值插入到所应该在的前面的位置。
 * 2、找到规律,合成两个for循环。 insertSort(int[] array)方法,并进行优化,优化 重点,二行代码
 * 3、测试 80000 个数据排序所需要的时间。 testTime()方法      1S 左右, 比选择、冒泡快
 * */
public class S3_InsertSort {
   
     

    public static void main(String[] args) {
   
     
        int[] array = {
   
     101, 34, 20, 1};

        System.out.println("原始数组:");
        System.out.println(Arrays.toString(array));

        System.out.println();
        deductionInsertSort(array);
//        int[] ints = insertSort(array);

        System.out.println("排序后:");
//        System.out.println(Arrays.toString(ints));

        // 测试 80000 个数据排序 所用的时间
        System.out.println();
        System.out.println("测试 80000 个数据 采用插入排序 所用的时间:");
        //testTime();
    }

    /*
     * 测试一下 冒泡排序的速度O(n^2), 给 80000 个数据,测试一下
     * */
    public static void testTime() {
   
     
        // 创建一个 80000个的随机的数组
        System.out.println();
        int array2[] = new int[80000];
        for (int i = 0; i < 80000; i++) {
   
     
            array2[i] = (int) (Math.random() * 8000000); // 生成一个[ 0, 8000000] 数
        }
//        System.out.println(Arrays.toString(array2)); // 不在打印,耗费时间太长
        long start = System.currentTimeMillis();  //返回以毫秒为单位的当前时间
        System.out.println("long start:" + start);
        Date date = new Date(start); // 上面的也可以不要,但是我想测试
        System.out.println("date:" + date);
        SimpleDateFormat format = new SimpleDateFormat("yyyy-mm-dd HH:mm:ss");
        System.out.println("排序前的时间是=" + format.format(date));

        insertSort(array2);

        System.out.println();
        long end = System.currentTimeMillis();
        Date date2 = new Date(end); // 上面的也可以不要,但是我想测试
        System.out.println("排序后的时间是=" + format.format(date2));
        System.out.println("共耗时" + (end - start) + "毫秒");
        System.out.println("毫秒转成秒为:" + ((end - start) / 1000) + "秒");
    }

    /*
     * 推导后 合成的 插入排序
     * */
    public static int[] insertSort(int[] array) {
   
     
        int insertValue = 0;
        int insertIndex = 0;
        for (int i = 1; i < array.length; i++) {
   
     
            // 定义 待插入 的数
            insertValue = array[i]; // 保存 第二个数
            insertIndex = i - 1;   // 保存要插入的位置
            /*
             * 给 insertValue 找到插入的位置
             * 说明
             * 1、insertIndex >= 0 保证再给 insertValue 找插入位置,不越界
             * 2、insertValue < array[insertIndex] 待插入的数,还没有找到插入位置
             * 3、就需要 array[insertIndex] 后移
             * */
            while (insertIndex >= 0 && insertValue < array[insertIndex]) {
   
     
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }
            // 当退出 while 循环时,说明插入的位置找到,insertIndex +1;
            // 举例:理解不了,debug 可以帮助理解
            // 这里我们判断是否需要赋值
            if (insertIndex + 1 != i) {
   
      // insertIndex+1 == i  ,就不需要进行赋值了,因为这时是正好的排序
                array[insertIndex + 1] = insertValue;
            }
        }
        return array;
    }

    /*
     * 推导插入排序
     * */
    public static int[] deductionInsertSort(int[] array) {
   
     
        // 使用逐步推导的方式来讲解,便于理解

        // 第一轮{101, 34, 119, 1} =》 {34, 101 119, 1}
        // 定义 待插入 的数、插入的位置
        int insertValue = array[1]; // 保存 第二个数
        int insertIndex = 1 - 1;   // 保存要插入的位置

        /*
         * 给 insertValue 找到插入的位置
         * 说明
         * 1、insertIndex >= 0 保证再给 insertValue 找插入位置,不越界
         * 2、insertValue < array[insertIndex] 待插入的数,还没有找到插入位置
         * 3、就需要 array[insertIndex] 后移
         * */
        while (insertIndex >= 0 && insertValue < array[insertIndex]) {
   
     
            array[insertIndex + 1] = array[insertIndex];
            insertIndex--;
        }
        // 当退出 while 循环时,说明插入的位置找到,insertIndex +1;
        // 举例:理解不了,debug 可以帮助理解
        array[insertIndex + 1] = insertValue;

        System.out.println("第一轮插入");
        System.out.println(Arrays.toString(array));
        // 第 2 轮
        insertValue = array[2];
        insertIndex = 2 - 1;
        while (insertIndex >= 0 && insertValue < array[insertIndex]) {
   
     
            array[insertIndex + 1] = array[insertIndex];
            insertIndex--;
        }
        array[insertIndex + 1] = insertValue;
        System.out.println("第二轮插入");
        System.out.println(Arrays.toString(array));

        // 第 3 轮
        insertValue = array[3];
        insertIndex = 3 - 1;
        while (insertIndex >= 0 && insertValue < array[insertIndex]) {
   
     
            array[insertIndex + 1] = array[insertIndex];
            insertIndex--;
        }
        array[insertIndex + 1] = insertValue;
        System.out.println("第三轮插入");
        System.out.println(Arrays.toString(array));

        return array;
    }
}

3.4 测试结果