排序算法之插入排序

发表于

排序算法之插入排序

从这周开始，每周我将写一些工作中常用的算法如下：

  1. 冒泡排序和选择排序；
  2. 插入排序；
  3. 希尔排序；
  4. 归并排序及其优化；
  5. 快速排序及其优化；
  6. 堆排序；

下面开始正文：

插入排序

关于插入排序的理论部分就不说了，去看维基百科，里面有各种语言的实现版本。咱们看图说话，容易理解。

待排数组如下：

插入排序初始数组

第一步

我们首先考虑 8 这个元素，只有 8 这一个元素，所以就排好序了。

插入排序01

第二步

我们来考虑 6 这个元素：

插入排序02

我们要把 6 放在其前面数组中合适的位置，和它前面的 8 相比 6 比 8 要小，所以 6 和 8 要互换位置：

插入排序03

此时前两个元素就排好的位置：

插入排序04

第三步

我们来考虑 2 这个元素：

插入排序05
我们把 2 和 8 比，2 比 8 小，所以互换位置：

插入排序06
然后，把 2 和 6 比，2 比 6 小，所以互换位置：

插入排序07

至此前三个元素就排好的位置：

插入排序08

第四步

我们来考虑 3 这个元素：

插入排序09
我们把 3 和 8 比，3 比 8 小，所以互换位置：

插入排序10

然后，把 3 和 6 比，3 比 6 小，所以互换位置：

插入排序11
然后，把 3 和 2 比，3 比 2 大，所以不互换位置。

插入排序11
至此前四个元素就排好的位置：

插入排序12
后面就不一一列举了，思路尽在 一二三四步骤中。

写程序

上面的思路理解了，下面的程序就比较好写了：

插入排序13
我们从数组的索引为 1 的位置开始，因为索引为 0 的位置已经排好序（假设数组长度为 n）即：

1
2
3
for (int i = 1; i < n; i++) {
    
}

大范围的确定好了，我们要进行小范围的比较排序了，那么 1位置的元素假设为第 j 位，要和之前的 位置 j-1位置的元素比较，如果大于不需要交换，否则需要交换：那么：

1
2
3
4
5
6
7
for (int j = i; j > 0; j--) {
    if (arr[j] < arr[j - 1]) {
        swap(&arr[j], &arr[j-1]);
    } else {
        break;
    }
}

故完整的如下：

1
2
3
4
5
6
7
8
9
for (int i = 1; i < n; i++) {
    for (int j = i; j > 0; j--) {
        if (arr[j] < arr[j - 1]) {
            swap(&arr[j], &arr[j-1]);
        } else {
            break;
        }
    }
}

当然，也可以这么写(嗯，更好看，装下逼也是可以的😜😜😜)：

1
2
3
4
5
6
7
8
9
void insertSort(int arr[],int n) {
    
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && (arr[j] < arr[j - 1]); j--) {
            swap(&arr[j], &arr[j-1]);
            
        }
    }
}

测试

下面我们开始测试。测试用例呢 分为四种，分别为：

  1. 有序
  2. 近乎有序
  3. 随机
  4. 倒叙

我们测试10W个数据，测试它的排序时间，测试用例的程序在这里，测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int n  = 100000;
// 有序
int *a = generateSequenceArray(n);
// 近乎有序
int *b = generateRandomSequenceArray(n, 100);
// 随机
int *c = generateRandomArray(n,0,n);
// 倒叙
int *d = generateReverseArray(n);

int *a1 = copyGenerateRandomArray(a, n);

int *b1 = copyGenerateRandomArray(b, n);

int *c1 = copyGenerateRandomArray(c, n);

int *d1 = copyGenerateRandomArray(d, n);

printf("**************有序*************\n");
testSort("插入排序　　", insertSort,a1, n);
printf("\n**************近乎有序*************\n");
testSort("插入排序　　", insertSort,b1, n);
printf("\n**************随机*************\n");
testSort("插入排序　　", insertSort,c1, n);
printf("\n**************倒叙*************\n");
testSort("插入排序　　", insertSort,d1, n);

free(a);free(a1);

free(b);free(b1);

free(c);free(c1);

free(d);free(d1);

运行之后的log（这里是在MacBook Pro上测试的结果，其它可能不是这个时间，但大底相同）：

1
2
3
4
5
6
7
8
9
10
11
**************有序*************
sortname:插入排序　　	 sorttime: 0.000647s

**************近乎有序*************
sortname:插入排序　　	 sorttime: 0.051551s

**************随机*************
sortname:插入排序　　	 sorttime: 18.110468s

**************倒叙*************
sortname:插入排序　　	 sorttime: 36.259288s

由此可以看出：插入排序对于近乎有序的数组用时很少，当数组随机或者是最坏情况，那就比较耗时。

那，我们能不能改进呢？ 答案是可以的

插入排序的优化

在上面的看图说话中，某个元素要想找到自己的位置，则必须和之前的比较，完了之后可能要交换位置，如果说该元素是最小的，且是最后一个，那要交换 n-1 个了。我们知道 交换元素 是比较耗时的操作，那能不能不交换元素，也能找到它的合适的位置呢？方法还是的有的！采用赋值的方法

我们看第四步：

插入排序09
进行比较之后 3 比 8 小，我们在这里不进行交换，而是将 3 这个值记录下来为 e = 3,然后将 8 元素值 赋值到 3 的位置

插入排序14
然后将 e = 3 和 元素 6 比较，3 比 6 小，将 元素 6 赋值给其后一位：

插入排序15
然后将 e = 3 和 元素 2 比较，3 比 2 大，所以 元素 3 就找到了自己的位置：

插入排序16
看完图之后，这个思路是不是很清晰，下面的程序也是非常好写的：

1
2
3
4
5
6
7
8
9
for (int i = 1; i < n; i++) {
   
   int e = arr[i];//将该元素记录下来
   int j;
   for (j = i; j > 0 && arr[j - 1] > e; j--) {
       arr[j] = arr[j - 1];
   }
   arr[j] = e;
}

插入排序优化测试

我们利用前面的测试方法，测试一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
**************有序*************
sortname:插入排序　　	 sorttime: 0.000647s
sortname:插入排序优化	 sorttime: 0.000554s

**************近乎有序*************
sortname:插入排序　　	 sorttime: 0.051551s
sortname:插入排序优化	 sorttime: 0.025874s

**************随机*************
sortname:插入排序　　	 sorttime: 18.110468s
sortname:插入排序优化	 sorttime: 8.335453s

**************倒叙*************
sortname:插入排序　　	 sorttime: 36.259288s
sortname:插入排序优化	 sorttime: 16.780035s

看看测试时间，这个优化还是有明显的提高的！！！

不知道这一节你掌握了么？😜😜😜

最后附上Demo