【直接插入排序】

概念及原理参见百度百度-直接插入排序

C代码示例

/**
 直接插入排序

 @param k 待排序数组
 @param n 数组元素个数
 */
void insertSort(int k[], int n) {
    int i, j, temp = 0;
    
    for (i=1; i<n; i++) {
        if (k[i] < k[i-1]) {
            temp = k[i];
            // FIXME: 此处的第二表达式中如果没有 j>=0 条件，则排序结果会有问题，出现随机数进入排序数组中，排序结果错误
            for (j=i-1; j>=0 && k[j] > temp; j--) {
                k[j+1] = k[j];
            }
            k[j+1] = temp;
        }
    }
}

// 测试
void sortTest(void) {
//    printf("=================开始排序测试 begin=================");
//    int a[10] = {4, 5, 1, 2, 3, 6, 8, 10, 7, 9};
//    bulleSort(a, 10);
//    printf("\n=================开始排序测试 end=================\n");
    
    printf("++++++++++++++++++开始排序测试 begin++++++++++++++++++");
    
    int b[10] = {4, 5, 1, 2, 3, 6, 8, 10, 7, 9};
//    bulleSort2(b, 10);  // 正常的两两比较冒泡排序
//    selectSort(b, 10);
    insertSort(b, 10);
    
    printf("\n排序完成后：\n");
    for (int i = 0; i < 10; i++) {
        printf("%d ", b[i]);
    }
    
    printf("++++++++++++++++++开始排序测试 end++++++++++++++++++");
}