OC算法02：插入排序探索

张建 lol
  2020-08-07 19:28:01 2020-08-07 19:28 Created   2023-04-25 20:44:30 2023-04-25 20:44 Updated      

基本思想

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到全部对象都插入为止。即边插入边排序，保证子序列中随时都是排好序的。

基本操作

有序插入

  • 在有序列序列中插入一个元素，保持序列有序，有序长度不断增加。

  • 可以插入在中间、最前面和最后面

插入排序种类

  1. 顺序法定位插入位置 – 直接插入排序

  2. 缩小增量多遍插入排序 – 希尔排序

直接插入排序

  1. 基本思路：每轮排序把数组分为2部分，一部分为已排序好的数组，一部分为还未排序好的数组。每次取出还未排序好的数组中首元素与已排序好的数组从右往左比较。如果发现从未排序中取出的元素比从已排序中取出的元素大，就把该未排序的元素插入到从已排序中取出元素的后面。这样每一轮就能确定一个未排序元素在已排序数组中的准确位置

  2. 算法思想

  • 从第一个元素开始，该元素可以认为已经被排序

  • 取出下一个元素，在已经排序的元素序列中从后向前扫描

  • 如果该元素（已排序）大于新元素，将该元素移到下一位置

  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

  • 将新元素插入到下一位置中

  • 重复步骤2~5

  1. 直接插入排序的流程演示

流程举例: 红色的为已排序部分，蓝色的为未排序部分

1）原始数据：首先把原数组从下坐标1开始拆分为2部分， 已排序部分(红色)，未排序部分(蓝色)。默认原数组首元素为已排序元素。

2）第一轮：接着用后面未排序部分的第一个元素与已排序部分的最后一个元素进行比较，这里发现已排序最末尾元素5小于未排序元素第一个元素9.且元素5余元素9的位置是相邻的。不发生插入。把元素9列入已排序数组中。此时已排序好的元素多了一个。

3）第二轮：然后接着用后面未排序部分的第一个元素与已排序部分的最后一个元素进行比较，这里发现已排序最末尾元素9大于未排序元素第一个元素2。并且9不是已排序元素最前面一个元素，所以忽略本次操作，让元素2与已排序元素从右往左的下一个元素进行比较，此时发现已排序元素5大于元素2，但发现元素5是已排序元素中首个元素。则直接把元素2插入到元素5前面。

4）第三轮排序：用后面未排序部分的第一个元素与已排序部分的最后一个元素进行比较，这里发现已排序最末尾元素9小于未排序元素第一个元素15。且两个元素相邻。不发生插入，把元素15加入已排序部分。

5）第四轮排序：用后面未排序部分的第一个元素与已排序部分的最后一个元素进行比较，这里发现已排序最末尾元素15小于未排序元素第一个元素46。且两个元素相邻。不发生插入，把元素46加入已排序部分。

6）最后：依次按照上面的方式递归排序。直到所有元素排序完成。

  1. 列子:

代码实现：

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
- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSMutableArray * arr = [NSMutableArray arrayWithArray:@[@15,@2,@5,@10,@20]];
    
    // 插入排序的原理：始终定义第一个元素为有序的，将元素逐个插入到有序的排列中
    // 其特点是：不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去
    for (int i = 0 ; i < arr.count; i ++) {
        // temp为待排元素i为其位置
        NSNumber * temp = arr[i];
        // j为已排元素最后一个元素的位置
        int j = i - 1;
        // 当j>=0时，i为第一个待排元素，取已排元素和待排元素比较，在已经排好序中从后向前扫描
        while (j >= 0 && [arr[j] integerValue] > [temp integerValue]) {
            // 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置
            [arr replaceObjectAtIndex:j+1 withObject:arr[j]];
            j --;
        }
        // 跳出循环时，j已排元素小于或等于i的元素（待排元素）。插入新元素a[j+1] = temp，即空出来的位置插入待排序的值
        [arr replaceObjectAtIndex:j+1 withObject:temp];
        NSLog(@"插入排序排序中:%@",[self getArrayStr:arr]);
    }
}
// 将数组中的元素拼接成字符串 - 方便打印
- (NSString *)getArrayStr:(NSArray *)array {
    NSMutableString *strM = [NSMutableString string];
    for (NSNumber *num in array) {
        [strM appendString:[NSString stringWithFormat:@"%@,",num]];
    }
    return strM.copy;
}

打印结果:

1
2
3
4
5
2020-08-07 21:30:38.316438+0800 C-直接插入排序算法[3671:1382925] 插入排序排序中:15,2,5,10,20,
2020-08-07 21:30:38.316483+0800 C-直接插入排序算法[3671:1382925] 插入排序排序中:2,15,5,10,20,
2020-08-07 21:30:38.316502+0800 C-直接插入排序算法[3671:1382925] 插入排序排序中:2,5,15,10,20,
2020-08-07 21:30:38.316519+0800 C-直接插入排序算法[3671:1382925] 插入排序排序中:2,5,10,15,20,
2020-08-07 21:30:38.316535+0800 C-直接插入排序算法[3671:1382925] 插入排序排序中:2,5,10,15,20,
  1. 算法分析
  • 直接插入排序的算法性能

  • 时间复杂度

最好的情况（关键字在记录中顺序有序）：

  1. 当元素的初始序列为正序时，仅外循环要进行n-1趟排序且每一趟只进行一次比较，没有进入if语句不存在元素之间的交换(移动)。此时比较次数(Cmin)和移动次数(Mmin)达到最小值。 此时时间复杂度为O(n)。
1
2
比较次数：Cmin = n-1;
移动次数：Mmin = 0;
  1. 举例：

如：1 2 3 4 5
比较： 次数 移动
第2个元素和第一个元素比较 1 0
第3个元素和第二个元素比较 1 0
…
第n个元素和第n-1个元素比较 1 0
比较的次数：n-1
移动的次数：0

最坏的情况（关键字在记录序列中逆序有序）：

  1. 最差就是逆序。每趟排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移，i个元素后移移动次数当然也就为i了，再加上temp = arr[i]与arr[j+1] = temp的两次移动，每趟移动的次数为i+2,此时比较次数(Cmin)和移动次数(Mmin)达到最小值。 此时时间复杂度为O(n2)。
1
2
Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2)
Mmax = (1+2)+(2+2)+...+(n-1+2) = (n-1)*(n+4)/2 = O(n2)  (i取值范围1~n-1)
  1. 例子：

如：5 4 3 2 1
比较： 次数 移动
第2个元素和第1个元素比较 1 1+2
第3个元素和前2个元素比较 2 2+2
…
第n个元素和前n-1个比较 n-1 n-1+2
最后： 把1+2+…+n-1加起来求平均值
比较的次数：1+2+…+n-1 = (n+2)(n-1)/2
移动的次数：(1+2)+(2+2)+…+(n-1+2) = (n-1)*(n+4)/2 = O(n2) (i取值范围1~n-1)

事件复杂度结论：原始数据越接近有序，排序速度越快

1）最好的情况下（顺序有序）：O(n)
2）最坏的情况下（逆序有序）：O(n^2)
3）平均情况下，耗时差不多是最坏情况的一般：O(n^2)
4）要提高查找速度

减少元素的比较次数
减少元素的移动次数

  • 空间复杂度

由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 O(1) 。

  • 算法稳定性

直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。

  • 插入排序和选择排序的区别

  1. 插入排序和选择排序都有两层循环，外循环遍历整个数组

  2. 内循环稍有区别：

    • 选择排序的内循环是遍历一组未排过序的数组。
    • 插入排序的内循环是遍历一组已排过序的数组。

希尔排序

  1. 简介

    希尔排序(Shell Sort)，一听这名字就知道是一个叫希尔的外国人发明的排序。没错，他就是唐纳德 希尔（Donald Shell），一位美国的计算机科学家，他于1959年发明的希尔排序算法。

  2. 希尔排序思路

  • 希尔排序相当于 直接插入排序的加强版，在直接插入排序的概念之上加入了 增量 这个概念。

  • 什么是增量？
    插入排序只能与相邻的元素进行比较，而希尔排序则是进行 跳跃 比较，而 增量 就是 跳跃的 间隔数。
    所谓增量即是把数组按照一定间隔数分组成不同的数组。例如:@{1,2,3,4,5,6,7},一共有6个元素，假设把数组按照增量3进行分组，那么就是@{1,4,7},@{2,5},@{3,6}各分为一组。因为增量是3，所以每间隔3个下坐标为一组。

  • 按照增量分组后，把每一组的元素按照插入排序进行排序。当按照一个增量分组完成并每组数据按照插入排序完成后，将增量设为原本的二分之一，然后重复上面的步骤进行插入排序。直到增量为1，按照增量为1的最后一次进行分组插入排序。即完成了排序。

  1. 希尔排序的流程演示
  • 原始数据：@[@(11),@(10),@(9),@(8),@(7),@(6),@(5),@(4),@(3),@(2),@(1)]

  1. 第一次分组：

第一步，数组中有11个元素，把数组除以二，得到5(11/2实际是等于5余1，由于取正所以为5，由于有余数，所以按照增量取出来的数组的 组数 有 增量+1 即 5 + 1 = 6组。如果没有余数则组数就是增量数。)，以5为增量，从数组第一个元素开始，每间隔5个数取出来的所有元素分为一组，分为6组，分别是：
@{11,7}、@{10,4}、@{9,3}、@{8,2}、@{5,1}、@{6}

第一次排序：每种颜色为一组。接着对每组进行插入排序(具体比较过程就不说了，看过上面插入排序的应该懂)，排序结果为下图(共交换5次):
@{7,11}、@{4,10}、@{3,9}、@{2,8}、@{1,5}、@{6}

2)第二次分组：将增量5再次除以2，得到2(实际5/2是等于2余1，有余数所以组数为3)。分为3组分别是:
@{7,2,11,8}、@{4,1,10,5}、@{3,6,9}

第二次排序：每种颜色为一组，对每组元素进行插入排序。排序结果为(共交换4次)
@{2,7,8,11}、@{1,4,5,10}、@{3,6,9}

3)第三次分组：将增量2再次除以1，得到1(实际2/2等1，没有余数，所以分为1组)。分组后是
@{2,1,3,7,4,6,8,5,9,11,10}

第三次排序：最后对整组数组进行插入排序，排序结果为(共交换7次)：

  1. 希尔排序的特点

1）一次移动，移动位置比较大，跳跃式地接近排序后的最终位置
2）最后一次只需要少量移动
3）增量序列必须是递减的，最后一个必须是1
4）增量序列应该是互质的

  1. 实例
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
35
36
37
38
39
40
- (void)viewDidLoad {
    [super viewDidLoad];
    NSMutableArray * arr = [NSMutableArray arrayWithArray:@[@(9),@(3),@(8),@(5),@(2),@(4),@(7),@(6),@(1)]];
    [self shellSort:arr];
}

- (void)shellSort:(NSMutableArray *)list{
    // 起始间隔值gap设置为总数的一半
    int gap = (int)list.count / 2;
    // 直到gap==1结束
    while (gap >= 1) {
        //i为待排元素，以步距gap从后向前扫描
        for(int i = gap ; i < [list count]; i++){
            //temp为待排元素i为其位置
            NSInteger temp = [[list objectAtIndex:i] intValue];
            //获取当前位置
            int j = i;
            //然后将此位置之前的元素，按照增量进行跳跃式比较
            while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
                [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
                j -= gap;
            }
            //跳出循环时，j元素小于i的元素（待排元素）。插入新元素a[j] = temp，即空出来的位置插入待排序的值
            [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
        }
        NSLog(@"步长：%d --- 希尔排序:%@",gap,[self getArrayStr:list]);
        //步长
        gap = gap / 2;
    }
}

// 将数组中的元素拼接成字符串 - 方便打印
- (NSString *)getArrayStr:(NSArray *)array {
    NSMutableString *strM = [NSMutableString string];
    for (NSNumber *num in array) {
        [strM appendString:[NSString stringWithFormat:@"%@,",num]];
    }
    return strM.copy;
}

打印结果

1
2
3
2020-08-09 22:02:14.160098+0800 OC-哈希排序[23997:1116332] 步长：4 --- 希尔排序:1,3,7,5,2,4,8,6,9,
2020-08-09 22:02:14.160373+0800 OC-哈希排序[23997:1116332] 步长：2 --- 希尔排序:1,3,2,4,7,5,8,6,9,
2020-08-09 22:02:14.160620+0800 OC-哈希排序[23997:1116332] 步长：1 --- 希尔排序:1,2,3,4,5,6,7,8,9,
  1. 希尔排序算法分析：

1）希尔排序的时间复杂度与增量的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。
2）空间复杂度：
O(1)
3）是一种不稳定的排序算法：

  • Post title：OC算法02：插入排序探索
  • Post author：张建
  • Create time：2020-08-07 19:28:01
  • Post link：https://redefine.ohevan.com/2020/08/07/OC数据结构和算法/OC算法02：插入排序探索/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
On this page
OC算法02：插入排序探索
  1. 基本思想
  2. 基本操作
  3. 插入排序种类
    1. 直接插入排序
    2. 希尔排序