精华内容
下载资源
问答
  • 插入排序C语言实现

    2011-12-03 16:26:38
    插入排序C语言实现 插入排序C语言实现 插入排序C语言实现
  • 插入排序 C语言实现

    2009-10-26 15:02:51
    经典的插入排序算法,C语言实现,数据结构必备
  • 插入排序c语言实现

    2020-08-03 18:48:12
    插入排序 算法思想: 细心的同学会发现,我们把打扑克牌过程放慢,从获得第一张牌开始接下来我们按照从大到下(小到大)进行排序,我们当前获得一张牌如何在已排好序的的牌中按大小占据合适位置。这就需要依次与...

    插入排序

    算法思想:

    细心的同学会发现,我们把打扑克牌过程放慢,从获得第一张牌开始接下来我们按照从大到下(小到大)进行排序,我们当前获得一张牌如何在已排好序的的牌中按大小占据合适位置。这就需要依次与之前排好序的扑克牌进行比较,直到找到比之大或比之小的牌我们就将其放置此处。

    //插入排序 
    #include<stdio.h>
    #include<stdlib.h>
    int main()
    {
        int a[10]={0,2,1,6,8,7,3,5,4,9};
        int i,j,t,l; 
        for(i=1;i<10;i++)
        {
            for(j=i;j>0;j--)
            {
                if(a[j]<a[j-1])
                {
                    t=a[j-1];
                    a[j-1]=a[j];
                    a[j]=t;
                }                
            }
        }
        for(l=0;l<10;l++)
        {
            printf("%d\n",a[l]);
        }
    }
    算法复杂度:O(n²)
    算法空间复杂度:O(1)
    算法稳定性:稳定

    展开全文
  • 直接插入排序 是一种最简单的排序方法,其基本操作是将一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表。 算法步骤: (1)设待排序的记录存放在数组Data[1…n]中,Data[1]是一个有序序列...

    直接插入排序

    是一种最简单的排序方法,其基本操作是将一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表。

    算法步骤:

    (1)设待排序的记录存放在数组Data[1…n]中,Data[1]是一个有序序列。
    (2)循环n-1次,每次使用顺序查找法,查找Data[ ](i = 2,…,n)在已排好序的序列Data[ 1…i-1 ]中插入位置,然后将Data[i]插人表长为i-1的有序序列Data[ 1…i-1 ],直到将Data[n]插人表长为n-1的有序序列Data[ 1…n-1 ],最后得到一个表长为n的有序序列。

    书上的例子
    在这里插入图片描述
    时间复杂度

    最好情况:O(n)
    最坏情况:O(n2n^2)
    平均情况:O(n2n^2)

    空间复杂度

    O(1)

    稳定性

    稳定

    完整代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100  //顺序表最大容量,可以自行加大 
    
    typedef struct 
    {
    	int key;//关键字项 
    	char *otherinfo;//其他数据项 
    }ElemType;//记录类型 
    typedef struct
    {
    	ElemType Data[MAXSIZE+1];//静态顺序表的数据域,这里Data[0]为空闲或者为哨兵单元 
    	int length;//顺序表的长度 
    }SqList;//顺序表 
    
    void InitList(SqList &L)//顺序表的初始化 
    {
    	L.length = 0;//使顺序表长度归0,便是顺序表的初始化 
    }
    
    void CreateList(SqList &L)//顺序表的创建 
    {
    	printf("请输入:"); 
    	while(1)//建立一个死循环,循环终止条件是按了enter键 
    	{
    		L.length++;//顺序表长度加一 
    		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
    		{
    			printf("顺序表已满!\n");
    			return ;
    		}
    		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
    		if(getchar() == '\n')//循环终止条件 
    			break;
    	}
    }
    
    void InputList(SqList L)//顺序表的输出 
    {
    	int i;//记录次数 
    	if(L.length == 0)//判断顺序表是否为空 ,若为空结束该函数 
    	{
    		printf("顺序表是空的!\n");
    		return ;
    	}
    	printf("打印为:");
    	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
    		printf("%d ",L.Data[i].key);	
    }
    
    void InsertSort(SqList &L)//直接插入排序 
    {
    	int i,j;//i表示为轮到第i个数据插入,j表示为第i个数据插入的地址 
    	for(i=2;i<=L.length;i++)//利用循环逐个插入 
    	{
    		if(L.Data[i].key<L.Data[i-1].key)//判断第i个和i-1个数据的大小,若小于,需将Data[i]插入有序子表中 
    		{
    			L.Data[0] = L.Data[i];//将待插入的记录在监视哨中 
    			L.Data[i] = L.Data[i-1];//Data[i-1]后移 
    			for(j=i-2;L.Data[0].key<L.Data[j].key;j--)//从后往前寻找插入位置 
    				L.Data[j+1] = L.Data[j];//记录逐个后移,直到找到插入位置 
    			L.Data[j+1] = L.Data[0];//将Data[0]即Data[i],插入到正确位置 
    		}
    	}
    }
    
    int main()
    {
    	SqList L;
    	InitList(L);//初始化顺序表 
    	CreateList(L);//创建顺序表 
    	InsertSort(L);//直接插入排序 
    	InputList(L);//打印排序后结果 
    	return 0;
    }
    
    

    在这里插入图片描述
    (完)

    展开全文
  • 插入排序 1、直接插入排序 算法思想:直接插入排序是无序序列插入到有序序列中,通常假定a[0]为已经排好序的子序列,然后将剩下无序序列一个一个插入到有序的子序列中。适用于基本有序和数据量不大的情况。 例如对于...

    插入排序

    1、直接插入排序

    算法思想:直接插入排序是无序序列插入到有序序列中,通常假定a[0]为已经排好序的子序列,然后将剩下无序序列一个一个插入到有序的子序列中。适用于基本有序和数据量不大的情况。
    例如对于一个无序序列{45,32,56,71,12}来讲,首先确定45为有序的,然后在无序序列中向右遍历,32小于45则插入到45的前面,再继续往右遍历,56大于32同时也大于45则应该插入到45后面,依此类推直到得到有序序列。
    无序序列:{45,32,56,71,12}
    第一趟:32 45 56 71 12
    第二趟:32 45 56 71 12
    第三趟:32 45 56 71 12
    第四趟:12 32 45 56 71

    C语言代码如下:

    #include<stdio.h>
    #include<string.h>
    #define len 5
    void insertSort(int a[])
    {
    	int i,j,temp;
    	for(i=0;i<len;i++)
    	{
    		temp = a[i];
    		//当前数小于前一位数时
    		if(a[i] < a[i-1])
    		{
    			//将子序列重新排列为有序序列
    			for(j=i-1;temp<a[j];j--)
    			{
    				a[j+1] = a[j];
    			}
    			a[j+1] = temp;
    		}
    	}
    }
    int main()
    {
    	int a[] = {45,32,56,71,12};
    	int i;
    	printf("未排序前:\n"); 
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    	printf("\n经过直接插入排序后:\n"); 
    	insertSort(a);
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    }
    

    2、希尔排序

    算法思想:希尔排序需要定义一个增量d,然后根据增量将无序序列分割成若干个子序列,分别对这些子序列进行直接插入排序,当整个表中元素趋于“基本有序”时,再对整体序列进行一次直接插入排序。
    其中增量d可以缩小增量d=d/2,但是这个增量并不是最优的。
    形如序列{45,32,56,71,12},初始增量为d = len/2 = 2,故序列可分为{45,56},{32,71},{12},
    在这里插入图片描述
    对这三组分别进行直接插入排序,则小的元素被调换到前面继续缩小增量d=d/2=1。
    此时缩小完增量后,序列被分为1组,已经趋于“基本有序”,{45,56,32,71,12}最后直接进行直接插入排序就得到有序序列{12,45,56,32,71}.
    C语言代码:

    #include<stdio.h>
    #include<string.h>
    #define len 5
    void shellSort(int a[])
    {
    	int i,j,dk,temp;
    	//增量dk的变化,dk = dk/2
    	for(dk=len/2;dk>0;dk/=2)
    	{
    		for(i=dk;i<len;i++)
    		{
    			//需将a[i]插入有序增量子表中
    			if(a[i] < a[i-dk])
    			{
    				//存到临时变量中
    				temp = a[i];
    				for(j=i-dk;j>=0&&temp<a[j];j-=dk)
    				{
    					//统一记录后移,查找插入的位置	
    					a[j+dk] = a[j];
    				}
    				a[j+dk] = temp;
    			}
    		}
    	}
    }
    int main()
    {
    	int a[] = {45,32,56,71,12};
    	int i;
    	printf("未排序前:\n"); 
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    	printf("\n经过直接插入排序后:\n"); 
    	shellSort(a);
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    }
    

    3、折半插入排序

    折半插入排序是从折半查找转换而来,通过折半查找寻找插入位置,在确定待插入位置后,统一向后移动元素。(可以自行查看折半查找算法)

    #include<stdio.h>
    #include<string.h>
    #define len 5
    void binarySort(int a[])
    {
    	int i,j,low,mid,high,temp;
    	for(i=0;i<len;i++)
    	{
    		//设置折半查找的范围
    		low = 0;
    		high = i-1;
    		temp = a[i];
    		//进入折半查找
    		while(low <= high)
    		{
    			//取中间点
    			mid = (low+high)/2;
    			//如果小于中间的元素,则查找左半子表否则查找右半子表
    			if(temp < a[mid]){
    				high = mid - 1;
    			} else {
    				low = mid + 1;
    			}
    		}
    		//统一后移元素,空出插入位置
    		for(j=i-1;j>=high+1;j--)
    		{
    			a[j+1] = a[j];
    		}
    		a[high+1] = temp;
    	}
    }
    int main()
    {
    	int a[] = {45,32,56,71,12};
    	int i;
    	printf("未排序前:\n"); 
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    	printf("\n经过直接插入排序后:\n"); 
    	binarySort(a);
    	for(i=0;i<len;i++)
    	{
    		printf("%d  ", a[i]);
    	}
    }
    

    如果以上程序或解释有问题,请务必指出互相交流。

    展开全文
  • 插入排序算法 方法一 #include&lt;stdio.h&gt; void insertsort(int a[], int n){ int temp; for(int i = 1; i &lt; n; i++){ for(int j = 0; j &lt; i; j++){ //printf("%d\n", j);...

    插入排序算法

    方法一

    #include<stdio.h>
    
    void insertsort(int a[], int n){
        int temp;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                //printf("%d\n", j);
                //printf("%d\n", a[j]);
               if(a[j]>a[i]){
                    temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
               }
            }
        }
    }
    int main(){
        printf("hello world!\n");
        int a[6]={2, 5, 4, 6, 3, 1};
        for(int i = 0; i < 6; i++){
           	scanf("%d", &a[i]);
        }
        insertsort(a, 6);
        for(int i = 0; i < 6; i++){
           printf("%d\n", a[i]);
        }
        return 0;
    }
    
    
    展开全文
  • 数据结构直接插入排序完整算法(C语言实现)【待补充…】 这里引用一篇博客写的蛮全面的(已运行) 链接link #include<stdio.h> #define MaxSize 100 typedef int keytype; typedef char infotype; typedef ...
  • 插入排序 /*************************** author:vivi data: 19-09-07 ****************************/ #include <stdio.h> #include <stdlib.h> // function:直接插入排序 void InsertSort...
  • 直接插入排序即是在要排序的数组中,假设前n-1(n>=2)个数已经是排好序的,现在要把第n个数插入到前n个已经排好序的数组中,使得这n个数也变成有序的,如此反复循环,使得要排序的数组中的最后一个元素也排好序, ...
  • 插入排序 时间复杂度:O(N²) 稳定性:稳定 排序原理: 插入排序适合数据已大致有序了的场合 假定一个初始有序数列(初始设定首元素为有序数列),后边的元素都是待插入数据,一次插入一个, 在有序数列中找待...
  • 对一维数组的直接插入排序,过程函数化。 什么是直接插入排序? 直接插入排序就是将某一个元素与顺序表中元素进行比较,然后插入到相应的位置,使整个顺序表处于有序状态。 对于插入排序,有三种方法:1. 直接...
  • #include void main() { int A[6]={5,2,4,6,1,3};...//从右侧牌堆中抓一张key牌,key牌即手中抓的将要插入的牌 i=j-1;//与key牌左侧第一张牌比较 while((i>=0)&&(A[i]>key))//一直比较,将较小的牌移至左侧 {
  • 插入排序 对一个元素个数为20个的随机数组进行插入排序 #include <stdio.h> #include <stdlib.h> #include <time.h> void Display(int *a, int n){ for (register int i = 0; i < n; i++){ ...
  • 第二章算法基础2.1插入排序对于少量元素的排序,插入排序是个有效算法,工作方式类似于排序一手扑克牌。每次从桌上拿一张牌并将它插入另一手中正确的位置,为找到正确位置,依此对手中的牌进行比较,直到找出正确...
  • 一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下: ⒈ 从第一个元素开始,该元素可以认为已经被排序(先假定第一个待排序元素已排好序) ⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,726
精华内容 690
关键字:

插入排序c语言实现

c语言 订阅