struct node f int key; int data; typedef struct node node void insertsort(r, n) NODE rl l;intn;/*r为具有n+1个单元的数组,n为记录个数* f int i, j; for(i=2; i<=n; i++) {r|0=r[i;*将待排序记录赋予下监视哨* while(r10key< rIjn. key)/待排序记录的关键字值与有序子序列*/ /的各记录的关键字值进行比较/ r计+1rj-;/若条件真,则rj记录后移* ri+1-r|0];/若条件假,则待排序记录插入到相应位置*
struct node { int key; int data; }; typedef struct node NODE; void insertsort(r,n) NODE r[ ]; int n; /* r[ ]为具有n+1个单元的数组, n为记录个数*/ { int i,j; for(i=2;i<=n;i++) { r[0]=r[i]; /* 将待排序记录赋予下监视哨*/ j=i-1; while(r[0].key<r[j].key) /*待排序记录的关键字值与有序子序列*/ /*的各记录的关键字值进行比较/* r[j+1]=r[j--]; /*若条件真, 则r[j]记录后移*/ r[j+1]=r[0]; /*若条件假, 则待排序记录插入到相应位置*/ } }
算法简洁、容易实现是直接插入排序的两大特点, 下面分析其时间效率 整个排序过程中只有比较关键字和移动记录两种运 算.当原始记录已按关键字非递减有序,即为正序时, 时间效率最高,因完成每趟排序仅需进行一次比较及两 次移动记录操作(即开始时将记录移至监视哨中和最后将 记录移入适当位置,整个排序过程总的比较次数为n-1, 记录总的移动次数为(m-1,故其时间复杂度为Omn); 反之,如果原始记录是按关键字非增减有序的,即为 逆序时,时间效率最低,因要插入的第个记录,均要与 前i-1个记录及监视哨的关键字进行比较,即每趟要进行 i次比较,总的比较次数为: ∑i=(n+2)(n-1)/2
算法简洁﹑容易实现是直接插入排序的两大特点, 下面分析其时间效率. 整个排序过程中只有比较关键字和移动记录两种运 算. 当原始记录已按关键字非递减有序, 即为正序时, 时间效率最高, 因完成每趟排序仅需进行一次比较及两 次移动记录操作(即开始时将记录移至监视哨中和最后将 记录移入适当位置), 整个排序过程总的比较次数为n-1, 记录总的移动次数为2(n-1), 故其时间复杂度为O(n); 反之, 如果原始记录是按关键字非增减有序的,即为 逆序时, 时间效率最低, 因要插入的第i个记录, 均要与 前i –1个记录及监视哨的关键字进行比较, 即每趟要进行 i次比较, 总的比较次数为: ( 2)( 1)/ 2 2 = + − = i n n n i
从移动记录的次数来看,每趟排序中除了上面提到的两 次移动外,还需将有序子序列中关键字值大于待排序记 录的关键字值的记录后移一个位置,总的移动次数为: ∑(+1)=(n+4)(n-1)/2 故其时间复杂度为O(n2) 若在随机情况下,设待排序记录序列可能出现的各 种排列的概率相同,则可取上述两种极端情况的平均值 作为比较和移动记录的平均次数,约为n2/4.由此,直 接插入排序的时间复杂度为Omn2) 直接插入排序是稳定的排序方法 对于直接插入排序,补充一C函数,其功能为:将 以带头结点的单链表存储的一组无序记录,排序成非递 减序列
从移动记录的次数来看, 每趟排序中除了上面提到的两 次移动外, 还需将有序子序列中关键字值大于待排序记 录的关键字值的记录后移一个位置, 总的移动次数为: ( 1) ( 4)( 1)/ 2 2 + = + − = i n n n i 故其时间复杂度为 ( ). 2 O n 若在随机情况下, 设待排序记录序列可能出现的各 种排列的概率相同, 则可取上述两种极端情况的平均值 作为比较和移动记录的平均次数, 约为 /4 2 n . 由此, 直 接插入排序的时间复杂度为 ( ). 2 O n 直接插入排序是稳定的排序方法. 对于直接插入排序, 补充一C函数, 其功能为: 将 以带头结点的单链表存储的一组无序记录, 排序成非递 减序列
struct node int key; struct node *next;; typedef struct node node void insertsort(h NODE *h INODE*p, *r* 1, q; int exchang: =h->next;/指向有序子表的表尾 q=l->next;/*q指向待排序的结点 while(q=null) p=h->next;/p指向有序子表的表头,排序过程中可向表尾移动* r=h /*r指向p的直接前趋结点* exchang=0;/标识结点未交换* while(p!=q & exchang==0) fif(p->key<=q->key) r=p;p=r->next;}/结点后移*
struct node { int key; struct node *next; }; typedef struct node NODE; void insertsort(h) NODE *h; { NODE *p,*r,*l,*q; int exchang; l= h->next; /*l指向有序子表的表尾*/ q=l->next; /*q指向待排序的结点*/ while(q!=null) { p=h->next; /* p指向有序子表的表头, 排序过程中可向表尾移动*/ r=h; /* r指向p的直接前趋结点*/ exchang=0;/*标识结点未交换*/ while(p!=q && exchang==0) { if(p->key<=q->key) { r=p; p=r->next; } /*结点后移*/
se RI->next=q->next; q->next=p r->next=q; /待排序的结点前插* exchang-l; /标识结点有交换* if(p=q)l=q;/一趟排序未交换q指向的待排序结点成为有+ /序子表的表尾结点 q=->next;/q指向下一趟排序的待排序结点* 811希尔排序 希尔排序是对直接插入排序法的一种改进,提高了 排序的效率.希尔排序的作法是:先取定一个小于待排 序记录个数n的整数d1作为第一个增量,将待排序的所有
else { l->next=q->next; q->next=p; r->next=q; /*待排序的结点前插*/ exchang=1; /*标识结点有交换*/ } } if(p==q) l=q;/*一趟排序未交换, q指向的待排序结点成为有*/ /*序子表的表尾结点*/ q=l->next; /*q指向下一趟排序的待排序结点*/ } } 8.1.1希尔排序 希尔排序是对直接插入排序法的一种改进, 提高了 排序的效率. 希尔排序的作法是: 先取定一个小于待排 序记录个数n的整数d1 作为第一个增量, 将待排序的所有