数据结构课程设计(内部排序算法比较 C语言)

排序算法比较c语言课程设计一、课程目标知识目标：1. 理解排序算法的基本概念和分类；2. 掌握冒泡排序、选择排序、插入排序等常见排序算法的实现原理和步骤；3. 了解不同排序算法的时间复杂度和空间复杂度分析；4. 学会使用C语言实现不同排序算法。

技能目标：1. 能够运用所学排序算法解决实际问题；2. 培养良好的编程习惯，编写结构清晰、可读性强的代码；3. 提高分析问题和解决问题的能力，具备一定的算法优化意识。

情感态度价值观目标：1. 培养学生对计算机科学的兴趣，激发学习热情；2. 培养学生的团队合作意识，提高沟通能力；3. 培养学生勇于面对挑战，克服困难的精神。

课程性质：本课程为C语言程序设计的一部分，重点在于让学生通过排序算法的学习，掌握C语言编程技巧，提高解决问题的能力。

学生特点：学生已经具备一定的C语言基础，了解基本的数据结构和算法，但对于排序算法的深入理解和应用尚有不足。

教学要求：注重理论与实践相结合，让学生在实践中掌握排序算法的原理和应用。

通过案例分析和编程实践，培养学生分析问题、解决问题的能力。

同时，关注学生的情感态度价值观培养，提高综合素质。

在教学过程中，将课程目标分解为具体的学习成果，以便进行教学设计和评估。

二、教学内容1. 排序算法基本概念：介绍排序的定义、排序算法的稳定性、内排序与外排序的分类。

2. 常见排序算法：- 冒泡排序：讲解其原理、实现步骤、时间复杂度和空间复杂度分析；- 选择排序：介绍其原理、实现步骤、时间复杂度和空间复杂度分析；- 插入排序：阐述其原理、实现步骤、时间复杂度和空间复杂度分析；- 快速排序：讲解其原理、实现步骤、时间复杂度和空间复杂度分析，以及优化方法。

3. 排序算法性能比较：分析各种排序算法的时间复杂度和空间复杂度，探讨不同场景下排序算法的适用性。

4. C语言实现排序算法：结合教材，编写冒泡排序、选择排序、插入排序和快速排序的C语言代码，并进行调试和优化。

(完整)数据结构(C语言版)实验报告 (内部排序算法比较)编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)数据结构(C语言版)实验报告 (内部排序算法比较)）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为(完整)数据结构(C语言版)实验报告 (内部排序算法比较)的全部内容。

《数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。

试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受.基本要求：(l)对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

（2)待排序表的表长不小于100000；其中的数据要用伪随机数程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

（3)最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。

数据测试：二．概要设计1.程序所需的抽象数据类型的定义：typedef int BOOL; //说明BOOL是int的别名typedef struct StudentData ｛ int num; //存放关键字}Data； typedef struct LinkList { int Length; //数组长度Data Record[MAXSIZE］; //用数组存放所有的随机数} LinkList int RandArray［MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum（) //随机生成函数void InitLinkList(LinkList* L） //初始化链表BOOL LT(int i, int j,int* CmpNum） //比较i和j 的大小void Display（LinkList* L） //显示输出函数void ShellSort（LinkList* L， int dlta[]， int t,int＊ CmpNum, int* ChgNum) //希尔排序void QuickSort (LinkList＊L，int* CmpNum, int＊ChgNum) //快速排序void HeapSort （LinkList* L, int* CmpNum, int＊ChgNum) //堆排序void BubbleSort(LinkList＊L，int* CmpNum, int＊ChgNum) //冒泡排序void SelSort（LinkList* L, int* CmpNum，int＊ChgNum）//选择排序void Compare(LinkList* L,int＊CmpNum，int* ChgNum) //比较所有排序2 .各程序模块之间的层次（调用）关系：二、详细设计typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型{int num； //定义关键字类型｝Data； //排序的记录数据类型定义typedef struct LinkList //记录线性表{int Length； //定义表长Data Record[MAXSIZE］; //表长记录最大值｝LinkList; //排序的记录线性表类型定义int RandArray[MAXSIZE］； //定义随机数组类型及最大值/＊＊*＊*＊＊**＊*＊****＊＊随机生成函数**＊＊*＊＊＊*＊＊＊＊＊＊*＊＊＊*/void RandomNum(){int i; srand（（int)time（NULL）)； //用伪随机数程序产生伪随机数for(i=0； i小于MAXSIZE； i++） RandArray[i］〈=(int）rand(）；返回；}/＊**＊＊＊*＊*＊*＊＊**＊*初始化链表＊＊**＊＊*＊＊＊*＊*＊***＊＊＊＊＊/void InitLinkList（LinkList＊ L） //初始化链表{int i；memset（L,0，sizeof(LinkList））；RandomNum();for(i=0； i小于〈MAXSIZE； i++)L—〉Record［i]。

数据结构课程设计—内部排序算法比较在计算机科学领域中，数据的排序是一项非常基础且重要的操作。

内部排序算法作为其中的关键部分，对于提高程序的运行效率和数据处理能力起着至关重要的作用。

本次课程设计将对几种常见的内部排序算法进行比较和分析，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。

冒泡排序是一种简单直观的排序算法。

它通过重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

这种算法的优点是易于理解和实现，但其效率较低，在处理大规模数据时性能不佳。

因为它在最坏情况下的时间复杂度为 O(n²)，平均时间复杂度也为O(n²)。

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，直到整个序列有序。

插入排序在数据量较小时表现较好，其平均时间复杂度和最坏情况时间复杂度也都是 O(n²)，但在某些情况下，它的性能可能会优于冒泡排序。

选择排序则是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

以此类推，直到全部待排序的数据元素排完。

选择排序的时间复杂度同样为O(n²)，但它在某些情况下的交换操作次数可能会少于冒泡排序和插入排序。

快速排序是一种分治的排序算法。

它首先选择一个基准元素，将数列分成两部分，一部分的元素都比基准小，另一部分的元素都比基准大，然后对这两部分分别进行快速排序。

快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n²)。

然而，在实际应用中，快速排序通常表现出色，是一种非常高效的排序算法。

归并排序也是一种分治算法，它将待排序序列分成若干个子序列，每个子序列有序，然后将子序列合并成一个有序序列。

`课题：内部排序算法比较…第一章问题描述排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。

比较的结果用一个直方图表示。

第二章系统分析界面的设计如图所示：!|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|~请选择操作方式：如上图所示该系统的功能有：（1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。

（2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。

（3）选择0 打印“谢谢使用！！”退出系统的使用！！、第三章系统设计（I）友好的人机界面设计：（如图所示）|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|：（）（II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（所示）|******************************||-------欢迎使用---------||-----（1）随机取数-------||-----（2）自行输入-------||-----（0）退出使用-------||******************************|；请选择操作方式：（用户在此输入操作方式）（）（III）系统采用定义结构体数组来存储数据。

数据结构课程设计报告题目：各种内排序性能比较学生姓名：学号：班级：指导教师：2011-6-13目录1、需求分析说明 (2)1.1所需完成的任务及要求1.2程序实现的功能2、总体设计 (3)2.1 总体设计说明2.2 总体流程图2.3各主程序详细流程图3、详细设计 (7)3.1使用的算法思想3.2各个算法的效率简析4、实现部分 (8)4.1程序算法的代码5、程序测试 (15)5.1程序运行的主界面5.2 各算法运行界面6、总结 (18)1、需求分析说明排序是数据处理中经常遇到的一种重要操作。

然而排序的算法有很多，各有其优缺点和使用场合。

本程序的设计的主要目的是通过比较各种内部排序（包括：插入法排序、起泡法、选择法、快速法、合并法排序）的时间复杂度，即元素比较次数和移动次数，来分析各种算法优缺点和适合排列何种序列。

达到在实际应用中选择合适的方法消耗最短的时间完成排序。

1.1所需完成的任务及要求任务：1)用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；2)输入的数据形式为任何一个正整数，大小不限。

要求：排序后的数组是从小到大的；1.2程序实现的功能（1）使用随机函数实现数组初始化，生成多组元素个数不同的数组；（2）用列表打印出每种排序下的各趟排序结果；（3）打印使用各种排序算法以后元素比较和交换的次数；（4）设计合理的打印列表来打印。

2、总体设计（从总体上说明该题目的框架，用文字和图表说明）2.1 总体设计说明采用插入气泡，选择，快速，合并的方法实现各种排序算法，并且在实现过程中插入适当变量来实现计数元素交换次数和比较次数的统计。

对于每一趟比较之后元素顺序以及最后的结果使用单独的函数来实现，形成单独的一个模块；2.2 总体流程图2.3 各主程序详细流程图①主函数流程图：3、详细设计3.1 使用的算法思想（1）对主界面的menu菜单，在主函数里面用switch语句调用各个模块的功能调用；（2）在插入法时，其算法思想是：将第一个元素作为单独的一个数组独立出来，对剩下的元素，逐个与前面的数组从后往前进行比较，一旦发现当前的元素大于或是等于前面已经排序好的元素中某个元素，则在这个元素之后插入即可；（3）在起泡法时，其算法思想是：将待排序的数组从后往前，依次比较相邻的两个元素，如果发现逆序则交换序列，使得数值、比较小的元素逐渐往前排列，在这个算法时要用flag作为标记位，用来判断元素是否交换，用以减少不必要的交换次数；（4）对于选择法，其排序思想是:从第一个元素开始，并且标记当前元素的位置，比较后面所有的元素，找到其中最小的元素，也标记当前元素的位置，然后把两个标记位的元素进行交换，前面的标记位不断地向后移动，直到最后一个元素的位置，则排序完成；（5）对于快速法，其算法思想是：一般取数组中的第一个元素为基准，通过一趟排序将待排序元素分为左右两个子序列，左子序列的所有元素都小于或等于右子序列的所有元素，然后将左右两个序列按照与此相同的原理进行排序，直至整个序列有序为止，排序完成。

****课程设计报告题目：各种内部排序性能比较学生姓名：彭伟奇学号： 1021112417班级：10211124指导教师：高永平2012年6 月15 日一、课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

二、实验要求任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；输入的数据形式为任何一个正整数，大小不限。

输出的形式：数字大小逐个递增的数列。

功能要求：给出多组不同元素个数的输入数据(可考虑用随机函数生成整数，而不用人工输入)，并用列表打印出每种排序下的各趟排序结果。

每个排序法结束时应打印出其元素比较的次数和交换的次数。

此程序需将结果用列表打印，一定要将其打印结果排列好。

三、程序源代码#include "stdlib.h"#include"stdio.h"#include"time.h"#define MAXSIZE 200typedef int KeyType;typedef struct //定义存储记录关键字及其他信息的结构体{ KeyType key;char other;}RedType;typedef struct //定义存储所有记录的结构体{ RedType r[MAXSIZE+1];int length;}SqList;typedef struct{int move; /*记录数据移动次数*/int comp; /*记录数据比较次数*/}Recode;int dlta[5]={31,15,7,3,1}; //初始化希尔排序的增量序列int num[10]={0}; //记录每个排序方法的移动次数和比较次数int flag=0; //标记变量//利用产生的随即数模拟用户输入的数据class sort{public:void select_sort(SqList L);void Zhijie(SqList L) ;void ShellInsert(SqList *L,int dk,Recode *r);void ShellSort(SqList L,int dlta[],int t) ;void Maopao(SqList L);int Partition(SqList *L,int low,int high,Recode *r); void QuickSort(SqList L) ;protected:int dk,dlta[5],t,low,high;};void create(SqList *L,int length){ int i;srand(time(0));L->length=length;for(i=1;i<=L->length;i++){L->r[i].key=rand()%1000;L->r[i].other=rand()%5;}}/*输出元素*/void visit(SqList L){int i;printf("\n");for(i=1;i<=L.length;i++)printf("%4d%2c",L.r[i].key,L.r[i].other);printf("\n");}/*简单选择排序*/void select_sort(SqList L){ Recode r;p =0;r.move =0;int i,j,k;RedType t;for (i=1;i<L.length;i++){ j=i;for (k=i+1;k<=L.length;k++){ p++;if (L.r[j].key>L.r[k].key){j=k;}}if (i!=j){t=L.r[j];L.r[j]=L.r[i];L.r[i]=t;r.move =r.move +3;}}if(!flag){ printf("本次随机数据排序的移动次数为:");printf("%d\n",r.move);printf("本次随机数据排序的比较次数为:");printf("%d\n",p);printf("简单选择排序后的结果：");visit(L);}else{num[0]=r.move;num[1]=p;}}//直接插入排序void Zhijie(SqList L){ Recode r;p =0;r.move =0;int j;for(int i=2;i<=L.length;++i){ p ++;if(L.r[i].key<L.r[i-1].key){L.r[0]=L.r[i]; //复制为哨兵L.r[i]=L.r[i-1];r.move=r.move +2;for(j=i-2;L.r[0].key < L.r[j].key;--j){L.r[j+1]=L.r[j]; //记录后移r.move ++;p ++;}L.r[j+1]=L.r[0]; //插入到正确位置r.move ++;}}if(!flag){printf("本次随机数据排序的移动次数为:");printf("%d\n",r.move);printf("本次随机数据排序的比较次数为:");printf("%d\n",p);printf("直接插入排序后的结果：");visit(L);}else{num[2]=r.move;num[3]=p;}}void ShellInsert(SqList *L,int dk,Recode *r){ int i,j;for(i=dk+1;i<=L->length ;++i){ r->comp ++;if(L->r[i].key<L->r[i-1].key){ L->r[0]=L->r[i]; //暂存r->move ++;for(j=i-dk;j>0&&(L->r[0].key < L->r[j].key);j-=dk){ L->r[j+dk]=L->r[j]; //记录后移r->move ++;r->comp ++;}L->r[j+dk]=L->r[0]; //插入到正确位置r->move ++;}}}void ShellSort(SqList L,int dlta[],int t){ //按增量序列dlta[0..t-1]对顺序表L作希尔排序。

课程设计排序算法c语言一、教学目标本课程的目标是让学生掌握排序算法的原理和实现，能够运用C语言编写相应的程序。

具体分为三个部分：1.知识目标：使学生了解常见的排序算法，如冒泡排序、选择排序、插入排序等，理解它们的原理和特点。

2.技能目标：培养学生能够使用C语言实现这些排序算法，并能够分析它们的时空复杂度。

3.情感态度价值观目标：培养学生对编程的兴趣，增强他们解决问题的能力，培养他们的团队合作意识。

二、教学内容本课程的教学内容主要包括：1.排序算法的基本概念和分类。

2.冒泡排序、选择排序、插入排序等常见排序算法的原理和实现。

3.C语言编程基础，如数据类型、控制结构、函数等。

4.排序算法的时空复杂度分析。

5.编程实践和团队协作。

三、教学方法为了达到本课程的教学目标，将采用以下教学方法：1.讲授法：讲解排序算法的基本概念、原理和实现。

2.讨论法：引导学生讨论排序算法的优缺点，提高他们的思考能力。

3.案例分析法：通过分析实际案例，使学生更好地理解排序算法的应用。

4.实验法：让学生动手编写C语言程序，实现排序算法，提高他们的实践能力。

四、教学资源为了支持本课程的教学内容和教学方法，将准备以下教学资源：1.教材：《C语言程序设计》。

2.参考书：《算法导论》、《数据结构与算法分析》。

3.多媒体资料：PPT课件、教学视频等。

4.实验设备：计算机、网络等。

五、教学评估为了全面、客观、公正地评估学生的学习成果，将采用以下评估方式：1.平时表现：通过课堂参与、提问、小组讨论等环节，评估学生的学习态度和课堂表现。

2.作业：布置与课程内容相关的编程作业，评估学生的编程能力和对知识的理解程度。

3.考试：定期进行理论考试和实践考试，评估学生对排序算法的掌握程度。

4.团队项目：学生进行团队合作项目，评估他们的团队协作能力和问题解决能力。

六、教学安排教学进度将按照以下计划进行：1.授课时间：共计16周，每周2课时。

2.授课地点：计算机实验室。

实验报告3实验名称：数据结构与软件设计实习题目：内部排序算法比较专业：生物信息学班级：01 姓名：学号：实验日期：2010.07.24一、实验目的：比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序；二、实验要求：待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；对结果做简单的分析，包括各组数据得出结果的解释；设计程序用顺序存储。

三、实验内容对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。

将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。

四、实验编程结果或过程：1. 数据定义typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length;}SqList;2. 函数如下，代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)//希尔排序void ShellSort(SqList &L,int dlta[ ])3. 运行测试结果，运行结果无误，如下图语速个数为20元素个数为100错误调试无。

排序算法比较专业班级：XXX学号：XXX姓名：XXX指导教师：XXX课程设计时间：XXX计算机科学与技术专业数据结构课程设计任务书学生姓名XXX 专业班级XXX 学号XXX 题目排序算法比较课题性质工程设计课题来源XXX指导教师XXX同组姓名XXX主要内容1.输入一个大于0的整数，生成一组无序数列2.设计冒泡排序，快速排序，插入排序，选择排序，希尔排序，归并排序的子函数，对生成的无序数列进行排序3.设计主函数对各排序算法子函数进行调用4.输出各排序算法排序的移动次数和时间任务要求1．研究各种排序算法的数据存储方式2．实现各种排序的主要算法3．分析算法的运行效率4．具有良好的运行界面5．算法具有良好的健壮性6．按要求撰写课程设计报告和设计总结。

参考文献1．《数据结构（C语言版）》，严蔚敏、吴伟民，清华大学出版社，1997. 2．《Visual C++实用教程（第一版）》，张荣梅、梁晓林，冶金工业出版社，2004.审查意见指导教师签字：教研室主任签字： 年 月 日1 需求分析对一组无序数运用各种算法进行排序，并返回排序移动次数和运行时间2 概要设计3 运行环境（软、硬件环境）1) 硬件：PC 机main 生成无序数组进行冒泡排序 进行希尔排序 进行选择排序 进行快速排序 进行归并排序输出移动次数和时间2)操作系统：Windows 2000/XP/20033)编译环境：Visual C++6.04 开发工具和编程语言开发工具：VISCALL c++6.0；编程语言：C语言。

5 详细设计1.声明数据类型2.编写addlist函数生成随机无序数组3.编写qipao函数实现冒泡排序，并输出排序移动次数和时间4.编写insertSort函数实现插入排序，并输出排序移动次数和时间5.编写SelectSort函数实现选择排序，并输出排序移动次数和时间6.编写xierSort函数实现希尔排序，并输出排序移动次数和时间7.编写MergeSort函数实现归并排序，并输出排序移动次数和时间8.编写Main函数对子函数进行调用6 调试分析在调试过程中出现的一些问题：1、输入语句中没有加取地址符号&2、误把取地址运算符&当作逻辑与&&3、误把赋值=当恒等==4、条件语句（if）后误加分号5、循环语句中改变了循环变量6、作为输出结果的变量没有赋初值7.中英文输入切换导致符号错误7 测试结果8 参考文献[1]谭浩强，C程序设计题解与上机指导（第3版），清华大学出版社，2005.7.[2][美]Harvey M. Deitel，Paul J. Deitel 著，聂雪军，贺军译，C程序设计经典教程（第4版），清华大学出版社，2006。

内部排序算法比较1、课程设计的目的本课程设计为了更好的了解和认识数据结构常用的内部排序算法。

排序对于数据结构的管理来说是至关重要的，所以熟悉掌握和深入了解这些常用的经典内部排序算法是有必要的。

2、课程设计的要求1. 掌握常用的排序方法和各种排序方法的特点。

2.熟悉排序的基本概念。

3、课程设计的内容3.1需求分析编制一个演示内部排序算法比较的程序。

可对冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序和堆排序进行比较。

3.2概要设计（1）冒泡排序基本思想是：设数组a中存放了n 个数据元素，循环进行n-1次如下的排序过程：第一次时，依次比较相邻两个数据元素a[i]和a[i+1].key(i=0,1,2,3...,n-2).若为逆序，则交换两个数据元素，否则不交换，这样，当作完n-1次比较后数值最大的数据元素将比放置在a[n-1]中。

第二次时，数据元素个数减1，即数据元素个数为n-1，操作方法与第一次类似，这样，n个数据元素集合中数值次大的数据元素将被放置在a[n-2]中。

当第n-1次排序结束时，n个数据元素集合中次小的数据元素将被放置在a[1]中，而a[0]中放置了最小的数据元素。

冒泡排序算法的空间复杂度为o(n2)。

（2）直接插入排序基本思想是:顺序地把待插入的数据元素按其关键字的大小插入到已排序数据元素子集合的适当位置.子集合的数据元素个数从只有一个数据元素开始逐次增大,当子集合最终与集合大小相同时排序完毕.设待排序的N个数据元素存放在数组A中,初始时子集合a[0]以排好序.第一次循环准备把数据元素a[1]插入到以排好序的子集合中,这只需比较a[0].key和a[1].key,若a[0].key<=a[1].key,则说明序列已有序,否则,将a[1]插入到a[0]之前,这样子集合的大小增大为2;第二次循环是把数据元素a[2]插入到以排好序的子集合中,这需要先比较a[2].key和a[1].key,已确定是否需要把a[2]插到a[1]之前,然后比较a[2].key和a[0].key,以确定是否需要把a[2]插入到a[0]之前;这样的循环过程一直进行到a[n-1]插入完为止.这时,数据元素集合a[0],a[1],a[2],...,a[n-1]就全部排好了序。