学步园

#include <iostream><br /> using namespace std;<br /> #define MAXSIZE 20<br /> typedef struct<br /> {<br /> int r[MAXSIZE+1];<br /> int length;<br /> }SqList;//顺序表存储的记录<br /> //输入记录<br /> void Input(SqList &L)<br /> {<br /> cin>>L.length;<br /> for(int i=1;i<=L.length;i++)<br /> cin>>L.r[i];<br /> }<br /> //输出记录<br /> void OutLook(SqList &L)<br /> {<br /> for(int i=1;i<=L.length;i++)<br /> cout<<L.r[i]<<" ";<br /> }<br /> //--------------------------------------<br /> //直接插入排序<br /> //--------------------------------------<br /> void DirectInsertSort(SqList &L)<br /> {<br /> int i,j;<br /> for(i=2;i<=L.length;i++)<br /> if(L.r[i]<L.r[i-1])<br /> {<br /> L.r[0]=L.r[i];//r[0]作为哨兵<br /> for(j=i-1;L.r[j]>L.r[0];j--)<br /> L.r[j+1]=L.r[j];<br /> L.r[j+1]=L.r[0];<br /> }<br /> }<br /> //------------------------------------<br /> //希尔排序<br /> //------------------------------------<br /> void ShellInsert(SqList &L,int d)<br /> {<br /> int i,j;<br /> for(i=d+1;i<=L.length;i++)//从分组的第二个元素开始<br /> if(L.r[i]<L.r[i-d])<br /> {<br /> L.r[0]=L.r[i];<br /> for(j=i-d;(j>0)&&(L.r[0]<L.r[j]);j-=d)<br /> L.r[j+d]=L.r[j];<br /> /*因为每个组内的元素都是间隔的，所以r[0]起不到哨兵的作用，故需用j>0来判断是否越界*/<br /> L.r[j+d]=L.r[0];<br /> }<br /> }<br /> void ShellSort(SqList &L)<br /> {<br /> int dk;<br /> dk=L.length/2;//分的组数<br /> while(dk>=1)//注意这里循环的条件<br /> {<br /> ShellInsert(L,dk);//对每一次分组进行排序，细化<br /> dk=dk/2;//进一步分组，直到dk=1，即把所有元素看成一组来排序<br /> }<br /> }<br /> void main()<br /> {<br /> freopen("in1.txt","r",stdin);<br /> SqList L;<br /> Input(L);<br /> DirectInsertSort(L);<br /> //ShellSort(L);<br /> OutLook(L);<br /> } 

希尔排序基本思想是：通过分组来，来对各个组内的元素进行排序，随着分组的逐渐粗化，使得整个待排序记录由无序到基本有序，再到有序的过程。

这里需要注意这两种插入排序算法各自的优点和缺点：

直接插入排序，由程序可知他的算法时间复杂度为O(n²)，空间复杂度是O(1)，且是一种稳定的排序算法（即关键字相同的记录，在排序后，相对彼此的顺序没有改变），它适用于待排序记录按关键字基本有序或是待排序记录较少的情况，在这些情况下，效率较高。

希尔排序，时间复杂度是O(nlog₂n)，空间复杂度是O(1)，是一种不稳定的算法（因为在分组时可能把两个关键字相同的记录分到不同的组，这样在排序时两者就不能比较了），它的性能在待排序的记录有较多时能得到充分的发挥。