【算法导论】插入排序法

简介: 插入排序法的时间复杂度为n的平方,对于较小的输入规模来说,插入排序法比合并排序法更快些。在最佳情况下,即输入数组已经排序好,则时间复杂度可表示为n,是一个线性函数;在最差情况下,即输入数组是逆序排列时,时间复杂度为.

插入排序法的时间复杂度为n的平方,对于较小的输入规模来说,插入排序法比合并排序法更快些。在最佳情况下,即输入数组已经排序好,则时间复杂度可表示为n,是一个线性函数;在最差情况下,即输入数组是逆序排列时,时间复杂度为.插入排序法的具体实现方法如下:


具体的c/c++语言实现如下:

#include<iostream>
#include<ctime> 
using namespace std;

void InsectionSortAscend(int* arrayA,int Length);//插入排序法:升序
void InsectionSortDescend(int* arrayA,int Length);//插入排序法:降序

void main()
{
	clock_t start,finish;
    double totaltime;
    start=clock();

	int arrayA[6]={5,2,4,6,1,3};
	int Length=sizeof(arrayA)/sizeof(int);

	InsectionSortDescend(arrayA,Length);
	InsectionSortAscend(arrayA,Length);
    
	finish=clock();
    totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
    cout<<"此两个程序的运行时间为"<<totaltime<<"秒!"<<endl;
    
}
/*****************************************
/            插入排序
/输入:数组arrayA、数组长度
/输出:由小到大已排列好的数组
/时间复杂度:n的平方
/*****************************************/
void InsectionSortAscend(int* arrayA,int Length)
{
	int i=0;
	int j=0;
	int temp=0;
    
	for(i=1;i<Length;i++)
	{
		temp=arrayA[i];
		j=i-1;
		while(j>=0&&arrayA[j]>temp)
		{
			arrayA[j+1]=arrayA[j];
			j=j-1;
		}
		arrayA[j+1]=temp;
	}
    for(int i=0;i<Length;i++)
	   cout<<arrayA[i];
	cout<<endl;

}

/*****************************************
/            插入排序
/输入:数组arrayA、数组长度
/输出:由大到小已排列好的数组
/时间复杂度:n的平方
/*****************************************/
void InsectionSortDescend(int* arrayA,int Length)
{
	int i=0;
	int j=0;
	int temp=0;
    
	for(i=Length-2;i>=0;i--)
	{
		temp=arrayA[i];
		j=i+1;
		while(j<Length&&arrayA[j]>temp)
		{
			arrayA[j-1]=arrayA[j];
			j=j+1;
		}
		arrayA[j-1]=temp;
		
	}
    for(int i=0;i<Length;i++)
	   cout<<arrayA[i];
	cout<<endl;

}

注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为:

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
} 


排序法除了上述所说的之外还有大家都经常用的冒泡排序法,其时间复杂度为n的平方。在这里我就不具体介绍了。

下面简单介绍一下如何高效的计算多项式:


目录
相关文章
|
25天前
|
算法 搜索推荐 C#
|
1月前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
1月前
|
算法 搜索推荐
数据结构与算法-插入排序
数据结构与算法-插入排序
18 2
|
1月前
|
算法 搜索推荐 数据可视化
【漫画算法】插入排序:插入宝石的传说
【漫画算法】插入排序:插入宝石的传说
|
1月前
|
人工智能 搜索推荐 JavaScript
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
16 0
|
1月前
|
机器学习/深度学习 搜索推荐 算法
【C/排序算法】:直接插入排序和希尔排序
【C/排序算法】:直接插入排序和希尔排序
17 0
|
1月前
|
搜索推荐 算法
排序算法之插入排序
排序算法之插入排序
22 0
|
1月前
|
搜索推荐
排序算法---插入排序-----详解&&代码
排序算法---插入排序-----详解&&代码
|
1月前
|
人工智能 算法 C语言
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
24 0
|
2月前
|
搜索推荐 算法 Java
sort-05-insert sort 插入排序算法详解
这是一个关于排序算法的系列文章总结,包括冒泡排序、快速排序、选择排序、堆排序、插入排序等10种排序算法的详细讲解和Java实现。插入排序是一种简单直观的排序算法,通过构建有序序列并逐个插入新元素来排序。提供的Java代码展示了插入排序的实现过程,并附有测试示例。所有算法已开源在GitHub项目[https://github.com/houbb/sort](https://github.com/houbb/sort)中。

热门文章

最新文章