包含插入排序法的词条

by intanet.cn ca 算法 on 2024-03-19

本篇文章给大家谈谈插入排序法，以及对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

1、C语言的插入排序法是什么？
2、什么是插入排序，最好用实例说明
3、简单插入排序

C语言的插入排序法是什么？

插入排序(insertion sort)

如果需要对一个小型数组进行升序排列，那么可以选用插入排序，插入排序可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述。

可以把左手中的牌比做已经摸起的牌，即已经被排列好的牌，左手可以容纳的牌数的空间可以假想为和要摸的牌的总数相同；而在桌子上的那部分没摸的牌则是未被排序的牌，这二者的关系可以抽象为数组中已经被排序好的部分和未被排序好的部分。

一开始摸起的第一张牌不需要排序，可以认定其为已排序的牌。

如果用外层循环for来表示摸起的牌的话，则可以抽象为：

// 对象数组

// 桌子上的牌

int A[] = {5,1,3,6,2,4};

// 从数组的第二个元素开始抽取

for(int i = 1; i sizeof A/sizeof A[0]; ++i)

{

int pick = A[i]; // 被摸起的牌

int j = i - 1; // j记录已排序部分的最后一张牌的位置

. . .

}

而后摸起的排要根据排列策略和先前摸起的牌的点数的大小来确定其插入的合适位置，这里示范的排列策略是升序排列，摸起了这张牌后，便自右向左地和手中的牌进行比较。

把pick称作摸起的牌，如果pick比手中的牌小，则手中较大的那张牌就向右挪一位，pick再和下一张牌做隐野比较，如果下一张牌困郑仍然比pick大，那么那张牌便也向右移动一个位置，依此类推。

如果手中下一张和pick比较的牌比pick小，那么pick就被插入在了手中前一张牌移动后空下的位置；

或者手中所有的牌都比pick大，那么所有的牌就都向右移动过一个位置，所以pick最终被插入在了手中最左边的位置。

这个过程可以抽象为：

// 对象数组

// 桌子上的牌

int A[] = {5,1,3,6,2,4};

// 从数组的第二灶尺喊个元素开始抽取

for(int i = 1; i sizeof A/sizeof A[0]; ++i)

{

int pick = A[i]; // 被摸起的牌

int j = i - 1; // j记录已排序部分的最后一张牌的位置

// 如果循环了j+1次，即j = -1时还未找到比pick小的牌

// 那么pick就是最小的牌被插入在位置A[0]处

// A[j]是当前手中和pick进行比较的牌

while(j = 0 A[j] pick)

{

// 未找到可插入位置，则A[j]向后挪一位

A[j+1] = A[j];

// j减1继续向左定位手中下一张供和pick比较的牌--j;

}

// while结束后，j+1所表达的位置便是pick可以插入的位置

A[j+1] = pick;

}

// 对于有N个元素的数组A，采用插入排序法排序时，当外层循环进行了N-1次后排序完毕

什么是插入排序，最好用实例说明

插入排序1.直接插入排序原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序李清区元素都移动到有序区完成排序。要点：设立哨兵，作为临时存储和判断数组边界之用。实现：Void InsertSort(Node L[],int length){Int i,j;//分别为有序区和无序区指针for(i=1;ilength;i++)//逐步扩大有序区{j=i+1;if(L[j]L[i]){L[0]=L[j];//存储待排序元素数扰拍While(L[0]L[i])//查找在有序区中的插入位置，同时移动元素{L[i+1]=L[i];//移动i--;//查找}L[i+1]=L[0];//将元素插入}i=j-1;//还原有序区指针}}2.希尔排序原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。要点：增量的选择以及排序最终以1为增量进行排序结束。实现：Void shellSort(Node L[],int d){While(d=1)//直到增量缩小为1{Shell(L,d);d=d/2;//缩小增量}}Void Shell(Node L[],int d){Int i,j;For(i=d+1;ilength;i++){if(L[i]L[i-d]){L[0]=L[i];j=i-d;While(j0L[j]L[0]){L[j+d]=L[j];//移动j=j-d;//查找薯羡}L[j+d]=L[0];}}}

[img]