top
友情提示
测试消息
确定
友情提示

处理中,请稍后...

排序算法:插入排序之直接插入排序
排序算法是一个合格的必须掌握的基本算法之一。在程序设计中,排序是最常遇到的问题之一。排序算法有很多种,不同的算法有着不同的特性。今天的主角是直接插入排序,其属于插入排序算法之一,是一个比较经典的算法。

插入排序的基本思想:从初始有序的子集开始,不断地把新的数据元素插入到一排列有序集合的合适位置,使子集中的元素不断增多,当子集元素个数等于集合元素个数时,排序结束。

直接插入排序是插入排序的一种,其基本思想:顺序地把待排序的数据元素按其关键字值得大小插入到已排序已排序元素子集合的适当位置。子集合的大小从最初的一个元素,逐渐增大,当子集合的最终大小等于集合大小时,排序完毕。【没错,这段话和上一段差不太多,谁让其是插入排序的代表呢】

C语言实现及测试:
#include <stdio.h>

/**
 * 直接插入排序:升序排序
 * @param data[] : 待排序数据
 * @param      n : 数据集合长度
 *
 * 为方便演示, 这里以 ‘int数组’ 数据演示
 * 集合长度可以在内部获取, 但是当外部明确有集合长度是, 显然直接传入是更好的选择,避免额外操作
 */
void InsertSortAsc(int data[], int n){
    int i = 0, j = 0, temp = 0; 

    for(i = 0; i < n-1; i++){
        temp = data[i+1];
        j = i;
        while(j > -1 && temp < data[j]){  //降序:temp < data[j] 改为 temp > data[j] 即可
            data[j+1] = data[j];
            j--;
        }
        data[j+1] = temp;
    }
}

/**
 * 测试
 */
int main(int argc, char const *argv[]){
    
    int i = 0;
    int a[] = {2,5,1,9,3};
    InsertSortAsc(a, 5);

    for(i = 0; i < 5; i++){
        printf("%d ", a[i]);
    }

    return 0;
}

关键是排序思想,思想掌握无论哪种语言平台都可以快速实现。而且C语言是最基础的,由于是面向过程的,某些地方没有面向对象的语言方便,比如集合长度。

时间复杂度
我们分三种情况讨论:
(1)最好

最好的情况是集合本身就是排好序的,那么此时,算法中内层while循环的执行次数就为0,外层for循环比较次数均为1,数据元素赋值的执行次数均为2, 所以,整个过程中排序比较次数为 n-1 次, 赋值语句执行次数为 2(n-1)。故最好情况下,时间复杂度为 O(n)。
(2)最坏
最坏情况是集合中元素顺序与我们需要的顺序正好相反,这种情况下算法的内层循环次数每次都为i, 整个外层循环的比较次数为 (n-1)(n+2)/2, 移动次数为 (n-1)(n+4)/2。所以,最坏情况下直接插入排序的时间复杂度为 O(n2);
(3)随机
这种情况下,元素的期望比较次数和期望移动次数约为 (n2)/4。

所以,直接插入排序的平均时间复杂度为O(n2)。

总结
实际应用中比然是根据需求及数据类型作相应调整,特别是C语言。此处只是用了简单的数据类型测试,方便看算法步骤。另外,不同写法可能中间过程会不一样,比如遍历方向,但是处理思想是一致的。以上只是我个人见解,欢迎留下您的想法。
标签
排序
算法
插入排序
直接插入排序
上一篇:是时候温习一下“昨天”的内容了
下一篇:排序算法:插入排序之希尔排序
文章阅读完了, 快到评论区留下你的看法吧!
Email:
验证码:
昵 称 :
评论列表
热门标签
今日倒计时
小时 分钟
年少不识曲中意,再听已是曲中人
加油吧骚年
文章分类
最新文章
浏览排行
最新留言
[2018/11/27]博客该更新了
[2018/10/25]网站链接以便更 www.qiuyegen.com
[2018/04/07]太难找了,找到了
[2018/03/21]Entry fileTemplates//Singleton.java.ft not found in C:/Dev/android-studio/lib/resources_en.jar 该错误对我们使用AS没有影响吗?为什么复制保存后重新创建一个新的之后这个错误又出现了?
[2018/01/23]815cce30b85eb6b7ee7930c09135fcf7好漂亮的博客空间啊
[2018/01/06]好漂亮的博客.......
[2017/12/26]试试水
[2017/12/21] 博主可以分享一下这个源码不, 很喜欢这个博客
[2017/11/20]你加我友链了????
[2017/11/20]你的alert 很不友好哈
Copyright © 2018 DevSONG . All rights reserved. 有疑问或者建议? 留言给我或者E-mail me
滇ICP备17002307号-3