1、直接插入排序的基本思想
1.1、例子
初始状态：数列为 3,2,7,1,8，有序数列为【3】
第一趟：取出下标为1的数据2，完成后：2,3,7,1,8，有序数列为【2,3】
第二趟：取出下标为2的数据7，完成后：2,3,7,1,8，有序数列为【2,3,7】
第三趟：取出下标为3的数据1，完成后：1,2,3,7,8，有序数列为【1,2,3,7】
第四趟：取出下表为4的数据8，完成后：1,2,3,7,8，有序数列为【1,2,3,7,8】
1.2、算法描述
从数列的第2个元素依次取出，将这个数字 插入到 前面的有序数列 中去。
1.3、算法效率
时间复杂度：最恶劣为 O(n²)，最理想情况下为O(n)；
空间复杂度：需要借助一个变量，因此空间复杂度为S(1)。
2、基于顺序表的实现代码
2.1、main.c
int main(int argc, const char *argv[])
{//初始化一个无序的数组int arr[LEN];initArr(arr, LEN);//打印数据原始的内容printf("数组的原始内容为:\n");printArr(arr, LEN);//对数组进行直接插入排序int cnt=straightInsertSort(arr, LEN);//打印排序后数组的内容printf("快速排序完成，循环的次数为[%d],数组内容:\n", cnt);printArr(arr, LEN);return 0;
}
2.2、几个函数
void initArr(int *arr, int len){for(int i=0;i<len;i++)arr[i]=rand()%101;
}void printArr(int *arr, int len){for(int i=0;i<len;i++)printf("%-4d", arr[i]);printf("\n");
}int straightInsertSort(int *arr, int len){int cnt=0,i,j;for(i=1;i<len;i++){int temp=arr[i];for(j=i-1;j>=0&&arr[j]>temp;j--){arr[j+1]=arr[j];cnt++;}arr[j+1]=temp;cnt++;}return cnt;
}
2.3、运行结果
数组的原始内容为:
32 32 54 12 52 56 8 30 44 94
快速排序完成，循环的次数为[27],数组内容:
8 12 30 32 32 44 52 54 56 94 3、基于单链表的实现代码
3.1、与数组实现的区别
基于单来链表的实现方式，与数组实现不同在于：
1、找待插入位置：数组是从后往前进行判定的(后移元素和遍历比较放一起实现了)，而链表需要从前往后进行遍历判断待插入的位置；
2、插入操作：数组实现，需要进行后移操作，而链表只需要进行元素插入。但时间复杂度是一致的。
3.2、定义结构体
typedef struct n{union{int data;//元素节点，表示数据内容int len;//头节点，表示数据域的长度};struct n *next;
}Node, *PNode, *PLinkList;//创建一个长度为len的数列，并对元素赋随机值
PLinkList createLinkList(int len);
//打印链表的内容
void printLinkList(PLinkList L);
//直接插入排序,返回值为遍历的次数
int straightInsertSort(PLinkList L);
//销毁链表
void destroyLinkList(PLinkList L);
//头插法插入链表.插入成功返回1，失败返回0
int insertHead(PLinkList L, int data);
3.3、测试代码的步骤
int main(int argc, const char *argv[])
{//初始化一个无序的数列PLinkList L = createLinkList(10);//打印数据原始的内容printf("原始数据为:\n");printLinkList(L);//对数组进行直接插入排序int cnt=straightInsertSort(L);//打印排序后数组的内容printf("快速排序完成，循环的次数为[%d],内容:\n", cnt);printLinkList(L);//销毁链表destroyLinkList(L);return 0;
}
3.4、几个实现的函数
PLinkList createLinkList(int len){PLinkList L=(PLinkList)malloc(sizeof(Node));if(L == NULL)return NULL;L->len=0;L->next=NULL;for(int i=0;i<len;i++){insertHead(L, rand()%101);}return L;
}int insertHead(PLinkList L, int data){PNode p=(PNode)malloc(sizeof(Node));if(p == NULL)return 0;p->data=data;p->next=L->next;L->next=p;L->len++;
}void printLinkList(PLinkList L){PNode p =L->next;for(int i=0;i<L->len;i++){printf("%-4d", p->data);p=p->next;}printf("\n");
}int straightInsertSort(PLinkList L){int cnt=0;if(L->len == 1)return 0;//无须排序PNode p=L->next;//p指针待排元素的上一级指针PNode t=L;//t指针找待插入的位置PNode temp;for(int i=1;i<L->len;i++){temp=p->next;//temp为待排元素p->next=p->next->next;cnt++;//从头开始遍历链表,待插入的位置t(之后)t=L;for(int j=0;j<i;j++,t=t->next){cnt++;if(t==L && t->next->data > temp->data){break;}if(t->data<=temp->data && t->next->data>temp->data){break;} }//将p插入到链表temp->next=t->next;t->next=temp;if(t == p)p=p->next;}//最后一个元素单独处理//p=p->next;return cnt;
}
PS： 感觉straightInsertSort写得有点啰嗦，而且可能还有bug.
3.5、运行结果
原始数据为:
94 44 30 8 56 52 12 54 32 32
快速排序完成，循环的次数为[37],内容:
8 12 30 32 32 44 52 54 56 94 4、心得
1、直接插入排序用单链表实现，还是不容易的；
2、直接插入排序的优势，似乎是对基本有序的数列效率较高，有机会笔者想多生成点数据来试下。似乎在SQL中select where 值在某个范围，进行快直接插入排序，会不会效率较高？
