同样的复杂度,为什么插入排序比冒泡排序更受欢迎?

前面了解了 冒泡排序 和 插入排序,时间复杂度、空间复杂度都相同:

  • 最好情况时间复杂度:O(n)
  • 最坏情况时间复杂度:O(n2)
  • 平均情况下的时间复杂度:O(n2)
  • 空间复杂度:O(1),稳定排序算法

但为什么实际开发中插入排序使用偏多呢?

原因如下:

  • 针对同一个数组,冒泡排序和插入排序,最优情况下需要交互数据的次数是一样(即原数组的逆序度一样)
  • 每次数据交换,冒泡排序的移动数据要比插入排序复杂。冒泡排序进行了 3 次赋值,插入排序进行了 1 次赋值

代码对比:

//冒泡排序int temp = array[j + 1];array[j+1] = array[j];array[j] = temp;hasSwitch = true;//有数据交换//插入排序if (array[j] > value) {    array[j+1] = array[j];} else {    break;}

测试代码:

package constxiong.interview.algorithm;import java.util.Random;/** * 测试冒泡排序 * @author ConstXiong * @date 2020-04-10 09:36:54 */public class CompareBubbleAndInsertionSort {        public static void main(String[] args) {        //生成两个一样长度的随机数组        int length = 10000;        int[] array_1 = generateArray(length);        int[] array_2 = new int[length];         System.arraycopy(array_1, 0, array_2, 0, length);        print(array_1);        print(array_2);                //比较冒泡排序与插入排序的耗时        long array_1_start = System.currentTimeMillis();        bubbleSort(array_1);        System.out.println("bubbleSort cost time : " + (System.currentTimeMillis() - array_1_start));        long array_2_start = System.currentTimeMillis();        insertionSort(array_2);        System.out.println("insertionSort cost time : " + (System.currentTimeMillis() - array_2_start));                //打印排序后的两个数组,看看结果是否正确        print(array_1);        print(array_2);    }        /**     * 生成随机数组     * @param length     * @return     */    private static int[] generateArray(int length) {        Random r = new Random();        int[] array = new int[length];        for (int i = 0; i <array.length; i++) {            array[i] = r.nextInt(length);        }        return array;    }        /**     * 冒泡排序     * @param array     */    private static void bubbleSort(int[] array) {        for (int i = 0; i <array.length; i++) {            //提前退出冒泡循环的标志            boolean hasSwitch = false;            //因为使用 j 和 j+1 的下标进行比较,所以 j 的最大值为数组长度 - 2            for (int j = 0; j <array.length - (i+1); j++) {                if (array[j] > array[j + 1]) {                    int temp = array[j + 1];                    array[j+1] = array[j];                    array[j] = temp;                    hasSwitch = true;//有数据交换                }            }            //没有数据交换退出循环            if (!hasSwitch) {                break;            }        }    }        /**     * 插入排序     */    private static void insertionSort(int[] array) {        for (int i = 1; i <array.length; i++) {            int j = i - 1;            int value = array[i];            for (; j >= 0; j--) {                if (array[j] > value) {                    array[j+1] = array[j];                } else {                    break;                }            }            array[j+1] = value;        }    }        /**     * 打印数组     * @param array     */    private static void print(int[] array) {        for(int i : array) {            System.out.print(i);        }        System.out.println();    }}

打印结果:

同样的复杂度,为什么插入排序比冒泡排序更受欢迎?-度崩网-几度崩溃

随着数组长度的提升,冒泡排序比插入排序多出的耗时也随之增多。

给TA打赏
共{{data.count}}人
人已打赏
Java

合并两个有序的链表

2020-7-31 3:35:00

Java

单向链表的反转

2020-7-31 3:38:20

本站所发布的一切源码、模板、应用等文章仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版,购买注册,得到更好的正版服务。如有侵权。本站内容适用于DMCA政策。若您的权利被侵害,请与我们联系处理,站长 QQ: 84087680 或 点击右侧 私信:盾给网 反馈,我们将尽快处理。
⚠️
本站所发布的一切源码、模板、应用等文章仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版,购买注册,得到更好的正版服务。如有侵权。本站内容适用于DMCA政策
若您的权利被侵害,请与我们联系处理,站长 QQ: 84087680 或 点击右侧 私信:盾给网 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索