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

    2020-03-14 23:25:11
    今天写一下直接插入排序:直接插入排序就是讲记录插入在已经排列好的有序表中,从而得到一个新的,递增为1的有序表. 先上代码: #include <stdio.h> void InsertSort(int * arr,int length) { int i,j; ...

      最近两天又重新刷了一遍大话数据结构,对几种排序还是深恶痛绝

      今天写一下直接插入排序:直接插入排序就是讲记录插入在已经排列好的有序表中,从而得到一个新的,递增为1的有序表.

      先上代码:

      

    #include <stdio.h>
    
    void InsertSort(int * arr,int length)
    {
    	int i,j;
    	int temp;
    	for(int i = 1;i<length;i++)
    	{
    		if(arr[i] < arr[i-1])
    		{
    			temp = arr[i];
    			for(j = i-1;arr[j] > temp;j--)
    				arr[j+1] = arr[j];
    			arr[j+1] = temp;
    
    		}
    	}
    }
    
    int main()
    {
    	int arr[] = {9,8,7,6,5,4,3,2,1};
    	InsertSort(arr,9);
    	for(int i = 0;i < 9;i++)
    		printf("%d\t",arr[i]);
    	return 0;
    }

    代码是用C语言写的,应该通俗易懂.

    所谓插入排序其实很简单的,在本子上画一下.我就用大话数据结构的哪个例子来做比方

    待排序数组为{0,5,3,4,6,2},在树上,他们把arr[0]当做临时变量,而代码中我用了temp,效果是一样的

    只有一个数的时候,当然谈不上什么有序无序了,所以我们直接从第二个数开始

    第一步:0 5 3(i) 4 6 2,发现,3小于5,无序,所以将3赋值给arr[0]也就是临时变量,那么久变成了

    第二步:3 5(j) 3(i) 4 6 2记录了哨兵的值以后,就将5右移,变成了

    第三步:3(j) 5 5(i) 4 6 2此时,发现arr[j] = arr[0],嵌套for循环跳出,再将临时变量赋值给arr[j+1]第一次交换就玩成了

    第四步:3(j) 3 5 4 6 2

    接下来我就不分析了直接看数组是怎么变化的

    4 3 5 4 6 2

    4 3 5 5 6 2

    4 3 4 5 6 2

    ........

     

    就是这样

    展开全文
  • 直接插入排序 是一种最简单的排序方法,其基本操作是将一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增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;
    }
    
    

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

    展开全文
  • 插入排序 /*************************** author:vivi data: 19-09-07 ****************************/ #include <...// function:直接插入排序 void InsertSort(int R[],int n) { int ...

    vivi直接插入排序

    /*************************** 
    * author:vivi
    * data: 19-09-07
    ****************************/  
    #include <stdio.h>
    #include <stdlib.h>``
    
    // function:直接插入排序
    void InsertSort(int R[],int n)              
    {
    	int i,j,temp;
    	for(i=1;i<=n-1;i++)
    	{
    		if(R[i]<R[i-1])
    		{
    	        temp = R[i];
    		    for(j=i-1;j>=0;j--)
    		    {
    			    if(temp<R[j]) 
    				{
    			    	R[j+1] = R[j];
    				} 
    				else break;
    		    }
    		    R[j+1] = temp;
    		    printf("R[%d]=%d\n",j+1,temp);
    	    }
    	}
    }
    
    void print(int R[],int n)
    {
    	int i;
    	for(i=0;i<n;i++)
    	{
    		printf("%d ",R[i]);
    	}
    	return;
    }
    
    int main() 
    {
        int R[10] = {12,10,15,4,6,1};
        InsertSort(R,6);
        print(R,6);
    	return 0;
    }
    
    
    展开全文
  • 对一维数组的直接插入排序,过程函数化。 什么是直接插入排序直接插入排序就是将某一个元素与顺序表中元素进行比较,然后插入到相应的位置,使整个顺序表处于有序状态。 对于插入排序,有三种方法:1. 直接...

    考研-数据结构-C-算法-数组-排序-直接插入

     

    语言:C语言 

    对一维数组的直接插入排序,过程函数化。

    什么是直接插入排序?

    直接插入排序就是将某一个元素与顺序表中元素进行比较,然后插入到相应的位置,使整个顺序表处于有序状态。

    对于插入排序,有三种方法:1.  直接插入排序2. 二分插入排序3.希尔排序

     

    1.为了方便阅读、理解,采取初始化数组的形式输入。当然也是可以放一个输入函数,将数据从命令框中或者直接调用文件函数,从文件中读取,从而获取待排序的数据。

    2.再者就是可以更改存储类型,定义一个LinkType的数据结构,将数据放在链表中。只是存储结构不同,算法的思想是一样的。

    3.没有写C++或者Java的版本,算法的核心都是一样的,只要理解了核心思想,剩下的就是不同语言的表达了。

    // 排序函数
    int InsertSortFun(int array[],int length)
    {
        int temp;
        int k;
        for(k=1;k<length;k++)     //从数组的第二个元素开始,终止于数组长度
        {
            temp=array[k];     //存放抽出来的元素A 
            int j=k;
            while(j>0&&array[j-1]>temp) //如果前一个元素大于A元素
            {
                array[j]=array[j-1];    //前一个元素往后移
                j--;
            }
            array[j]=temp;      //当前位置的原元素已往后移,把A元素填入
        }
    }

     实现排序的基本操作有两个:

    (1)“比较”序列中两个关键字的大小;

    (2)“移动”记录。

    性能分析:

    最好的情况(关键字在记录序列中顺序有序):

    “比较”的次数:

    “移动”的次数:

    0

    最坏的情况(关键字在记录序列中逆序有序):

    “比较”的次数:

    “移动”的次数:

    原始数据越接近有序,排序速度越快

    最坏情况下(输入数据是逆有序的) Tw(n)=O(n2)

    平均情况下,耗时差不多是最坏情况的一半 Te(n)=O(n2)

    要提高查找速度

    1. 减少元素的比较次数

    2. 减少元素的移动次数

    //  完整C代码
    #include <stdio.h>
    #include <stdlib.h>
    
    #define arraysize 5
    
    int InsertSortFun(int array[],int length)
    {
        int temp;
        int k;
        for(k=1;k<length;k++)     //从数组的第二个元素开始,终止于数组长度
        {
            temp=array[k];     //存放抽出来的元素A 
            int j=k;
            while(j>0&&array[j-1]>temp) //如果前一个元素大于A元素
            {
                array[j]=array[j-1];    //前一个元素往后移
                j--;
            }
            array[j]=temp;      //当前位置的原元素已往后移,把A元素填入
        }
    }
    
    void PrintArray(int array[]){   //打印数组的函数 
    	for(int i =0;i < arraysize ;i++)
    	printf("%d ",array[i]);
    }
    
    int main(){
    	
    	int array[arraysize] = {1,3,3,5,4};   //初始化数组 
    	InsertSortFun(array,arraysize);   //调用排序函数 
    	PrintArray(array);   //打印数组,进行输出 
    	return 0;
    } 

    运行结果:

    注:希望各位同行批评指正,多多交流,也希望能够帮助广大研友们。

    展开全文
  • 直接插入排序即是在要排序的数组中,假设前n-1(n>=2)个数已经是排好序的,现在要把第n个数插入到前n个已经排好序的数组中,使得这n个数也变成有序的,如此反复循环,使得要排序的数组中的最后一个元素也排好序, ...
  • 数据结构直接插入排序完整算法(C语言实现)【待补充…】 这里引用一篇博客写的蛮全面的(已运行) 链接link #include<stdio.h> #define MaxSize 100 typedef int keytype; typedef char infotype; typedef ...
  • #include<stdio.h> void insertsort(int *list, int length) { int i,j; int temp; for(i=0; i<length; i++){ if(list[i]>list[i+1]){ temp = list[i]; list[i] = list[i+1... list[i+1]...
  • #include #define N 8 void seqsearch(int a[]); void show(int a[]); int main() {     int a[N] = {50,36,66,76,95,12,25,36};  printf("原无序记录:\n");... printf("排序过程如下\n");
  • #include int main(){  int i,j,n,a[100],x;  scanf("%d",&n);  for(i=0;i  scanf("%d",&a[i]);  }  for(i=1;i  if(a[i-1]>a[i]){  j=i-1;  x=a[i];  
  • 一、直接插入排序 定义顺序表的存储结构 初始化顺序表为空表 输入10个元素创建含有10个元素的顺序表 输出顺序表 对顺序表进行直接插入排序(InsertSort) 输出排序后的顺序表 例如: 11 938 ...
  • 插入排序 对一个元素个数为20个的随机数组进行插入排序 #include <stdio.h> #include <stdlib.h> #include <time.h> void Display(int *a, int n){ for (register int i = 0; i < n; i++){ ...
  • #include "stdio.h" #define MAXSIZE 10//一个用作示例的小顺序表的最大长度 ...{//作直接插入排序 int i,j; for(i=2;i;i++) { r[0]=r[i]; //r[0]用作哨兵单元 j=i-1; while(r[0][j]) { r[j+1]=r[j]; //记录后移 j
  • 直接插入排序,根据魏敏洪的c数据结构编的
  • 【算法】直接插入排序C语言实现

    千次阅读 2015-02-06 00:44:48
    我抓牌的习惯是,在抓牌的时候,我要看着我的牌,看看牌的状况,有没有大小鬼,有几个2,有没有长的连,顺便做好基本的排序工作.比如我第一张牌抓的是7,放在手里,第二张牌是J,我把它放在7的后面(对,我默认是左到右升序的的)...
  • void InsertSort(int L[],int n) { int } //一般的方法 void InsertSort(int L[],int n) { int i,j,temp;...i++) //第一个循环,遍历待排序列 { temp=L[i]; j=i-1; while(j>=0&&temp<L
  • 折半插入排序 C语言

    2020-11-19 17:10:14
    直接插入排序采用顺序查找法查找当前记录在已排好序的序列中的插入位置,这个“查找”操作可利用“折半查找”来实现,由此进行的插人排序称之为折半插入排序( Binary Insertion Sort )。 算法步骤: ①设待排序的...
  • 上一节介绍了直接插入排序算法的理论实现和具体的代码实现,如果你善于思考就会发现该算法在查找插入位置时,采用的是顺序查找的方式,而在查找表中数据本身有序的前提下,可以使用折半查找来代替顺序查找,这种排序...
  • #include<stdio.h> int main() { int temp = 0; int arr[10] = { 38, 9, 5, 12, 4, 98, 20, 76, -20, 0 };...arr[j+1]) //如果当前的最大值情况改变,应继续向前判断大小关系,否则可以直接跳出循环 { temp
  • 1、直接插入排序 算法思想:直接插入排序是无序序列插入到有序序列中,通常假定a[0]为已经排好序的子序列,然后将剩下无序序列一个一个插入到有序的子序列中。适用于基本有序和数据量不大的情况。 例如对于一个无序...
  • 直接插入排序(1)直接插入排序的基本思想直接插入排序(Straight Insertion Sort)算法是一种常用且简单直观的方法。它的基本思想是:设有n个数据的待排序序列,假设前面1到i-1个数据已经有序,是长度为i-1的有序序列,...

空空如也

空空如也

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

直接插入排序c语言

c语言 订阅