数据结构08排序算法1

附加空间。另外,算法本身的复杂程度也是需要考虑的一个因素。? 排序算法所需要的附加空间一般都不大,矛盾并不突出。而排序是一种经常执行的一种运算,往往属于系统的核心部分,因此排序的时间开销是算法好坏的最重要的标志。Р基本概念Р为简单起见,数据的存储结构采用记录数组形式,同时假定关键字是整数。记录数组的类型说明如下:Рtypedef struct ?{ int key;? datatype other;?} rectype;? rectype R[n];Р排序(Sorting)Р插入排序Р基本原理,每步将一个待排序的对象,按其关键字大小,插入到前面已经排好序的一组对象适当位置上,直到对象全部插入为止。Р直接插入排序(Insert Sort)?希尔排序(Shell Sort)Р直接插入排序Р基本思想:А当插入第i个对象时,前面的V[1],V[2],…,V[i-1]已经排好序,此时,用v[i]的关键字与V[i-1], V[i-2],…的关键字顺序进行比较,找到插入位置即将V[i]插入,原来位置上对象向后顺移。Р直接插入排序Рi (1) (2) (3) (4) (5) (6) temp? [21] 25 49 25* 16 08 25?1 [21 25] 49 25* 16 08 49?2 [21 25 49] 25* 16 08 25*?3 [21 25 25* 49] 16 08 16?4 [16 21 25 25* 49] 08 08 ?5 [08 16 21 25 25* 49]РInsertsort(rectype R[ ])?{ 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+1]=R[0]; ? }?}Р直接插入排序算法