注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天涯倦客的博客

祝福你朋友永远快乐!

 
 
 

日志

 
 

直接插入排序  

2011-02-15 14:00:46|  分类: C# |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

直接插入排序(direct Insert Sort)的基本思想是:顺序地将待排序的记录按其关键码的大小插入到已排序的记录子序列的适当位置。子序列的记录个数从1开始逐渐增大,当子序列的记录个数与顺序表中的记录个数相同时排序完毕。
设待排序的顺序表sqList中有n个记录,初始时子序列中只有一个记录sqList[0]。第一次排序时,准备把记录sqList[1]插入到已排好序的子序列中,这时只需要比较sqList[0]和sqList[1]的大小,若sqList[0]≤sqList[1],说明序列已有序,否则将sqList[1]插入到sqList[0]的前面,这样子序列的大小增大为2。第二次排序时,准备把记录sqList[2]插入到已排好序的子序列中,这需要先比较sqList[2] 和sqList[1]以确定是否需要把sqList[2]插入到sqList[1]之前。如果sqList[2]插入到sqList[1]之前,再比较sqList[2]和sqList[0]以确定是否需要把sqList[2]插入到sqList[0]之前。这样的过程一直进行到sqList[n-1]插入到子序列中为止。这时,顺序表sqList就是有序的。
直接插入排序的算法如下所示,算法中记录的比较表示记录关键码的比较,顺序表中只存放了记录的关键码:
  //插入排序
        public void InsertSort(List<int> sqList)
        {
            for (int i = 1; i < sqList.Count; ++i)
            {
                if (sqList[i] < sqList[i - 1])
                {
                    int tmp = sqList[i];
                    int j = 0;
                    for (j = i - 1; j >= 0 && tmp < sqList[j]; --j)
                    {
                        sqList[j + 1] = sqList[j];
                    }
                    sqList[j + 1] = tmp;
                }
            }
        }

直接插入排序算法的时间复杂度分为最好、最坏和随机三种情况:
(1) 最好的情况是顺序表中的记录已全部排好序。这时外层循环的次数为n-1,内层循环的次数为0。这样,外层循环中每次记录的比较次数为1,所以直接插入排序算法在最好情况下的时间复杂度为O(n)。
(2) 最坏情况是顺序表中记录是反序的。这时内层循环的循环系数每次均为i。这样,整个外层循环的比较次数为 Σ?=+?=+1n1i2)1n)(1n()1i(
因此,直接插入排序算法在最坏情况下的时间复杂度为O(n2)。
(3) 如果顺序表中的记录的排列是随机的,则记录的期望比较次数为n2/4。因此,直接插入排序算法在一般情况下的时间复杂度为O(n2)。
可以证明,顺序表中的记录越接近于有序,直接插入排序算法的时间效率越高,其时间效率在O(n)到O(n2)之间。
直接插入排序算法的空间复杂度为O(1)。因此,直接插入排序算法是一种稳定的排序算法。
【例7-1】关键码序列为(42,20,17,27,13,8,17*,48),用直接插入排序算法进行排序。
排序过程如图7.1所示。

 

直接插入排序 - 海里的贝壳 - apple的博客

 

图7.1 直接插入排序示例图

  评论这张
 
阅读(1181)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017