排序对于任何一个程序员来说，可能都不会陌生。你学的第一个算法，可能就是排序。大部分编程语言中，也都提供了排序函数。在平常的项目中，我们也经常会用到排序。今天我们就花点时间,来比较一下插入排序和冒泡排序.插入排序和冒泡排序的时间复杂度相同，都是 O(n2)，空间复杂度都是O(1),但是在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？分析一个排序的优劣我们一般从三个方面来分析:
1.这个排序是原地排序吗?
2.这个排序算法是稳定的吗?
3.这个算法的时间复杂度是多少?


冒泡排序
代码实现如下:

[AppleScript] 纯文本查看 复制代码

    private static void method1(int[] a) {
            if (a.length <= 1) return;

            for (int i = 0; i < a.length; ++i) {
                // 提前退出冒泡循环的标志位
                boolean flag = false;
                for (int j = 0; j < a.length - 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;  // 没有数据交换，提前退出
            }
        }

下面我们先来按照这三个问题来分析一下冒泡排序:
1.冒泡排序是原地排序吗?
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
2.冒泡排序是稳定的吗?
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
3.冒泡算法的时间复杂度是多少?
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为O(n2).平均时间复杂度的上限就是O(n2).



插入算法
代码实现:

[AppleScript] 纯文本查看 复制代码

    private static void method2(int[] a) {
        // 插入排序，a 表示数组，n 表示数组大小
        if (a.length <= 1) return;

        for (int i = 1; i < a.length; ++i) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                if (a[j] > value) {
                    a[j + 1] = a[j];  // 数据移动
                } else {
                    break;
                }
            }
            a[j + 1] = value; // 插入数据
        }
    }

同样也是这三个问题:
1.插入排序是原地排序吗?
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。
2.插入排序算法是稳定的吗?
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
3.插入算法的时间复杂度是多少?
如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n)。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n2).平均时间复杂度的上限也是O(n2).

经过这三个问题的分析,他俩都是相同的.但是为什么插入会比冒泡受欢迎呢? 我们从代码实现可以看出.冒泡排序会比插入排序的数据移动负载.冒泡排序需要三个赋值操作,而插入排序只需要一个赋值操作.

[AppleScript] 纯文本查看 复制代码

冒泡排序中数据的交换操作：
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;
}

我随机生成了一个长度10000的int数组.分别用冒泡和插入去排序.

[AppleScript] 纯文本查看 复制代码

        int[] arr = new int[10000];
        Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(100000);
        }
        long s = System.currentTimeMillis();
        method2(arr);
        long e = System.currentTimeMillis();
        System.out.println(e-s);

冒泡执行时间是208毫秒. 而插入排序值需要20毫秒.

排序对于任何一个程序员来说，可能都不会陌生。你学的第一个算法，可能就是排序。大部分编程语言中，也都提供了排序函数。在平常的项目中，我们也经常会用到排序。今天我们就花点时间,来比较一下插入排序和冒泡排序.插入排序和冒泡排序的时间复杂度相同，都是 O(n2)，空间复杂度都是O(1),但是在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？分析一个排序的优劣我们一般从三个方面来分析:
1.这个排序是原地排序吗?
2.这个排序算法是稳定的吗?
3.这个算法的时间复杂度是多少?


冒泡排序
代码实现如下:

[AppleScript] 纯文本查看 复制代码

    private static void method1(int[] a) {
            if (a.length <= 1) return;

            for (int i = 0; i < a.length; ++i) {
                // 提前退出冒泡循环的标志位
                boolean flag = false;
                for (int j = 0; j < a.length - 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;  // 没有数据交换，提前退出
            }
        }

下面我们先来按照这三个问题来分析一下冒泡排序:
1.冒泡排序是原地排序吗?
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
2.冒泡排序是稳定的吗?
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
3.冒泡算法的时间复杂度是多少?
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为O(n2).平均时间复杂度的上限就是O(n2).



插入算法
代码实现:

[AppleScript] 纯文本查看 复制代码

    private static void method2(int[] a) {
        // 插入排序，a 表示数组，n 表示数组大小
        if (a.length <= 1) return;

        for (int i = 1; i < a.length; ++i) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                if (a[j] > value) {
                    a[j + 1] = a[j];  // 数据移动
                } else {
                    break;
                }
            }
            a[j + 1] = value; // 插入数据
        }
    }

同样也是这三个问题:
1.插入排序是原地排序吗?
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。
2.插入排序算法是稳定的吗?
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
3.插入算法的时间复杂度是多少?
如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n)。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n2).平均时间复杂度的上限也是O(n2).

经过这三个问题的分析,他俩都是相同的.但是为什么插入会比冒泡受欢迎呢? 我们从代码实现可以看出.冒泡排序会比插入排序的数据移动负载.冒泡排序需要三个赋值操作,而插入排序只需要一个赋值操作.

[AppleScript] 纯文本查看 复制代码

冒泡排序中数据的交换操作：
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;
}

我随机生成了一个长度10000的int数组.分别用冒泡和插入去排序.

[AppleScript] 纯文本查看 复制代码

        int[] arr = new int[10000];
        Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(100000);
        }
        long s = System.currentTimeMillis();
        method2(arr);
        long e = System.currentTimeMillis();
        System.out.println(e-s);

冒泡执行时间是208毫秒. 而插入排序值需要20毫秒.