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

Bertha 。 2023-07-24 09:27 9阅读 0赞

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

*  最好情况时间复杂度：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();
        }
    
    }

**打印结果：**

![format_png][]

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

--------------------

### 【Java面试题与答案】整理推荐 ###

*  [基础与语法][Link 1]
 *  [集合][Link 2]
 *  [网络编程][Link 3]
 *  [并发编程][Link 4]
 *  [Web][]
 *  [安全][Link 5]
 *  [设计模式][Link 6]
 *  [框架][Link 7]
 *  [算法与数据结构][Link 8]
 *  [异常][Link 9]
 *  [文件解析与生成][Link 10]
 *  [Linux][]
 *  [MySQL][]
 *  [Oracle][]
 *  [Redis][]
 *  [Dubbo][]

[format_png]: /images/20230528/a4cfab773184468693530908e9196438.png
[Link 1]: https://www.javanav.com/interview/93b0069472fd479393006c0e73043fc4.html
[Link 2]: https://www.javanav.com/interview/4147d95e693945e7a50345fd33ec817e.html
[Link 3]: https://www.javanav.com/interview/68a57ffc78de4133bb890bdd502ac418.html
[Link 4]: https://www.javanav.com/interview/36a24fa3258e45c89873f474ce914912.html
[Web]: https://www.javanav.com/interview/4e27cb63adb440c6825a159d35cf4010.html
[Link 5]: https://www.javanav.com/interview/03affb2ce3f04fda8853f714e5764906.html
[Link 6]: https://www.javanav.com/interview/07a32a9ff17a4006a53550ce658cafed.html
[Link 7]: https://www.javanav.com/interview/5c466456e9b54ab0a749b5948e51f1d3.html
[Link 8]: https://www.javanav.com/interview/943f917041ee4f05add24539f5b861b2.html
[Link 9]: https://www.javanav.com/interview/d3f058cfc05d4c6dadd821b622e84d36.html
[Link 10]: https://www.javanav.com/interview/67a50996c28f418e83b109ea42fc3eff.html
[Linux]: https://www.javanav.com/interview/00cccb81729540d1923bd0a0ef49533a.html
[MySQL]: https://www.javanav.com/interview/d311e78502a845f1a4bb307bd6aec2b3.html
[Oracle]: https://www.javanav.com/interview/5f29e9677edf4a16be3dce30d257c9ab.html
[Redis]: https://www.javanav.com/interview/066c62b3af4d4827b2243a822c3084a9.html
[Dubbo]: https://www.javanav.com/interview/9a3e7a7740324757abaab953f7ebc455.html