数据结构知识点

题型：

一、单项选择题（10小题，20%）

二、填空题（10小题，20%）

三、简答题（4小题，只要结果，20％）

四、应用题（给出解题过程和结果，20%）

五、算法填空（20%）

复习要点：

第一章

1.相关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、算法及其特征等；

◎数据：所有能输入到计算机中并被计算机程序处理的符号总称。

◎数据元素：基本单位。    

◎数据项：最小单位。

◎算法特征（5点）：有穷性；确定性；可行性；输入；输出。

2.逻辑结构、存储结构（物理结构）及其类型；

◎逻辑结构有四种基本类型：集合、线性结构、树形结构和网状结构。

◎数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

◎注：期中考题目

数据结构分为两大类，即为逻辑结构和存储结构。其中逻辑结果又分为 线性结构和非线性结构 ，存储结构一共有四种（顺序、链接、索引、散列）。

3.算法分析：语句频度（执行次数）计算、时间和空间复杂度分析。

表示方法

◎语句频度：直接写次数。

◎时间复杂度：O(执行次数),如：O(n)。

◎空间复杂度：O(所需空间)

第二章

  1.顺序表（数组）插入、删除、有序表合并算法及其移动次数计算；

数据元素   

序号    1     2    3    4    5     6    7    8

表示  L.elem[0]  [1]  [2]  [3]  [4]   [5]  [6]  [7]

◎顺序表插入

  算法思想：如果要在序号5前插入元素e，需要将序号5～8向后移动一个位置。

  ▲移动次数为4次，公式n-i+1

◎顺序表删除

  算法思想：如果要删除序号5元素，需要将6～8依次向前移动一位

    ▲移动次数为3次，公式n-i

◎有序表合并

  LA = (3,5,8,11)

  LB = (2,6,8,9,11,15,20)  

  则LC = (2,3,5,6,8,8,9,11,11,15,20)  

  算法思想（以非递减为例）：La和Lb非递减排列，La与Lb中元素逐个比较，较小的先插入Lc中。

     ▲注：非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。

  ▲移动次数为（La.length + Lb.length）

2.链表（有无头节点、单双、循环）插入(前、后)、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。

◎单链表

  ▲每个节点有数据域和指针域      data  next

                头     a1      a2      a3      a4      a5      a6

带头节点L→→→→→→→

                                        P↑

                 a1      a2      a3      a4      a5      a6

   不带头节点L→→→→→→

                                  P↑

单循环链表   

   ●在P（a3）节点前插入S节点

       (1)Q = P;  //先让Q指向a3

(2)P = L;  //P指向第一个节点（带头结点指向头结点，不带头结点指向a1）

(3)while(P->next != Q) P = P->next;  //找到a3的前驱a2，P指向a2

(4)S->next = P->next;  //P->next为a3，让S->next等于a3

(5)P->next = S;  //a2指针域指向节点S

●在P（a3）节点后插入S节点

    (1)S-next = P->next;

    (2)P->next = S;

●删除P（a3）前一个节点

  (1)Q = P;

  (2)P = L;

  (3)while(P->next->next != Q) P = P->next;  //找到a1

  (4)P->next = P->next->next;  //让a1指针域指向a3，从而删除a2

●删除P（a3）节点

  (1)Q = P;

  (2)P = L;

  (3)while(P->next != Q) P = P->next;  //找到a2

  (4)P->next = P->next->next;  //让a2指针域指向a4，从而删除a3

●删除P（a3）后一个节点

  (1)P->next = P->next->next;  //让a3指针域指向a5，从而删除a4

◎双链表

  ▲每个节点有前驱指针、数据域、后继指针 prior data next 

双循环链表  

                       头       a1       a2      a3     a4            

 ●在P（a2）节点前插入S节点

  ▲技巧：先让S->prior 和S->next与链表建立关系   

   注：步骤(4)必须在步骤(3)后面

   (1)S->next = P;  //先让S->next指向a2

   (2)S->prior = P->prior;  //S->prior指向a1

   (3)P->prior->next = S;  //再把a1->next指向S

   (4)P->prior = S;  // a2->prior指向S

●在P（a2）节点后插入S节点

  注：步骤(4)必须在步骤(3)后面

(1)S->prior = P;

(2)S->next = P->next;

   (3)P->next->prior = S;  //a3->prior指向S

(4)P->next = S;

●删除P（a2）前一个节点a1

  (1)Q = P->prior;  //Q指向要被删除的a1;

  (2)P->prior = P->prior->prior;  //P->priro指向头

  (3)P->prior->next = P;  //头->next指向P

   (4)free(Q);  //释放a1的存储空间

●删除P（a2）节点

(1)P->next->prior = p->prior;

(2)P->prior->next = p->next;

  (3)free(P);

●删除P（a2）后一个节点a3

(1)Q = P->next;

   (2)P->next = P->next->next;  //a2->next指向a4

   (3)P->next->prior = P;  //a4->prior = P

   (4)free(Q);  //释放a3存储空间

◎建立（不带头节点）单链表

读程序：设n为2（i取0，1）

i = 0时，

          p↑L↑q↑

i = 1时，     →

             L↑q↑    p↑        L↑q↑     p↑        

→

                 L↑       q↑p↑

第三章

  1.栈的进出序列、栈、队列、循环队列的满/空条件;

     ▲由于栈的插入、删除操作是在栈顶进行的，因而后进栈的元素必然是先出栈，0.所以栈是“后进先出”表。

▲由于队列的输入、输出操作分别在队的两端进行，因此先入队的元素必然先输出，故队列又称为“先进先出”表

   ◎栈的进出序列

     例题：进栈序列为123，可能得到的出栈序列是什么？

     答：共五种123/132/213/231/321

     进出栈情况（以132序列为例）：

1进栈→1出栈，输出1→2进栈→3进栈→3出栈→2出栈 输出32

◎栈、队列、循环队列的满/空条件

   栈空条件：s.top = s.base;栈满条件：s.top - s.base = stacksize;

   队空条件：Q.front=Q.rear; 队满条件：q->rear - q->front = MAXSIZE

循环队列空条件：Q.front=Q.rear

循环队列满条件：为避免在队满是队头指针和队尾指针也是重合的情况，规定队列中

还有一个空的存储单元时为队满，即为Q.front=(Q.rear+1)MOD maxsize(MOD为取余

运算符）。因而，这种循环队列不适合用动态数组作为存储结构。

 2. 栈、队列的存储结构、基本操作算法（双向栈）;

  ◎栈存储结构

●顺序栈

  typedef struct{

    SElemType *base;

    SElemType *top;

    int stacksize;

  }SqStack;

●链式栈

◎队列存储结构

 ●顺序存储结构

 ●链式存储结构 

◎双向栈

存储结构：

typedef   struct{ 

        Elemtype   *base[2]; 

        Elemtype   *top[2]; 

     }BDStacktype;   //双向栈类型

初始化：

Status Init_Stack(BDStacktype &tws, int m)//初始化一个大小为m的双向栈tws 

{ 

        tws.base[0 ]= (Elemtype*)malloc(sizeof(Elemtype)*m); 

        tws.base[1] = tws.base[0] + m; 

        tws.top[0] = tws.base[0]; 

        tws.top[1] = tws.base[1]; 

        return OK; 

}//Init_Stack

入栈：

Status push(BDStacktype &tws, int i, Elemtype x)

//x入栈,i=0表示低端栈,i=1表示高端栈 

{ 

if(tws.top[0] > tws.top[1]) return OVERFLOW;   

    //注意此时的栈满条件      

    if (i == 0) *tws.top[0]++ = x; 

    else if (i == 1) *tws.top[1]-- = x;     

    else return ERROR;    

    return OK; 

}//push

出栈：

Status pop(BDStacktype &tws, int i, Elemtype &x) 

//x出栈,i=0表示低端栈,i=1表示高端栈 

{ 

    if (i == 0) 

    {

        if (tws.top[0] == tws.base[0]) return   OVERFLOW; 

        x = *--tws.top[0]; 

    } 

    else if(i == 1) 

    { 

        if(tws.top[1] == tws.base[1]) return   OVERFLOW;  

        x = *++tws.top[1]; 

    } 

    else return ERROR;   

    return OK; 

}//pop

第四章

  1.字符串模式匹配的简单算法；

int Index(SString S, SString T, int pos) 

{  // 算法4.5

   // 返回子串T在主串S中第pos个字符之后的位置。

   // 若不存在，则函数值为0。

   // 其中，T非空，1≤pos≤StrLength(S)。

   int i = pos;

   int j = 1;

while (i <= S[0] && j <= T[0]) {

      if (S[i] == T[j]) {  // 继续比较后继字符

         ++i;

         ++j; 

      } 

else {  // 指针后退重新开始匹配

         i = i-j+2;  //此时i为上次开始比较位置的下一位

         j = 1; 

      }      

   }

if (j > T[0]) return i-T[0];

   else return 0;

} // Index

  2.计算NEXT。

   j      ：1 2 3 4 5 6 7

串     ：a b c a b a a

next[j]：0 1 1 1 2 3 2

▲技巧：第一二个肯定是0，1！如果要计算next[4]，找的字符串必须是以第3个字符c为结尾，第1个字符a为开头的。

以第6个为例，a前一个字母是b，以第5个字符b为结尾的ab刚好和以第1个字符为

开头的ab匹配，所以next[6] = 2+1 = 3。

第五章

  1.二维数组的地址（下标）换算；

    习题5.1假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算：

（1）数组A的体积（即存储量）

6*8*6 = 288字节

    （3）按行存储是，元素a14的第一个字节的地址

         1000+(8*1+4)*6 = 1072

         基址+(每行的元素个数*行数+当前列序)*每个元素所占存储单元

    （4）按列存储时，元素a47的第一个字节的地址

         1000+(6*7+4)*6 = 6276

         基址+(每列的元素个数*列数+当前行序)*每个元素所占存储单元

    习题5.2假设按低下标优先存储整数组A9*3*5*8时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？

    （2）a1111   地址：100+(3*5*8*1+5*8*1+8*1+1)*4 = 776

    （3）a3125   地址：100+(3*5*8*3+5*8*1+8*2+5)*4 = 1784

    （4）a8247   地址：100+(3*5*8*8+5*8*2+8*4+7)*4 = 4416

  2.特殊矩阵（三角、其他有规律）压缩为一维的下标计算；

◎下三角矩阵压缩为一维数组（记忆公式）

  ▲技巧：推荐把公式(2)背下来（i,j,R范围都是从0开始），其他根据范围变化公式

 (1)若1<=j,j<=n, 0<=R<=n(n+1)/2-1

       当i>=j时，k = i(i-1)/2+j-1;

       当i(2)若0<=i,j<=n-1, 0<=R<=n(n+1)/2-1

   //注意i,j是0到n-1，下面的公式相当于把(1)中i变成i+1,j变成j+1

   当i>=j时，k = (i+1)i/2+j;

   当j(3)若1<=j,j<=n, 1<=R<=n(n+1)/2

   //注意R是1到n(n+1)/2，下面公式相当于把(1)中k变成k-1

   当i>=j时，k = i(i-1)/2+j;

   当i(4)若0<=j,j<=n-1, 1<=R<=n(n+1)/2

   当i>=j时，k = (i+1)i/2+j+1;

   当i3.稀疏矩阵的三元组表示。

4.稀疏矩阵应用的算法。（略）

第六章

  1.二叉树的性质；

    性质1：。

性质2：深度为k的二叉树至多有个结点(k1)。

性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

性质4：。

性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，

则对任一结点i(1in)，有：  

(1)如果i=1，则结点i是二叉树的根，无双亲； 

如果i>1，则其双亲是i/2。 

(2)如果2i>n，则结点i无左孩子； 

             如果2in，则其左孩子是2i。 

          (3)如果2i+1>n，则结点i无右孩子； 

             如果2i+1n，则其右孩子是2i+1。

  2.二叉树的先序、中序、后序、层次遍历过程；树的先序、后序、层次遍历过程；

二叉树遍历过程：

        先（根）序遍历：根→左子树→右子树

        中（根）序遍历：左子树→根→右子树

        后（根）序遍历：左子树→右子树→根

        层次遍历：从上到下，从左往右，逐个遍历

树的遍历过程：

        先根（次序）遍历：先访问根结点，然后依次先根遍历根的每棵子树(根→子树)

        后跟（次序）遍历：先依次后根遍历每棵子树，然后访问根结点（子树→根）

        层次遍历：从上到下，从左往右，逐个遍历

▲注：树与二叉树相互转化后

        树的先根遍历相当于二叉树的先序遍历

树的后根遍历相当于二叉树的中序遍历

  3.给出两个遍历序列，画出树（二叉树、树）

    习题6.23画出和下列已知序列对应的树T：

    (1)树的先根次序访问序列为GFKDAIEBCHJ;

    (2)树的后根次序访问序列为DIAEKFCJHBG。

        注：树的后根遍历相当于二叉树的中序遍历

                                              由(1)知G为根；

                                              G为根，联系(2)知G无右子树；

                                              观察(1)，F为G左子树；

                                              根据，观察(2)知DIAEK在F左边，

                                                CJHB在F右边；

                                              观察(1)，K为F左子树；

                                              根据，观察(2)知K无右子树；

                                              观察(1)，D为K左子树；

                                              根据，观察(2)知D无左子树；

                                              观察(1)，A为D右子树；

                                              观察(2)，IE分别为A左右子树；

                                              F的右子树自行观察判断。

  4.二叉树与树相互转换；

◎树转化成二叉树：

  规则：树的最左孩子变成二叉树左子树，该左孩子的兄弟变成二叉树左子树的右子树

    注：原树中B为A最左孩子，C,D为B兄弟，变成二叉树后C成为B右子树，D成为C右子树。

   ◎二叉树转化成树

  5.求哈夫曼树和给出编码、带权路径长度计算。

    习题6.26假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.21, 0.10。试为这8个字母设计哈夫曼编码，并求带权路径长度

设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。

①当前未用权：7、19、2、6、32、3、21、10，选出2、3构造出5。

⑵当前未用权：7、19、6、32、21、10、5，选出5、6构造出11。

③当前未用权：7、19、32、21、10、11，选出7、10构造出17。

④当前未用权：19、32、21、11、17，选出11、17构造出28。

⑤当前未用权：19、32、21、28，选出19、21构造出40。

⑥当前未用权：32、28、40，选出32、28构造出60。

⑦剩下权：40、60，构造出100

▲编码：树的左分支为0，右分支为1。

得到哈夫曼编码为A:1101  B:01  C:11111  D:1110  E:10  F:11110  G:00  H:1100

带权路径长度：(7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4)/100 = 2.61

▲注：该公式为：A路径长*A权+B路径长*B权+…+H路径长*H权，因为设的权值是原来的100倍，所以结果除以100。

第七章

 1.邻接矩阵、邻接表存储结构及其特征；

注：以有向图G1为例(有路径用1，否则0)

v1  v2  v3  v4

v1  0   1   1   0   

v2  0   0   0   0

v3  0   0   0   1

v4  1   0   0   0

注：以有向图G1为例

标号 0  1  2  3

 0   0  1  1  0

 1   0  0  0  0

 2   0  0  0  1

 3   1  0  0  0

第0行值为1的是1、2，所以有

V1→2→1。

第1行值全为0，所以有

V2。

第2行值为1的是3，所以有

V3→3。

第3行值为1的是0，所以有

V4→0。

  2.求最小生成树（Prim、Kruskal）；

   ◎普里姆（Prim）： 以点为基础

①从V1开始，找到最小边(V1,V3)；

②寻找与V1、V3相关联的最小边，找到(V3,V6)；

③寻找与V1、V3、V6相关联的最小边，找到(V6，V4)；

④寻找与V1、V3、V6、V4相关联的最小边，此时有(V4,V1)和(V3,V2)，因为(V4,V1)与原来的边构成圈，所以选择(V3,V2)。（如果(V4,V1)不与原来的边构成圈，则二条边任选一条）；

⑤寻找与V1、V3、V6、V4、V2相关联，并且不与原来边构成圈的最小边，找到(V2,V5)；

◎克鲁斯卡尔(Kruskal)（避圈法）：以边为基础

  方法介绍：依次寻找权最小边，避免生成一个圈，所有点联通时生成最小树。

  3.拓扑排序；

    步骤：（1）在有向图中选一个没有前驱的顶点且输出之。

         （2）从图中删除该顶点和所有以它为尾的弧。

输出：                V6              V1          V4       V2      V5

注：拓扑排序不唯一。

4.求最短路径过程（Dijkstra、Floyd）。

◎迪杰斯特拉(Dijkstra)

      习题7.11试利用Dijkstra算法求题7.11图中从顶点a到其他各顶点间的最短路径，写

出执行算法过程中各步状态。

求解过程：

    K=1时，找a能直接到达的点，有b,c,d，(a,c)权最小，(a,c)为a到c最短路径，将c放如终点集S；

    K=2时，找a能直接到达的点，或通过(a,c)能到达的点，(a,c,f)权最小，(a,c,f)为a到f的最短路径，将f放入终点集S；

    K=3时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，

(a,c,e)权最小，(a,c,e)为a到e最短路径，将e放入终点集S；

    K=4时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，或通过(a,c,e)能到达的点，(a,c,f,d)为a到d最短路径，将d放入终点集S；

    K=5时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，或通过(a,c,e)能到达的点，或通过(a,c,f,d)能到达的点，(a,c,f,d,g)权最小，为a到g最短路径，将g放入终点集S；

    K=6时，只剩下(a,b)，(a,b)为a到b最短路径，将b放入终点集S。

◎弗洛伊德(Floyd)

    注：D(1)[i][j]是从Vi到Vj的中间顶点的序号不大于1的最短路径的长度；D(k) [i][j]是从Vi到Vj的中间顶点的序号不大于k的最短路径的长度；D(n-1) [i][j]就是从Vi到Vj的最短路径的长度。

D(-1)栏中，Vi→Vj不允许有转折点。直接填邻接矩阵。

D(0)栏中，Vi→Vj只允许通过V0转折，或者不转折。通过V0转折权值小于原权值，就把原权值替换掉。

D(1)栏中，Vi→Vj只允许通过V0、V1转折，或者不转折。如果转折后权值小于原权值，替换。

D(2)栏中，Vj→Vj允许通过V0、V1、V2转折，或者不转折，如果转折后权值小于原权值，替换。此时p(2)中就是各点间的最短路径。

第九章

  1.以下所有查找成功平均查找长度

2.顺序查找；折半查找；

◎顺序查找：从表中最后一个记录开始，逐个进行比较。

▲平均查找长度

 等概率时，平均查找长度ASL = (n+1)/2

 不等概率时，ASL = nP1 + (n-1)P2 + … + 2Pn-1 + Pn

◎折半查找：

指针low和high分别指示待查元素所在范围的下界和上界，mid=(low+high)/2，

如果要找的值大于S[mid]，则让mid = (mid+1 + high)/2，继续比较；

如果要找的值小于S[mid]，则让mid = (low + mid-1)/2，继续比较。

▲平均查找长度

  等概率条件下，ASL=(n+1)-1

                当n>50时，有近似结果ASL=(n+1)-1

3.二叉排序树的插入（建立）、删除、平衡过程；

◎二叉排序树建立

     (1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

     (2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

     (3)它的左、右子树也分别为二叉排序树。

▲注：中序遍历二叉 排序树，得到从小到大序列

根据字母的先后确定大小

插入Jan； F小于J，Feb成为Jan左子树； M大于J，Mar成为Jan右子树； Apr小于Jan，且Apr小于Feb，Apr成为Feb左子树； May大于Jan，且May大于Mar，May成为Mar右子树； June大于Jan，且June小于Mar，June成为Mar左子树。剩下的略。

◎二叉排序树删除（）

     3种情况：

        (1)*p为叶子节点，直接删除。

        (2) *p只有一个孩子*child只需将*child和*p的双亲直接连接后，即可删去*p。

        (3)*p有两个孩子

            用*p的直接前驱或直接后继代替*p，然后删除它的直接前驱或直接后继。

◎平衡二叉树：树上任何节点的左右子树深度差都不超过1

  ▲插入节点P后不平衡，找到离P最近的不平衡点，根据二叉排序树的建立进行调整。

     序列：Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec

(1)插入Aug时，Feb左右子树深度差超过1不平衡

(2)插入Oct时，最近不平衡点为May。因为Sep>Oct>May，所以Oct作为双亲

(3)插入Nov时，Jan不平衡。把Jan左转，Mar的左子树变成Jan右子树。

最终平衡树

4.哈希表构造、冲突解决方法；除留余数法、线性探测或链地址法。

    ◎构造：

除留余数法：H(key) = key MOD p, p<=m 

◎冲突解决：

线性探测法：Hi = (H(key)+) Mod m  i = 1, 2, …, k(k <= m-1)

链地址法：将所有关键字为同义词的记录存储在同一线性链表中。

例题：已知一个线性表（38，25，74，63，52，48），假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A[0..6]中，采用线性探测方法解决冲突。

①38：38%7 = 3，查找次数为1。

⑵25：25%7 = 4，查找次数为1。

③74：74%7 = 4，与25冲突，

(4+1)%7 = 5，查找次数为2。

④63：63%7 = 0，查找次数为1.

⑤52：52%7 = 3，与38冲突，

(3+1)%7 = 4，与25冲突，

(4+1)%7 = 5，与74冲突，

(5+1)%7 = 6，查找次数为4。

⑥48：48%7=6，与52冲突，

   (6+1)%7 = 0，与63冲突，

   (0+1)%7 = 1，查找次数为3

地址： 0    1     2     3    4    5     6

次数： 1     3          1    1     2    4

                                             等概率成功查找的平均查找长度为：

                                             (1+3+1+1+2+4)/6 = 2

第十章

1.简单排序（直接插入、选择、冒泡）的过程；

◎直接插入（略）

◎选择排序

基本思想：依次在序列中选出最小的记录R[k]，将它与第1个记录R[1]交换。

模式：for (i = 0; i < 10; i++)

        for (j = i; j < 10; j++)    ;

◎冒泡排序：

  基本思想：依次比较相邻的两个数，将小数放在前面，大数放在后面。

  模式：for(i = 0; i < n; i++)

            for(j = 0; j < n-i-1; j++);

2.先进排序（希尔、快速、堆、归并、基数）过程；

◎希尔排序：

基本思想：先取一个小于n的整数d1作为第一个增量，所有距离为dl的倍数的记录放在同一个组中，先在各组内进行直接插人排序；然后，取第二个增量d2◎快速排序：

基本思想：选第一个记录为支点，通过一趟排序将待排记录分割成的两部分，其中一部分记录关键字比支点小，另一个部分记录的关键字比支点大。再可分别找两个支点，对这两部分记录继续进行快速排序。

◎堆排序：n个关键字序列Kl，K2，…，Kn称为堆，必须所有根大于（或小于）其子树。

    例题：无序序列{49, 38, 65, 97, 76, 13, 27, 49}，进行堆排序

思路：将次序列写出完全二叉树形式，然后从最有一个非终端结点开始筛选。

◎归并排序：

◎基数排序：

     先将个位数值与f[i]中的i值相等的放入相应位置

     将十位数值与f[i]中的i值相等的放入相应位置

     将百位数值与f[i]中的i值相等的放入相应位置

3.各种排序的特点、稳定性、时间复杂度（包括平均、最好、最坏）。

希尔排序               O(nlogn)               O()