插入排序InsertionSort,参数是一个数组包含了n个待排序的数,输入的各个数字是原地排序的(sorted in place),意即这些数字就是在数组A中进行重新排序的,在任何时刻,至多只有其中的常数个数字是存储在数组之外的,当过程InsertionSort执行完毕后,输入数组A中就包含了已排好序的数组输出序列。
下面是利用C++语言实现的插入排序代码:
#include <iostream>
#define N 10
using namespace std;
//声明插入排序函数
int* insertionSort(int *array,int length);
int main()
{
int array[N] = {2,1,3,67,35,12,9,7,45,0};
insertionSort(array,N);
for(int i=0;i<N;i++)
{
cout<<array[i]<<endl;
}
return 0;
}
int * insertionSort(int * array,int length)
{
for(int i=1;i<length;i++)
{
int key = array[i];
int j = i-1;
while(j>=0 && array[j]>key)//注意j的取值>=0
{
array[j+1] = array[j];
j=j-1;
}//while
array[j+1] = key;
}//for
return array;
}
插入排序的算法复杂性分析:对于插入排序,它的复杂性依赖于待排序数组的一些属性,待排序数组长度、已排好序程度等。我们一般考察最坏情况下即逆序排序和最佳情况下即已排好序的复杂性。
最佳情况下:此时待排序数组已经是一个排好序的数组,推理可得程序运行时间可以表示为an+b;因此,它是n的一个线性函数。
最坏情况下:此时待排序数组是一个逆序数组,此时,我们必须把每个元素array[i]与整个已排序的子数组array[1...i-1]中的每个元素进行比较,因而,最坏情况下程序的运行 时间为an^2+bn+c,这是一个关于n的二次函数。
一般来说,如同插入排序一样,一个算法的运行时间对某一给定的输入来说,往往是固定的。
分享到:
相关推荐
直接插入排序法,是一个比较简单的排序法,比较基础,可供参考
c语言基本插入排序法c语言基本插入排序法c语言基本插入排序法c语言基本插入排序法
插入排序的c++实现,有注释,输入未排序double数组,输出排序好的double数组,由小到大排序
一段比较简便、易懂,且能运行的JAVA代码。运用的是插入排序法对10个数字进行排序。
网上有很多讲插入排序的算法,但大多数都没有提供完整的程序,于是我在业余时间参考网上资料写了一个插入排序的完整C++实现,在VC6.0++编译通过,大家打开压缩文件点击sort.dsw文件打开即可编译运行,代码也有详解的...
这一个原创C语言编写的数组大小排序法,包括插入法和冒泡法.通过学习它的思想,把握这两种基本的算法,达到举一反三的效果。
用c语言实现的插入排序法
插入排序插入排序插入排序插入排序插入排序插入排序插入排序
亂數用插入排序法 亂數用插入排序法 亂數用插入排序法
几种简单、高效的插入排序法,直接插入排序、冒泡排序法、选择排序,代码简单明了,可直接使用。
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
使用插入排序算法对输入的n个整数,按照从小到大的顺序排序。 Input Description 第一行输入一个整数n(0)。 第二行输入n个整数。 Output Description 输出排序后的整数,每个整数之间以一个空格分隔。注意:最后...
折半查找法采用循环和递归调用两种方式实现;还有直接插入排序法的C实现!
本人用了C#开发出选择排序法 ,冒泡排序法 ,插入排序法算法。希望能为C#语言的学习者带来一些益处。不要忘了,学语言要花大力气学数据结构和算法。
插入排序 插入排序 插入排序 插入排序 插入排序 dfdsfdsffdsf fdsfdsf dfsdfdsf
插入排序算法,随机数列,可控制数列的上下界限,c++。
直接插入排序通过键盘输入建立数组,再经过直接插入排序算法进行排序。在VS上X64编译通过。直接插入排序算法理论参考《算法导论》和张琨的《数据结构与算法分析(C++语言版)》
归并排序,插入排序,以及两种排序算法的结合C++实现