数据结构：排序（1）|| 插入排序

vlambda
2021-05-12

数据结构：排序（1）|| 插入排序

直接插入排序对应顺序查找

逐个比较，挨个排序，一个一个地扩张有序列

特性：是稳定排序，随机访问

时间复杂度：O(n^2)

由于该算法非常好理解，就不再细讲辽

折半插入排序对应二分查找

通过二分查找的方式去找到待插入位置

void BInsertSort(Sqlist &L){ //对顺序表L作折半插入排序 for (int i = 2; i <= L.length(); i++) { L[0] = L[i]; //暂存 low = 1; high = i - 1; while (low <= high) { m = (low + high) / 2; if (L[0] < L[m]) high = m - 1; else low = m + 1; } //循环中进行二分修改指针 for (int j = i - 1; i >= high + 1; j--) L[j + 1] = L[j]; L[high + 1] = L[0]; //后移，然后插入 }}

特性：采用二分查找去定位，较快一点

时间复杂度：O(n^2)

2-路插入排序在折半排序基础上再改进

换取时间往往需要使用额外空间。

2-路插入排序的目的是减少排序过程中移动记录的次数

数据结构：排序（1）|| 插入排序

通过增设了两个指针并开了一个新数组的方式，一定程度上减少了数据的移动次数。读取时，从first读到final即可得到有序序列。

前面的方法都无法避免移动序列，这是由于其顺序存储的存储结构导致的，若换用表的存储结构就可以避免移动序列，当然，牺牲了一部分的空间。

👇👇

表插入排序

表插入排序，就具备了指针空间，通过改变指针间接地改变顺序，这一点应该并不陌生。

特性：移动指针但无法随机访问

时间复杂度：O(n^2)

#define SIZE 100typedef struct{ RcdType rc; // 记录项 int next; //指针项}SLNode;typedef struct{ SLNode r[SIZE]; int length;}SLinkListType;

0号单元为表头结点，并设表头结点的关键字取最大整数MAXINT，表头结点用于记录起点位置，相当于head

数据结构：排序（1）|| 插入排序

通过顺序查找-->找到待插入位置-->插入-->修改位于该排序位后的值

若想重排静态链表数组，使其按照顺序排列，可以依照顺序逐个交换。交换后next值应该进行交换，换成“你从哪里被换来的”，这也就是括号中数字的意思，保证在被交换元素被访问到时可以方便的找回换到哪里去了。

数据结构：排序（1）|| 插入排序

这样我们就更换了原始的数据，使其静态排列，代码较简单，这里略过。

希尔排序，缩小增量排序

基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。

希尔排序先在宏观上使得序列基本有序，再对基本有序作基本有序阿巴阿巴，不断缩小基本有序序列的长度，最后长度缩到1都基本有序，那不就起飞🛫了？

一开始先以步长为5进行排序：

排序过程：

16<11,false,swap(16,11);

16<31,true;

out;

25<23,false,swap(25,23);

out;是错误的！

并不是做交换，而是用子序列普通插入排序后填入。

子序列1：11，16，31

sort（11，16，31）；

sort（子序列2）

sort（子序列3）

.......

第一趟排序结束

第二趟排序开始

......

直到d=1排序结束

return;

void ShellInsert ( SqList &L, int dk ) {//对直接插入排序进行修改：//1.增量是dk，不是1。2.r[0]是暂存单元，不是哨兵。for ( i=dk+1; i<=n; ++i ) if ( L.r[i].key< L.r[i-dk].key) { L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-dk; j>0&&(L.r[0].key<L.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置  L.r[j+dk] = L.r[0]; // 插入} // if} // ShellInsertvoid ShellSort (SqList &L, int dlta[], int t){ // 增量为dlta[]的希尔排序 for (k=0; k<t; ++t) ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序} // ShellSort