发布日期:2016-01-06 10:17 来源: 标签: 编程语言 开发语言 C++入门教程 C++插入排序
本章我们主要学习C++中插入排序法,下面我们就做一下具体讲解,希望大家多多支持中国站长网络学院。
插入法:
插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
     int iTemp;
     int iPos;
     for(int i=1;i<Count;i++)
     {
         iTemp = pData[i];
         iPos = i-1;
         while((iPos>=0) && (iTemp<pData[iPos]))
         {
             pData[iPos+1] = pData[iPos];
             iPos--;
         }
         pData[iPos+1] = iTemp;
     }
}
void main()
{
     int data[] = {10,9,8,7,6,5,4};
     InsertSort(data,7);
     for (int i=0;i<7;i++)
         cout<<data[i]<<" ";
     cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数:6次
交换次数:3次
其他:
第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数:4次
交换次数:2次
上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是,因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<=1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’而这里显然多了一些,所以我们浪费了时间。
最终,我个人认为,在简单排序算法中,选择法是最好的。

相关评论

专题信息
    Visual C++是一个功能强大的可视化软件开发工具,是高等院校计算机及相关专业主要核心课程。 本教程对Visual C++ 的应用与开发进行了详细系统的介绍,内容主要包括:Visual C++程序的建立,菜单、工具栏和状态栏的创建,对话框和常用控件,窗口、文档与视图,图形绘制,数据库应用,多媒体技术等。 本教程以案例教学为主,各章节都附有大量的实例,并且操作步骤详细,有利于引导读者更好的消化、理解和实际应用本章节所学的知识内容,希望大家能多多支持中国站长网络学院!