排序-插入排序

Posted on | In |

介绍

分析

基本思想:

1
通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到对应位置并插入该数据，使数据形成有序排列

算法描述:

  1. 第1个元素，作为有序序列
  2. 从数组中获取下一个元素，在已排序的元素序列中从后向前扫描，并判断给元素与已排序元素的大小
  3. 若排序序列的元素大于新元素，则将排序序列该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置
  6. 重复步骤2-5，直到处理完成
C实现
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
41
42
43
44
/**
 插入排序
 
 @param a 原数组
 @param len 数组长度
 */
void insertSort(int a[], int len)
{
    for (int i = 1; i < len; i++) {
        int t = a[i];
        int j = 0;
        for (j = i - 1; j >= 0; j--) {
            if (t < a[j]) {
                a[j + 1] = a[j];
            }
            else {
                break;
            }
        }
        a[j + 1] = t;
    }
}

/**
 测试插入排序
 */
void testInsertSort()
{
    int arr[8] = { 19, 3, 10, 9, 16, 11, 28, 26 };
    int len = sizeof(arr)/ sizeof(arr[0]);
    
    printf("插入排序前:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    
    insertSort(arr, len);
    
    printf("\n插入排序后:");
    for (int i = 0; i < len; i++) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
Swift实现
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
class InsertSort {
    
    /// 插入排序
    ///
    /// - Parameters:
    ///   - a: 原数组
    ///   - len: 数组长度
    func insertSort(a: inout [Int], len: Int) {
        for i in 1..<len {
            let temp = a[i];
            var index = i - 1;
            for j in (0...i-1).reversed() {
                if temp < a[j] {
                    a[j + 1] = a[j]
                }
                else {
                    break;
                }
                
                index -= 1
            }
            a[index + 1] = temp
        }
    }
    
    /// 测试
    func testInserSort() {
        var arr = [ 19, 3, 10, 9, 16, 11, 28, 26 ]
        print("插入排序前:\(arr)", separator: " ")
        insertSort(a: &arr, len: arr.count)
        print("插入排序后:\(arr)", separator: " ")
    }
}

总结

时间复杂度:

  • 最差O(n^2)
  • 最优O(n)
  • 平均O(n^2)

空间复杂度:

  • O(1)

稳定性:

  • 稳定