为什么插入排序比冒泡排序更受欢迎？

为什么插入排序比冒泡排序更受欢迎？（而选择排序又不做考虑）

• 排序算法的执行效率 考虑方向
• （排序）稳定性
• 冒泡排序
• 插入排序
• 选择排序
• 为什么插入排序比冒泡排序更受欢迎？

---

常见8种排序算法

排序算法	时间复杂度	基于比较
冒泡排序、插入排序、选择排序	O(n^2)	是
快速排序、归并排序	O(nlogn)	是
桶排序、计数排序、基数排序	O(n)	否

排序算法的执行效率 考虑方向

1. 最坏时间复杂度、最好时间复杂度、平均时间复杂度
   两个相同最坏时间复杂度的，可能最好时间复杂度不一致，导致性能有所偏差。
2. 时间复杂度的系数、常数 、低阶
   在较少的数据排序下，系数的大小、常数等会对排序效率有较大影响，反之如果是一万、一百万、一亿，影响甚至会忽略不计。
   
3. 比较次数和移动次数
   选出2个所有参考（除了比较次数和移动次数）都相同的排序算法，这个参数在数量越大的情况下，会有巨大的效率差距。

（排序）稳定性

如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

冒泡排序

冒泡排序主要就是交换，相邻的两个元素进行交换。
一次冒泡需要交换 n-1次

需要进行 n 次冒泡

当判断没有数据交换时，可以减少冒泡次数。

// 冒泡排序，a 表示数组，n 表示数组大小
public void bubbleSort(int[] a, int n) {
 if (n <= 1) return;
 for (int i = 0; i < n; ++i) {
 // 提前退出冒泡循环的标志位
 boolean flag = false;
 for (int j = 0; j < n - i - 1; ++j) {
 if (a[j] > a[j+1]) { // 交换
 int tmp = a[j];
 a[j] = a[j+1];
 a[j+1] = tmp;
 flag = true; // 表示有数据交换
 }
 }
 if (!flag) break; // 没有数据交换，提前退出
 }
}

插入排序

有可能进行0到n-1次插入 *** 作

 	//4,2,6,7,3,2
    //2,4,6,7,3,2
    /**
     * 2,4,6,,7,2
     * 2,4,,6,7,2
     * 2,,4,6,7,2
     */
    //2,3,4,6,7,2
    //2,2,3,4,6,7

    public static void chaRu(int[] arr){
        if (arr.length==1)return;

        //首先保证进行N次插入，（每一次：比较后，有可能不进行插入，移动等 *** 作。）
        for (int i = 0; i < arr.length; i++) {
            //保留每次可能进行插入 *** 作的对象
            int value = arr[i];
            //并且将最大可能移动 *** 作定为 i-1（比如第3位上，前面的1和2可有往后平移2次。）
            int j = i-1;
            for (; j >= 0; j--) {
                //当第j位上的数 大于 i位时。
                if (arr[j]>value){
                    //数据向后移一位
                    arr[j+1] = arr[j];
                }else {
                    //为了稳定性 当出现小于等于时，跳出。并决定了 向后移动（0-j）位。
                    break;
                }
            }
            //在第j+1位进行插入 *** 作
            arr[j+1] = value;
        }
    }

选择排序

    /**
     * 4,2,6,7,3,2
     * 选择排序
     */
    public static void select(int[] arr){
        if (arr.length==1)return;

        for (int i = 0; i < arr.length-1; i++) {
            int t = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j]<arr[t]){
                    t = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[t];
            arr[t] = temp;
            System.out.println(Arrays.toString(arr));
        }
    }

为什么插入排序比冒泡排序更受欢迎？

时间复杂度都为O（n^2），冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。

冒泡排序中数据的交换 *** 作：
if (a[j] > a[j+1]) { // 交换
 	int tmp = a[j];
 	a[j] = a[j+1];
 	a[j+1] = tmp;
 	flag = true;
}
插入排序中数据的移动 *** 作：
if (a[j] > value) {
 	a[j+1] = a[j]; // 数据移动
} else {
 	break;
}

但是 冒泡排序 数据赋值了3次 插入只进行了1次。

在数据量越大的排序下，会越明显，即使数量少，插入排序也占优势。

如有错误欢迎指正