YuHang’s Blog

谈谈排序（二）—— 基于交换的排序（冒泡&插入）

发表于

冒泡排序和插入排序都是基于交换而实现的

冒泡排序

基本思路

假设现在有一数组a{54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28}
现在将一个指针i放于数组的启示位置，之后开始与他后一个数组进行比较，若a[i]>a[i+1],则两个数交换位置。当这样的一趟排序完毕时，数组中最大的一个数组已经放到了数组的末尾，这时将剩余未排序的部分继续进行上述操作，当为排序的部分长度为1时，数组排序完毕。

实例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class BubbleSort {
    public void bubbleSort(int[] a, int len) {
//        外层排序是将冒泡的过程完成n次
        for (int i = len; i > 0; i--) {
//            内层用于完成一次冒泡
            for (int j = 0; j < i - 1; j++) {
                if (a[j + 1] < a[j]) {
                    swap(a, j + 1, j);
                }
            }
        }
    }
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

难点分析

内层未排序部分的判断：排序部分从数组中最后一个元素开始，长度为(len-i)。所以内层每次循环时，是从首元素到未排序的最后一个元素的遍历
初始状态：
数组最开始
进行中状态：

排序中的状态
注：红色箭头间是未排序的，红绿箭头见是排序好的

插入排序

基本思路

将数组分为两个部分：已排序和未排序。初始状态a[0]为已排序部分；a[1]-a[n]未排序
1.将未排序部分中的第一个数字拿出来放在已排序数组中第一个比他大的数字的前面
2.重复此过程直到未排序部分数组长度为0

实例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class InsertionSorting {
    public int[] insertionSort(int A[], int n) {
        for (int i = 1; i <= n; ++i) {     //i--n 为为排序部分
            int index = i;  //记录未排序部分第一元素的指针
            for (int j = i-1; j > 0; --j) {     //0--j 为已排序部分
                if (A[index - 1] > A[j - 1]) break;
                swap(A, index, j);
                index--;
            }
        }
        return A;
    }
    private void swap(int[] a, int position1, int position2) {
        int temp = a[position1 - 1];
        a[position1 - 1] = a[position2 - 1];
        a[position2 - 1] = temp;
    }
}

难点分析

难点在于如何分割排序部分和已排序部分

有什么用

好了，这两个排序算法都说完了，但是因为O(n2)的时间复杂度，所以日常生活中没人会用。但是学习的是编程中的一些技巧，现在总结一下。

  1. 关于数组操作和思维方式
    数组从零开始，但是很多题在思考的时候是从1开始的(树的根节点)。这时候按照自己的思路去写，然后将所有有关使用数组的地方下标统统-1，这样代码就没有问题了。不用进行反复思路的切换，减少出错的几率。
    2.冒泡排序和插入排序可以这样进行抽象：
    冒泡排序：将数组中最大/最小的一个数字去掉
    插入排序：将一个新的数字插入到数组中合适的位置
    冒泡&插入：将数组分为排序和未排序两个部分，这样每次我只用处理未排序的部分就行了
    以上的三种抽象在使用场景中的使用会频繁很多，所以还是有必要熟悉熟悉的