做网站莱芜,ftp跟网络连接Wordpress,wordpress支持的邮箱,跨境电商app有哪些直接插入排序
插入排序算法是所有排序方法中最简单的一种算法#xff0c;其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中#xff0c;最终得到的序列就是已经排序好的数据。
直接插入排序是插入排序算法中的一种#xff0c;采用的方法是#xff1a;在…直接插入排序
插入排序算法是所有排序方法中最简单的一种算法其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中最终得到的序列就是已经排序好的数据。
直接插入排序是插入排序算法中的一种采用的方法是在添加新的记录时使用顺序查找的方式找到其要插入的位置然后将新记录插入。 很多初学者所说的插入排序实际上指的就是直接插入排序算法插入排序算法还包括折半插入排序、2-路插入排序表插入排序和希尔排序等。 例如采用直接插入排序算法将无序表 { 3 , 1 , 7 , 5 , 2 , 4 , 9 , 6 } \{3,1,7,5,2,4,9,6\} {3,1,7,5,2,4,9,6}进行升序排序的过程为 首先考虑记录3由于插入排序刚开始有序表中没有任何记录所以3可以直接添加到有序表中则有序表和无序表可以如图1所示 向有序表中插入记录1时同有序表中记录3进行比较13所以插入到记录3的左侧如图2所示 向有序表插入记录7时同有序表中记录3进行比较37所以插入到记录3的右侧如图3所示 图 3 直接插入排序3 向有序表中插入记录5时同有序表中记录7进行比较57同时53所以插入到3和7中间如图4所示 向有序表插入记录 2 时同有序表中记录 7进行比较 27 再同 5 3 1 分别进行比较最终确定 2 位于 1 和 3 中间如图 5 所示 图 5 直接插入排序5 照此规律依次将无序表中的记录 4 9 和 6 插入到有序表中如图 6 所示 图 6 依次插入记录49和6
直接插入排序的具体代码实现为
#include iostream
using namespace std;
//自定义的输出函数
void print(int a[], int n ,int i){cout i : ;for(int j0; j8; j){cout a[j];}cout endl;
}
//直接插入排序函数
void InsertSort(int a[], int n)
{for(int i 1; in; i){if(a[i] a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入反之需要找到适当的插入位置后在插入。int j i-1;int x a[i];while(j-1 x a[j]){ //采用顺序查找方式找到插入的位置在查找的同时将数组中的元素进行后移操作给插入元素腾出空间a[j1] a[j];j--;}a[j1] x; //插入到正确位置}print(a,n,i);//打印每次排序后的结果}
}int main(){int a[8] {3,1,7,5,2,4,9,6};InsertSort(a,8);return 0;
}运行结果为
1: 13752496
2: 13752496
3: 13572496
4: 12357496
5: 12345796
6: 12345796
7: 12345679直接插入排序算法本身比较简洁容易实现该算法的时间复杂度为O(n^2)。
折半插入排序
它是在直接插入排序的基础上的一种改进因为在查找插入位置时没索要查找的序列一定是有序序列所以我们利用折半二分的思想来优化查找的效率。
算法步骤
设待排序的记录存放在数据arr[n]中 arr[1]是一个有序序列循环n-1次每次使用折半查找查找arr[i]在已排好序列的序列中插入位置然后将arr[i]插入表长为i-1的有序序列直到将arr[n]插入有序序列中。
该算法的具体代码实现为
#include iostream
using namespace std;
//自定义的输出函数
void print(int a[], int n ,int i){cout i : ;for(int j0; j8; j){cout a[j];}cout endl;
}
void BInsertSort(int a[],int size){int i,j,low 0,high 0,mid;int temp 0;for (i1; isize; i) {low0;highi-1;tempa[i];//采用折半查找法判断插入位置最终变量 low 表示插入位置while (lowhigh) {mid(lowhigh)/2;if (a[mid]temp) {highmid-1;}else{lowmid1;}}//有序表中插入位置后的元素统一后移for (ji; jlow; j--) {a[j]a[j-1];}a[low]temp;//插入元素print(a, 8, i);}}int main(){int a[8] {3,1,7,5,2,4,9,6};BInsertSort(a,8);return 0;
}运行结果为
1:13752496
2:13752496
3:13572496
4:12357496
5:12345796
6:12345796
7:12345679折半插入排序算法相比较于直接插入排序算法只是减少了关键字间的比较次数而记录的移动次数没有进行优化所以该算法的时间复杂度仍是 O(n^2)。
2路插入排序
2-路插入排序算法是在折半插入排序的基础上对其进行改进减少其在排序过程中移动记录的次数从而提高效率。
具体实现思路为另外设置一个同存储记录的数组大小相同的数组d理解成一个环状数组将无序表中第一个记录添加进d[0]的位置上然后从无序表中第二个记录开始同d[0]作比较如果该值比d[0]大则添加到其右侧反之添加到其左侧。
使用2-路插入排序算法对无序表{3,1,7,5,2,4,9,6}排序的过程如下 将记录3添加到数组d中 然后将1插入到数组d中如下图所示 将记录7插入到数组d中如下图所示 将记录 5插入到数组 d 中由于其比 7小但是比 3 大所以需要移动 7 的位置然后将 5 插入如下图所示 将记录2插入到数组d中由于比1大比3小所以需要移动3、7、5的位置然后将2插入如下图所示 将记录4插入到数组d中需要移动5和7的位置如下图所示 将记录 9 插入到数组 d 中如下图所示 将记录6插入到数组d中如下图所示
最终存储在原数组时从d[7]开始依次存储。
2-路插入排序算法的具体实现代码为
#include iostream
using namespace std;
void insert(int arr[], int temp[], int n)
{int i,first,final,k;first final 0;//分别记录temp数组中最大值和最小值的位置temp[0] arr[0];for (i 1; i n; i ){// 待插入元素比最小的元素小if (arr[i] temp[first]){first (first - 1 n) % n;temp[first] arr[i];}// 待插入元素比最大元素大else if (arr[i] temp[final]){final (final 1 n) % n;temp[final] arr[i];}// 插入元素比最小大比最大小else {k (final 1 n) % n;//当插入值比当前值小时需要移动当前值的位置while (temp[((k - 1) n) % n] arr[i]) {temp[(k n) % n] temp[(k - 1 n) % n];k (k - 1 n) % n;}//插入该值temp[(k n) % n] arr[i];//因为最大值的位置改变所以需要实时更新final的位置final (final 1 n) % n;}}// 将排序记录复制到原来的顺序表里for (k 0; k n; k ) {arr[k] temp[(first k) % n];}
}int main()
{int a[8] {3,1,7,5,2,4,9,6};int temp[8];insert(a,temp,8);for (int i 0; i 8; i ){cout a[i] ;}return 0;
}运行结果为
1 2 3 4 5 6 7 92-路插入排序算法相比于折半插入排序只是减少了移动记录的次数没有根本上避免所以其时间复杂度仍为O(n^2)。
表插入排序
表插入排序即使用链表的存储结构对数据进行插入排序。在对记录按照其关键字进行排序的过程中不需要移动记录的存储位置只需要更改结点间指针的指向。
链表的存储结构用代码表示为
#define SIZE 100
typedef struct {int rc;//记录项int next;//指针项由于在数组中所以只需要记录下一个结点所在数组位置的下标即可。
}SLNode;
typedef struct {SLNode r[SIZE];//存储记录的链表int length;//记录当前链表长度
}SLinkListType;
在使用数组结构表示的链表中设定数组下标为 0 的结点作为链表的表头结点并令其关键字取最大整数。则表插入排序的具体实现过程是首先将链表中数组下标为 1 的结点和表头结点构成一个循环链表然后将后序的所有结点按照其存储的关键字的大小依次插入到循环链表中。
例如将无序表{4938761327}用表插入排序的方式进行排序其过程为 首先使存储 49 的结点与表头结点构成一个初始的循环链表完成对链表的初始化如下表所示 然后将以 38 为关键字的记录插入到循环链表中只需要更改其链表的 next 指针即可插入后的链表为 再将以 76 为关键字的结点插入到循环链表中插入后的链表为: 再将以 13 为关键字的结点插入到循环链表中插入后的链表为 最后将以 27 为关键字的结点插入到循环链表中插入后的链表为 最终形成的循环链表为
从表插入排序的实现过程上分析与直接插入排序相比只是避免了移动记录的过程修改各记录结点中的指针域即可而插入过程中同其它关键字的比较次数并没有改变所以表插入排序算法的时间复杂度仍是 O(n2) 。
对链表进行再加工
在表插入排序算法求得的有序表是用链表表示的也就注定其只能进行顺序查找。而如果想用折半查找的算法就需要对链表进行再加工即对链表中的记录进行重新排列具体做法为遍历链表将链表中第 i 个结点移动至数组的第 i 个下标位置中。 例如上表是已经构建好的链表对其进行再加工的过程为 首先通过其表头结点得知记录中关键字最小的是数组下标为 4 的关键字 13 而 13 应该放在数组下标为 1 的位置所以需要同下标为 1 中存放的关键字进行调换。但是为了后期能够找到 49 将 13 的 next 域指向 49 所在的位置改变之前需要保存原来的值这里用 q 指针表示如下表所示 然后通过 q 指针找到原本 13 指向的下一位关键字 27 同时 q 指针指向下标为 2 的关键字 38 由于 27 应该移至下标为 2 的位置所以同关键字 38 交换同时改变关键字 27 的 next 域如下表所示 之后再通过 q 指针找到下一位关键字时发现所指位置为下标 2 而之前已经经过了 2 次移动所以可以判定此时数组中存放的已经不是要找的所以需要通过下标为 2 中的 next 域继续寻找找到下标为 5 的位置即关键字 38 由于下标 5 远远大于 2 可以判断 38 即为要找的值所以同下标为 3 的记录交换位置还要更改其 next 域同时将 q 指针指向下标为 1 的位置如下表所示 然后通过 q 指针找到下一位关键字由于其指向位置的下标 1 中的记录已经发生移动所以通过 next 域找到关键字 49 发现它的位置不用改变同样当通过关键字 49 的 next 域找到下标为 3 的位置还是需要通过其 next 域找到关键字 76 它的位置也不用改变。
重新排列的具体代码实现为
#include iostream
using namespace std;
#define SIZE 6
typedef struct {int rc;//记录项int next;//指针项由于在数组中所以只需要记录下一个结点所在数组位置的下标即可。
}SLNode;
typedef struct {SLNode r[SIZE];//存储记录的链表int length;//记录当前链表长度
}SLinkListType;
//重新排列函数
void Arrange(SLinkListType *SL){//令 p 指向当前要排列的记录int pSL-r[0].next;for (int i1; iSL-length; i) {//如果条件成立证明原来的数据已经移动需要通过不断找 next 域找到其真正的位置while (pi) {pSL-r[p].next;}//找到之后令 q 指针指向其链表的下一个记录所在的位置int qSL-r[p].next;//条件成立证明需要同下标为 i 的记录进行位置交换if (p!i) {SLNode t;tSL-r[p];SL-r[p]SL-r[i];SL-r[i]t;//交换完成后该变 next 的值便于后期遍历SL-r[i].nextp;}//最后令 p 指向下一条记录pq;}
}int main(int argc, const char * argv[]) {SLinkListType *SL(SLinkListType*)malloc(sizeof(SLinkListType));SL-length6;SL-r[0].rc0;SL-r[0].next4;SL-r[1].rc49;SL-r[1].next3;SL-r[2].rc38;SL-r[2].next1;SL-r[3].rc76;SL-r[3].next0;SL-r[4].rc13;SL-r[4].next5;SL-r[5].rc27;SL-r[5].next2;Arrange(SL);for (int i1; i6; i) {cout SL-r[i].rc ;}return 0;
}运行结果为:
13 27 38 49 76
希尔排序
希尔排序又称“缩小增量排序”也是插入排序的一种但是同前面几种排序算法比较来看希尔排序在时间效率上有很大的改进。
在使用直接插入排序算法时如果表中的记录只有个别的是无序的多数保持有序这种情况下算法的效率也会比较高除此之外如果需要排序的记录总量很少该算法的效率同样会很高。希尔排序就是从这两点出发对算法进行改进得到的排序算法。 希尔排序的具体实现思路是先将整个记录表分割成若干部分分别进行直接插入排序然后再对整个记录表进行一次直接插入排序。 例如无序表{4938659776132749554}进行希尔排序的过程为
首先对{4913}{3827}{6549}{9755}{764}分别进行直接插入排序如果需要调换位置也只是互换存储位置如下图所示 上图中两两进行比较例如49和13进行比较1349所以交换存储位置。 通过一次排序无序表中的记录已基本有序此时还可以再进行一次分割如下图所示 经过两次分割无序表中已基本有序此时对整张表进行一次直接插入排序只需要做少量的比较和插入操作即可最终希尔排序的结果为 希尔排序的过程中对于分割的每个子表其各自包含的记录在原表中并不是相互挨着的而是相互之间相隔着某个固定的常数。例如上例中第一次排序时子表中的记录分割的常量为 5第二次排序时为3。
通过此种方式对于关键字的值较小的记录其前移的过程不是一步一步的而是跳跃性的前移并且在最后一次对整表进行插入排序时减少了比较和排序的次数。 一般在记录的数量多的情况下希尔排序的排序效率较直接插入排序高。 希尔排序的具体代码实现
#include iostream
using namespace std;
#define SIZE 15
typedef struct {int key; //关键字的值
}SLNode;
typedef struct {SLNode r[SIZE];//存储记录的数组int length;//记录数组中记录的数量
}SqList;
//希尔排序的实现函数其中 dk 表示增值量
void ShellInsert(SqList * L,int dk){//从 dk1 个记录起每间隔 dk 个记录就调取一个进行直接插入排序算法for (int idk1; iL-length; i) {//如果新调取的关键字的值比子表中最后一个记录的关键字小说明需要将该值调换位置if (L-r[i].keyL-r[i-dk].key) {int j;//记录表中使用位置下标为 0 的空间存储需要调换位置的记录的值L-r[0]L-r[i];//做直接插入排序如果下标为 0 的关键字比下标为 j 的关键字小则向后一行下标为 j 的值为新插入的记录腾出空间。for (ji-dk; j0 (L-r[0].keyL-r[j].key); j-dk){L-r[jdk]L-r[j];}//跳出循环后将新的记录值插入到腾出的空间中即完成了一次直接插入排序L-r[jdk]L-r[0];}}
}
//希尔排序通过调用不同的增量值记录实现对多个子表分别进行直接插入排序
void ShellSort(SqList * L,int dlta[],int t){for (int k0; kt; k) {ShellInsert(L, dlta[k]);}
}
int main(int argc, const char * argv[]) {int dlta[3]{5,3,1};//用数组来存储增量值例如 5 代表每间隔5个记录组成一个子表1表示每间隔一个也就是最后一次对整张表的直接插入排序SqList *L(SqList*)malloc(sizeof(SqList));L-r[1].key49;L-r[2].key38;L-r[3].key64;L-r[4].key97;L-r[5].key76;L-r[6].key13;L-r[7].key27;L-r[8].key49;L-r[9].key55;L-r[10].key4;L-length10;//调用希尔排序算法ShellSort(L, dlta, 3);//输出语句for (int i1; i10; i) {cout L-r[i].key ;}return 0;
}运行结果
4 13 27 38 49 49 55 64 76 97提示经过大量的研究表明所选取的增量值最好是没有除 1 之外的公因子同时整个增量数组中最后一个增量值必须等于 1 因为最后必须对整张表做一次直接插入排序算法。
