《12. 蛤蟆的数据结构进阶十二排序实现之直接插入法》由会员分享,可在线阅读,更多相关《12. 蛤蟆的数据结构进阶十二排序实现之直接插入法(3页珍藏版)》请在金锄头文库上搜索。
1、12. 蛤蟆的数据结构进阶十二排序实现之直接插入法蛤蟆的数据结构进阶十二排序实现之直接插入法本篇名言:“路是脚踏出来的路是脚踏出来的 , 历史是人写出来的,人的每一步行动历史是人写出来的,人的每一步行动都在书定自己的历史。都在书定自己的历史。 - 吉鸿昌吉鸿昌”接下来看下直接插入法的实现。1.直接插入法直接插入法直接插入排序(straight insertion sort) 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据 与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去
2、,进行了(n- 1)趟扫描以后就完成了整个排序过程。2.代码实现代码实现代码比较简单,具体查看源码部分。3.源码源码#include “stdio.h“void print(int a, int n) for(int j= 0; jn; j+) printf(“%d “,aj); void InsertSort(int a, int n) for(int i= 1; in; i+) if(ai ai-1) /若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入 int j= i-1; int x = ai; /复制为哨兵,即存储待排序元素 ai = ai-1; /先后移一个元素 while(x aj) /查找在有序表的插入位置 aj+1 = aj; j-; /元素后移 aj+1 = x; /插入到正确位置 /print(a,n); /打印每趟排序的结果 int main() int a8 = 3,1,5,7,2,4,9,6; printf(“before insertion sortn“);print(a,8);InsertSort(a,8); printf(“nafter insertion sortn“);print(a,8);