精华内容
下载资源
问答
  • 函数分析:InsertSort(SqList &L) 参数:顺序表L 功能:排序(默认升序)空间复杂度:O(1)...//直接插入排序 升序排序 void InsertSort(SqList &L) { int temp;int i,j; for(int i=2;i<=L....

    函数分析:InsertSort(SqList &L) 参数:顺序表L 功能:排序(默认升序)空间复杂度:O(1) 时间复杂度:O(n方)
                              稳定性:稳定

    代码:

    //直接插入排序 升序排序
    void InsertSort(SqList &L)
    {
    	int temp;int i,j;
    	for(int i=2;i<=L.length;i++)
    	{
    		if(L.data[i]<L.data[i-1])//比较有序表最后一个
    		{
    		
    			L.data[0]=L.data[i];//放入哨兵中
    			L.data[i]=L.data[i-1];
    			for(j=i-2;L.data[0]<L.data[j];j--)//比较后移
    			{
    				L.data[j+1]=L.data[j];
    			}
    			L.data[j+1]=L.data[0];//哨兵入列
    		}
    	}
    	PrintList(L);
    }

    全部代码:

    /*
        Project: insert_sort(直接插入排序) 
        Date:    2018/12/27
        Author:  Frank Yu
        InsertSort(SqList &L) 参数:顺序表L 功能:排序(默认升序)空间复杂度:O(1) 时间复杂度:O(n方)
    	                      稳定性:稳定
    	思想:L[0]设置为“哨兵”,当前数据与前一个数据进行比较,若小于,则说明需要插入,将数据放入到哨兵。
    	     边比较,边后移,直至找到正确位置,将哨兵插回。
    */
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #define MaxSize 100
    #define ElemType int
    #define Status int
    using namespace std;
    //顺序表数据结构
    typedef struct
    {
    	ElemType data[MaxSize];//顺序表元素
    	int length;            //顺序表当前长度
    }SqList;
    //***************************基本操作函数*******************************//
    //初始化顺序表函数,构造一个空的顺序表 
    Status InitList(SqList &L)
    {
    	memset(L.data,0,sizeof(L));//初始化数据为0
    	L.length=0;                //初始化长度为0
    	return 0;
    }
    //创建顺序表函数 初始化前n个数据
    bool CreatList(SqList &L,int n)
    {
    	if(n<0||n>MaxSize)false;//n非法
    	for(int i=1;i<n+1;i++)//L[0]作为哨兵
    	{
    		scanf("%d",&L.data[i]);
    		L.length++;
    	}
    	return true;
    }
    //插入函数 位置i插入数据 i及之后元素后移  1=<i<=length+1 
    bool InsertList(SqList &L,int i,ElemType e)
    {
    	if(i<1||i>L.length+1) //判断位置是否有效
         {
    		printf("位置无效!!!\n");
        	return false;
    	 }
    	if(L.length+1>=MaxSize)//判断存储空间是否已满
    	{
    		printf("当前存储空间已满!!!\n");
    		return false;
    	}
    	for(int j=L.length+1;j>=i;j--)//位置i及之后元素后移
    	{
    		L.data[j]=L.data[j-1];
    	}
    	L.data[i]=e;
    	L.length++;
    	return true;
    }
    //删除函数 删除位置i的元素 i之后的元素依次前移
    bool  ListDelete(SqList &L,int i)
    {
    	if(i<1||i>L.length)//判断位置是否有效
         {
    		printf("位置无效!!!\n");
        	return false;
    	 }
    	for(int j=i+1;j<=L.length;j++)//位置i之后元素依次前移覆盖
    	{
    		L.data[j-1]=L.data[j];
    	}
    	L.length--;
    	return true;
    }
    //查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
    int LocateElem(SqList L,ElemType e)
    {
     for(int i=1;i<L.length+1;i++)//从低位置查找
    	{
    		if(L.data[i]==e)
    			return i;
    	}
     return 0;
    }
    //********************************功能函数*****************************************//
    //输出功能函数 按位置从小到大输出顺序表所有元素
    void PrintList(SqList L)
    {
    	printf("当前顺序表所有元素:");
    	for(int i=1;i<L.length+1;i++)
    	{
    		printf("%d ",L.data[i]);
    	}
    	printf("\n");
    }
    //创建顺序表函数
    void Create(SqList &L)
    {
    	int n;bool flag;
    	printf("请输入要创建的顺序表长度(>1):");
    	scanf("%d",&n);
    	printf("请输入%d个数(空格隔开):",n);
    	flag=CreatList(L,n);
    	if(flag){
    		printf("创建成功!\n");
    		PrintList(L);
    	}
    	else printf("输入长度非法!\n");
    }
    //插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
    void Insert(SqList &L)
    {
      int place;ElemType e;bool flag;
      printf("请输入要插入的位置(从1开始)及元素:\n");
      scanf("%d%d",&place,&e);
      flag=InsertList(L,place,e);
      if(flag) 
      {
    	printf("插入成功!!!\n");
    	PrintList(L);
      }
    }
    //删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
    void Delete(SqList &L)
    {
      int place;bool flag;
      printf("请输入要删除的位置(从1开始):\n");
      scanf("%d",&place);
      flag=ListDelete(L,place);
      if(flag) 
      {
    	printf("删除成功!!!\n");
    	PrintList(L);
      }
    }
    //查找功能函数 调用LocateElem查找元素
    void Search(SqList L)
    {
      ElemType e;int flag;
      printf("请输入要查找的值:\n");
      scanf("%d",&e);
      flag=LocateElem(L,e);
      if(flag) 
      {
    	printf("该元素位置为:%d\n",flag);
      }
      else
    	  printf("未找到该元素!\n");
    }
    //直接插入排序 升序排序
    void InsertSort(SqList &L)
    {
    	int temp;int i,j;
    	for(int i=2;i<=L.length;i++)
    	{
    		if(L.data[i]<L.data[i-1])//比较有序表最后一个
    		{
    		
    			L.data[0]=L.data[i];//放入哨兵中
    			L.data[i]=L.data[i-1];
    			for(j=i-2;L.data[0]<L.data[j];j--)//比较后移
    			{
    				L.data[j+1]=L.data[j];
    			}
    			L.data[j+1]=L.data[0];//哨兵入列
    		}
    	}
    	PrintList(L);
    }
    //菜单
    void menu()
    {  
       printf("********1.创建            2.插入*********\n");
       printf("********3.删除            4.查找*********\n");
       printf("********5.直接插入排序    6.输出*********\n");
       printf("********7.退出\n");
    }
    int main()
    {
     SqList L;int choice;
     InitList(L);
     while(1)
     {
      menu();
      printf("请输入菜单序号:\n");
      scanf("%d",&choice);
      if(7==choice) break;
      switch(choice)
      {
      case 1:Create(L);break;
      case 2:Insert(L);break;
      case 3:Delete(L);break;
      case 4:Search(L);break;
      case 5:InsertSort(L);break;
      case 6:PrintList(L);break;
      default:printf("输入错误!!!\n");
      }
     }
     return 0;
    }

    结果截图:

    直接插入排序结果截图

    更多数据结构实现:数据结构严蔚敏版的实现(含全部代码)

    有问题请下方评论,转载请注明出处,并附有原文链接,谢谢!如有侵权,请及时联系。

    展开全文
  • 数据结构——C语言实现直接插入排序算法 一、基本思想        直接插入排序算法是在一个已经有序的记录上,将下一个待排序的数,有序的插入已排好序的记录中,这个过程一直持续...

    数据结构——C语言实现直接插入排序算法

    一、基本思想
           直接插入排序算法是在一个已经有序的记录上,将下一个待排序的数,有序的插入已排好序的记录中,这个过程一直持续到将所有待排数全部插入到有序记录中才停止。
    例如,如果将一组数:      2      5      3      7      4      3*
    用直接插入排序算法实现从小到大的排序,那么其过程如下所示:
    (2)    5        3      7      4      3*
    (2        5)    3      7      4      3*
    (2       3         5)  7      4       3*
    (2        3        5      7)  4       3*
    (2        3        4      5      7)    3*
    (2        3        3*     4     5       7)
           由上述过程我们可以看到两个3在比较时后面一个3*在排序之后仍然处于后面的位置,这就体现出了直接插入排序算法的稳定性
    二、C语言算法实现

    #include<stdio.h>
    void InsertSort(int a[],int length)  //从小到大排序
    {
    	int i,j,temp;
    	for(i=1;i<length;i++)//从数组的第二个值开始插入
    	{
    		if(a[i]<a[i-1])  //若第i位小于第i-1位
    		{
    			temp=a[i];  //将第i位暂放入temp中,这时可以想象为第i位为空
    			a[i]=a[i-1];  //将第i-1位后移一位到第i位中,这时可想象为第i-1位为空
    			for(j=i-2;a[j]>temp;j--)  //继续将temp中的值和第i-2位比较
    			{
    				a[j+1]=a[j];  //若第i-2位大于temp,则将第i-2位后移到第i-1位中
    			}
    				a[j+1]=temp;  //循环至第j位小于等于temp值时,则将temp值放在第j+1位中
    		}
    	}
    }
    int main()
    {
    	int i;
    	int r[6]={2,5,3,7,4,3};
    	InsertSort(r,6);
    	for(i=0;i<6;i++) //循环输出
    		printf("%d",r[i]);
    }
    

    运行结果为运行结果

           接下来我们来分析直接插入排序算法的复杂度:
           空间复杂度:在这个算法中所占用的额外空间只有temp,temp用来暂时存放待插入的数,所以空间复杂度为S(n)=O(1)
           时间复杂度:执行算法的时间耗费主要取决于数据的分布情况,最好的情况是所有记录是顺序,最坏情况是逆序。若待排序记录是随机的,则时间复杂度T(n)=O(n²)
           从算法的基本思想来看,直接插入排序算法简便且比较适用于记录数目少且基本有序的情况,当待排序数目较大时,其性能就不好。

    展开全文
  • 数据结构常见的八大排序算法直接插入排序 一、简述 直接插入排序是一种最简单的排序算法,直接插入的算法基本思想是:仅有一个元素的序列总是有序的,因此,对n个记录的序列,可从第二个元素开始直接到第n个...

                                       数据结构常见的八大排序算法之直接插入排序

     一、简述

            直接插入排序是一种最简单的排序算法,直接插入的算法基本思想是:仅有一个元素的序列总是有序的,因此,对n个记录的序列,可从第二个元素开始直接到第n个元素,逐个向有序序列中执行插入操作,从而得到n个元素按关键字有序的序列。一般来说,在含有j-1个元素的有序序列中插入一个元素的方法是:从第j-1个元素开始依次向前搜索应当插入的位置,并且在搜索插入位置的同时可以后移元素,这样当找到适当的位置时,即可插入元素。原理简述:顺序把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。

    二、步骤展示

    一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

    1. 从第一个元素开始,该元素可以认为已经被排序
    2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
    3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
    4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置后
    6. 重复步骤2~5

    三、时空复杂度

    最好的情况下,即待排序序列按关键字已经有序排列,每趟操作只需1次或者0次移动

    在最坏的情况下,即待排序序列按关键字逆排序序列,这时在第j趟操作中,为插入元素需要同前面的j个元素进行j次关键字比较,移动元素的次数为j+1次。此时有:总比较次数=n(n-1)/2次,总移动次数 = (n+2)(n-1)/2次

    平均情况下:即在第j趟操作中,插入记录大约需要时间同前面的j/2个元素进行关键字比较,移动记录次数j/2+1次

    直接插入排序的时间复杂度:O(n2)

    空间复杂度:O(1),没有分配内存。

    四、代码示例 

    public class InsortSort {
    
        public static void sort(int[] a) {
            for (int i = 1; i < a.length; i++) {
                int num = a[i];
                int j;
                for (j = i; j > 0 && num < a[j - 1]; j--) {
                    a[j] = a[j - 1];
                }
                a[j] = num;
            }
        }
    
        public static void main(String[] args) {
            int[] arr = {1, 3, 2, 5};
            for (int i : arr) {
                System.out.printf(" "+i);
            }
            System.out.println();
            sort(arr);
            for (int i : arr) {
                System.out.printf(" "+i);
            }
        }
    }

     

    展开全文
  • 1)直接插入排序: 理解:假设有n个数需要排序,则第一个数已经排序,剩下的n-1个数没有排序,现在需要将剩下的n-1个数,一个一个找到合适的位置插入进去。 第一趟排序结束:得到已经排序的数字的个数是2,再加上...

    插入排序:

    1)直接插入排序:

    理解:假设有n个数需要排序,则第一个数已经排序,剩下的n-1个数没有排序,现在需要将剩下的n-1个数,一个一个找到合适的位置插入进去。

    第一趟排序结束:得到已经排序的数字的个数是2,再加上剩下的n-2个数字

    例如:待排序序列(49,38,65,97,76,13,27,49),第一趟排序结束(38 49 65 97 76 13 27 49 )

    直接插入排序实现java代码如下:

    private static void ZSort(int a[]) {
            // TODO Auto-generated method stub
            /*
             * 直接插入排序算法 第一个元素已经排序,剩下n-1个没有排序, 一个一个比较 
             * 第一轮循环,执行n-1次 
             * 第二轮循环,当比他大后移,否则break
             */
            for (int i = 1; i < a.length; ++i) {
                int temp = a[i];
                int j = i - 1;
                for (; j >= 0; j--) {
    
                    if (temp < a[j]) {
                        a[j + 1] = a[j];
                    } else {
                        break;
                    }
                }
                a[j + 1] = temp;
            }
        }
    
        public static void main(String[] args) {
            int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
            ZSort(a);
            for (int i : a) {
                System.out.print(i + " ");
            }
        }

    (欢迎指正!再更新其他算法)

     

    展开全文
  • 直接插入排序通过键盘输入建立数组,再经过直接插入排序算法进行排序。在VS上X64编译通过。直接插入排序算法理论参考《算法导论》和张琨的《数据结构与算法分析(C++语言版)》
  • 一、代码 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define MAXSIZE 20 typedef int Status; void insertSort(int data[],int dataArrLenght); int main(int argc, ...
  • 对待排序的数组r[1..n]中的元素进行直接插入排序,得到一个有序的(从小到大)的数组r[1..n]。 算法思想: 1、设待排序的记录存放在数组r[1..n]中,r[1]是一个有序序列。 2、循环n-1次,每次使用顺序查找,查找...
  • 用函数实现直接插入排序,并输出每趟排序的结果. Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 每行输出一趟排序结果,数据之间用一个空格分隔 Sample Input 10 ...
  • 数据结构经典排序算法(一)——直接插入排序

    千次阅读 多人点赞 2020-12-18 23:20:47
    ②循环n-1次,每次使用循环查找,查找r[i] (i=2,…,n)在已排好的序列r[1…i-1]中的插入位置,然后将r[i]插入表长为i-1的有序序列r[1,…,i-1],直到将r[n]插入表长为n-1的有序序列r[1,…,n-1],最后得到一个表长为n...
  • 直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排序好的有序表中,从而得到一个新的、记录数增1的有序表。 java代码实现 /* 申明待排序数组 */ int[] a = {9,1,5,8,3,7,4,6,2}; ...
  • 插入排序算法 冒泡排序算法 折半/二分查找算法 插入排序: 一般称为直接插入排序,对于少量的元素排序,比较高效, 这里使用的顺序是正序,从小到大排列, 基本思想: 每一步将一个待排序的数据插入到前面已经排好...
  • 考研-数据结构-C-算法-数组-排序-直接插入   语言:C语言  对一维数组的直接插入排序,过程函数化。 什么是直接插入排序直接插入排序就是将某一个元素与顺序表中元素进行比较,然后插入到相应的位置,使...
  •     打算把查找排序算法交换着来看,先叙述直接插叙排序的...2 直接插入排序算法-流程阐述     给出手写的过程,字写有些难看????????????… 3 C++代码实现   &n
  • 数据结构(C语言版) 直接插入排序

    千次阅读 2019-08-02 22:35:57
    直接插入排序示例: 此处以数据2的排序为例,用i从左到右遍历到下标为5的位置,发现此处的值2小于前一位的值5 下标 0 1 2 3 4 5 6 数据 1 3 4 5 2 6 遍历位置 i 将2放到缓存0的位置,然后数据5...
  • 直接插入排序 基本思想 : 减治算法。把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 当插入第i(i>=1)个元素时,前面的array[0],...
  • 直接插入排序 概念 插入排序的基本思想是:在一个已排好序的记录子集的基础上,每一步将下一个待排序的记录有序地插入到已排好序的记录子集中,直到将所有待排记录全部插入为止。 插入类排序的整个过程就如同打扑克...
  • 直接插入排序是一种最简单的排序算法,因此又称简单插入排序 思想:第i趟排序将序列中的第i+1个元素 k(i+1)插入到一个已经生成的子序列中合适的位置,使得插入的序列仍然保持有序。(不理解的就想打扑克牌时候手...
  • 直接插入排序(Straight Insertion Sort):将一个数据插入到已经排序的数据中,从而得到一个新的有序数据。 目录1.直接插入排序2.折半插入排序3. 2路插入排序三种插入排序总结: 图例: 1.直接插入排序 代码实现: ...
  • 实验课题 用 C 描述课本的同学 有以下结构体构成的数组 struct StudentInfo { char ID[10]; char * name; float score; }StuInfo[12]= { {"0800301105, "JACK, 95}, {"0800201505, "LUN, 85}, {"0400820115, "MARY, ...
  • 插入排序之直接插入排序.cpp
  • 代码: #include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 #define OVERFLOW -1 #define OK 1 typedef int KeyType; typedef int InfoType; typedef struct { KeyType key; InfoType ...
  • 一、直接插入排序 1、直接插入排序简介 直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。主要有下面三...
  • 数据排序中的一种最基本的排序算法 比较次数个移动次数约为n的平凡除4, 时间复杂度约为0(n的平凡)
  • 包括:插入、希尔、冒泡、快速、选择、堆排序、归并(二路归并)、基数排序8个排序算法,完整的C语言代码,可点开直接运行,并附详细注释,方便理解和维护
  • 数据结构C语言版直接插入排序

    千次阅读 2018-10-22 22:39:49
    元素集合越接近有序,直接插入排序算法的时间效率越高 最优情况下:时间效率为O(n) 最差情况下:时间复杂度为O(n^2) 空间复杂度:O(1),它是一种稳定的排序算法 图示: 代码: Sort.h # pragma once #...
  • 插入排序代码实现 (1),插入排序的原理 插入排序(InsertionSorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次...
  • 直接插入排序时间复杂度如何算?可分为正序和倒序两种情况?需要计算过程和思路,
  • 原题:假设一组成绩的关键字序列如下(24.15.32.28.19.10.40)采用直接插入排序时,当插入记录19到有序表时,为找插入位置的需要比较次数为:答案4次 分析直接插入排序的过程: 原来: 24.15.32.28.19.10.40 1)首先...
  • 直接插入排序算法思想: 每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。 range: range是左闭右开 for i in range(5): print(i) 输出1 2 3 4 直接...
  • (1)掌握线性表的存储方式,并在此基础上实现典型的排序算法 (2)理解并掌握内部排序中几种常用算法的性能和适用场合 (3)理解并比较各种排序算法的时间复杂度和空间复杂度

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 157,262
精华内容 62,904
关键字:

数据结构直接插入排序算法的全部代码

数据结构 订阅