渐增型算法：插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了渐增型算法：插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2638字，纯文字阅读大概需要4分钟。

内容图文

渐增型算法：插入排序

源码参考《算法设计、分析与实现 徐子珊著》

一、算法说明

1、渐增型算法：作为算法的主体是一个循环，逐个处理输入数据，已经处理的部分为问题的解；即按顺序处理问题，当输入数据处理完，问题也就处理了。
2、算法特点：直观，时间复杂度不友好
3、个人理解：降低问题维度，将一维的输入数据转化成单个数据，能准确处理单个数据时，遍历整个输入数据即可。

二、插入排序算法

1、输入一个乱序的数组，使用插入排序算法，输出升序或者降序数组；
2、从乱序数组中，逐个取出元素，加入已经排序好的数组，保证新加入的元素不破坏当前数组排序；
3、将数组排序问题，转化成，单个元素有序插入已经排序数组问题；
4、问题初始状态：从原始数组中取出第一个元素，作为已排序的数组初始状态；
5、算法核心：单个元素插入已排序数组，从数组尾部比较，将数据后移，找到该元素对应位置。

三、代码实现

// V1:基础版本，功能正常；先用伪代码实现思路，便于思考；注意关键点的实现
int insertionSortV1(int *array, int len)
{
    int key, j;
    for (int i = 1; i < len; i++) {
        key = array[i];
        j = i;
        // 将key插入到已经排好序的array[j - 1]中，使array[j]有序;修改判断条件，可以控制顺序
        while (j > 0 && (array[j - 1] > key)) {
            array[j] = array[j -1];
            j--;
        }
        array[j] = key;
    }
    return 0;
}

四、使用指针优化，扩展通用性

1、指针使用说明：输入任意类型的数据，提供对应的比较函数，即可以实现排序，参考qsort。

2、比较函数实现：

// V2: 输入任意类型的数组，使用指针实现
int intGreater(void *x, void *y)
{
    // 需要先对指针类型进行强制转换
    return *(int *)x - *(int *)y;
}

int charGreater(void *x, void *y)
{
    // 需要先对指针类型进行强制转换
    return strcmp((char *)x, (char *)y);
}

3、算法优化实现：

int insertionSortV2(void *array, int len, int array_size, int (*cmp)(void *, void *))
{
    int j;
    // array_size 表示数组元素的大小
    void *key = (void *)malloc(array_size);
    memset(key, 0, array_size);

    for (int i = 1; i < len; i++) {
        // 利用指针取数
        key = memcpy(key, array + i * array_size, array_size);
        j = i;
        // 将key插入到已经排好序的array[j - 1]中，使array[j]有序
        while ((j > 0) && (cmp(key, array + (j - 1) * array_size) < 0)) {
            // 内存赋值，使用指针
            memcpy(array + j * array_size, array + (j - 1) * array_size, array_size);
            j--;
        }
        memcpy(array + j * array_size, key, array_size);
    }

    return 0;
}

五、测试代码

// 测试代码
int main(void)
{
    int array[ARRAY_LEN] = {9, 3, 2, 4, 6, 7, 1, 0, 5, 8};
    char array_char[ARRAY_LEN] = {'a', 'h', 'd', 's', 'c', 'W', 'l', 'M', 'Z', 'z'};
    int ret;

    // ret = insertionSortV1(array, ARRAY_LEN, sizeof(int), intGreater);
    ret = insertionSortV2(array_char, ARRAY_LEN, sizeof(char), charGreater);
    if (ret != 0) {
        printf(" insetion sort array failed.ret=%d\n", ret);
        goto out;
    }

    for (int i = 0; i < ARRAY_LEN; i++) {
        // printf("array[%d] = %d\n", i, array[i]);
        printf("array_char[%d] = %c\n", i, array_char[i]);
    }

out:
    while (1);
    return 0;
}

内容总结

以上是互联网集市为您收集整理的渐增型算法：插入排序全部内容，希望文章能够帮你解决渐增型算法：插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---