hao对《数据结构与算法分析》的笔记(11)

数学基础： 定义：如果存在正常数c和n0使得当N >= n0时 T(N) <= c*f(N),则记为 T(N) = O(f(N)) 定义：如果存在正常数c和n0使得当N >= n0时 T(N) >= c*g(N),则记为 T(N) = Ω(g(N)) 定义：T(N) =

当前仅当T(N) = O(h(N))且T(N) = Ω(h(N)). 定义：如果T(N) = O(p(N)) 且T(N)

,则T(N) = o(p(N)). 法则1： 如果T1(N)=O(f(N)) 且T2(N) = O(g(N)),那么 a. T1(N) + T2(N) = max(O(f(N)), O(g(N))) b. T1(N) * T2(N) = O(f(N) * g(N)) 法则2： 如果T(N)是一个k次多项式，则T(N) =

法则3： 对于任意常数k，\log ^{k}N = O(N).它告诉我们对数增长非常缓慢。 一般法则： 法则1--------for循环 一次for循环的运行时间至多应该是for循环内语句（包括测试）的运行时间乘以迭代的次数。 法则2--------嵌套的for循环 从里向外分析这些循环。在一组循环嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有for循环的大小乘积。 法则3-----顺序语句 将各个语句的运行时间求和即可（这意味着，其中最大值就是所得的运行时间） 法则4-------if/esle语句 一个if/else语句的运行时间从来不超过判断加上if语句块和else语句块中运行时间长者的总的运行时间。 最大子序列求和算法：

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum = 0, MaxSum = 0, j;
    for( j = 0; j < N; j++)
    {
        ThisSum += A[j]
       if(ThisSum > MaxSum)
               MaxSum = ThisSum;
       else  if(ThisSum < 0)
                 ThisSum = 0;
              
    }
    
    return MaxSum
}

上面的代码无非不就是最大值状态的更新转移。消除多重循环。 对分查找：

int BinarySearch(const ElementType A[], ElementType X, int N)
{
     int Low = 0, Mid, High = N - 1;
     while(Low <= High)
     {
         Mid = (Low + High) / 2;
         if(A[Mid] < X)
             Low = Mid + 1;
         else if(A[Mid] > X)
            High = Mid - 1;

         return Mid
     }
     
    return NotFound;
}

欧几里得算法： 计算两个数的最大公因数

unsigned int  GCD (unsigned int M, unsigned int N)
{
      unsigned int Rem;
      while( N > 0)
      {
          Rem = M % N;
          M = N;
          N = Rem;
      }
      return M;
}

表：

链表在内存中不必相连。 链表的类型声明：

#ifndef _List_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);
int isEmpty(List L);
int isLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position  FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);

#endif 


//Place in the implement file
struct Node{
    ElementType Element;
    Position Next;
};

测试一个链表是否是空链表:

//Return True if L is empty
int isEmpty(List L)
{
    return L->Next == NULL;
}

测试当前位置是否是链表的末尾：

int isLast(Position P, List L)
{
    return P->Next == NULL;
}

查找：

Position Find(ElementType X, List L)
{
    Position P;
    P = L->Next;
    while(P != NULL && P -> Element != X)
    {
         P = P -> Next;
    }
    
return P;
}

删除链表节点：

void Delete(ElementType X, List L)
{
     Position P, TmpCell;
     P = FindPrevious(X, L)
     
     if(!IsLast(P, L))
     {
          TmpCell = P -> Next;
          P -> Next = TmpCell -> Next;
          free(TmpCell);
     }
}

查找前驱结点：

Position FindPrevious(ElementType X, List L)
{
    Position P;
    
    P = L;
    while(P->Next != NULL && P -> Next -> Element != X)
    {
        P = P -> Next;
    }
    
   return P;
}

链表的插入：

void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;
    
    TmpCell = malloc(sizeof(struct Node));
    if(TmpCell == NULL)
          Error("Out of Place");
    
    TmpCell -> Element = X;
     TmpCell -> Next = P -> Next;
    P -> Next = TmpCell;
}

删除链表：

void DeleteList(List L)
{
    Position P,Tmp;
    
    P = L -> Next;
    L -> Next = NULL;
    
    while(P != NULL)
    {
       Tmp = P -> Next;
       free(P);
       P = Tmp;
    }
}

栈的ADT：

栈的链表实现： 栈ADT链表实现的类型声明：

#ifndef _Stack_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
#endif

struct Node{
   ElementType Element;
   PtrToNode Next;
};

测试栈是否为空栈：

int IsEmpty(Stack S)
{
    return S -> Next == NULL;
}

创建空栈：

Stack CreateStack(void)
{
    Stack S;
    S = malloc(sizeof(struct Node));
    
    if(S == NULL)    Error("Out of space");
     
    S -> Next = NULL;
    MakeEmpty(S);
     
    reurn S;
}


void MakeEmpty(Stack S)
{
    if(S == NULL)  Error("Must use CreateStack First!");
     
    else
        while(!IsEmpty(S))    Pop(S);
}

Push进栈：

void Push(ElementType X, Stack S)
{
    PtrToNode TmpCell;
    
    TmpCell = malloc(sizeof(struct Node));
    if(TmpCell == NULL)   Error("Out of space");
    
    else
    {
        TmpCell -> Element = X;
         TmpCell -> Next = S -> Next;
        S -> Next = TmpCell;
    }
}

返回栈顶元素：

ElementType Top(Stack S)
{
    if(!IsEmpty(S))  return S -> Next -> Elemnt;
    Error("Empty Stack");
    return 0;
}

从栈弹出元素：

void Pop(Stack S)
{
   PtrToNode FirstCell;
    
   if(IsEmpty(S))  Error("empoty stack");

   else
   {
       FirstCell = S -> Next;
       S -> Next = S -> Next -> Next;
       free(FirstCell);
   }
}

队列模型：

队列的ADT类型声明：

#ifndef _Queue_H

struct QueueRecord;
typedef struct QueueRecord *Queue;

int IsEmpty(Queue Q);
int IsFull(Queue Q);
Queue CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);
void MakeEmpty(Queue Q);
void Enqueue(ElementType X, Queue Q);
 ElementTpe Front(Queue Q);
void Dequeue(Queue Q);
ElementType FrontAndDequeue(Queue Q);

#endif


#define MinQueueSize  5


struct QueueRecord{
        int Capacity;
        int Front;
        int Rear;
        int Size;
        ElementType *Array;
};

测试队列是否为空(数组实现)：

int  IsEmpty(Queue Q)
{
    return Queue -> Size == 0;
}

构造空队列：

void MakeEmpty(Queue Q)
{
     Q -> Size = 0;
     Q -> Front = 1;
     Q -> Rear = 0;
}

入队：

static int Succ(int Value, Queue Q)
{
    if(++ Value == Q -> Capacity)   Value = 0;
    return Value;
}

void Enqueue(ElementType X,Queue Q)
{
    if(IsFull(Q))  Error("Full Queue");
    else
    {
        Q -> Size ++;
        Q -> Rear = Succ(Q -> Rear, Q);
        Q -> Array[Q -> Rear] = X;
    }
}

树的遍历和应用：

二叉树： 二叉树(binary tree)是一棵树，其中每个节点都不能有多于两个的儿子。二叉树的一个性质是平均二叉树的深度要比N小得多，这个性质很重要。分析表明，这个平均深度为O(

)，而对于特殊类型的二叉树，即二叉查找树（binary search tree）,其平均深度为O(log N)。最坏情况深度达到N - 1。

表达式树： 表达式树（expression tree）的树叶是操作数（operand，比如常量或变量，而其它的节点为操作符（operator））。 二叉查找树：

因为二叉查找树的平均深度为O(log N)，所以一般递归建树，不用担心栈空间被耗尽。 二叉查找树声明：

#ifndef _TREE_H

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);

#endif

struct TreeNode{
      ElementType Element;
      SearchTree Left;
      SearchTree Right;
}

建立一棵空树：

SearchTree MakeEmpty(SearchTree T)
{
    if(T != NULL)
    {
          MakeEmpty(T->Left);
          MakeEmpty(T->Right);
          free(T);
    }

    return NULL;
}

Find操作：

Position Find(ElementType X, SearchTree T)
{
     if(T == NULL)  return NULL;
     if(X < T -> Element)    return Find(X, T -> Left);
     else if(X > T->Element) return Find(X, T -> Right);
     else
       return T;
       
}

FindMin的递归实现：

Position FindMin(SearchTree T)
{
    if(T == NULL)    return NULL;
    else if(T -> Left == NULL )  return T;
    else
        return FindMin(T -> Left);
}

FinMax的非递归实现：

Position FindMax(SearchTree T)
{
    if(T != NULL)
      while(T -> Right != NULL)
      {
          T = T -> Right;
      }
      
     return T;
}

插入元素到二叉查找树：

SearchTree Insert(ElementType X, SearchTree T)
{
     if(T == NULL)   
     {
         T = malloc(sizeof(struct TreeNode));
          if(T == NUU)   Error("Out of space");
          else
          {
              T -> Element = X;
              T -> Left = T -> Right = NULL;
          }
     }
     else if(X < T -> Element)
     {
          T -> Left = Insert(X, T);
     }
     else if(X > T -> Element)
     {
           T -> Right = Insert(X, T);
     }
     
     return T;
}

二叉查找树的删除：

SearchTree Delete(ElementType X, SearchTree)
{
    Position TmpCell;
    
    if(T == NULL)
        Error("Element not Found");
    else if(X < T -> Element)
         T -> Left = Delete(X, T -> Left);
     else if(X > T -> Element)
        T -> Right = Delete(X, T -> Right);
     else if(T -> Left && T -> Right)  //Two Children
     {
           TmpCell = FindMin(T -> Right);
           T -> Element = TmpCell -> Element;
           T -> Right = Delete(T -> Element, T -> Right);
     }
     else   //One or Zero Children
     {
         TmpCell = T;
         if(T -> Left == NULL)
                 T = T -> Right;
         else if(T-> Right == NULL)
                 T = T -> Left;
         free(TmpCell);
     }
      
    return T;
}

AVL树： AVL树是带有平衡条件的二叉查找树。 B树： 一种常用的查找树（不是二叉树），叫B树。

总结： 分析树是编译器设计的核心数据结构。分析树不是二叉树，而是表达式树相对简单的扩充。查找树的非递归实现多少要快一些。查找树的问题在于，其性能严重的依赖输入，而输入时随机的。如果情况不是这样，则运行时间会显著增加，查找树会成为昂贵的链表。

散列表的通常关键字不是整数，是字符串。 一种方法是把字符串的ASCII码加起来。(简单的散列函数)

typedef usigned int Index;

Index Hash(const char* key, int TableSize)
{
     unsigned int HashVal = 0;
     while(*key != '\0')    HashVal  += *key++;

     return HashVal % TableSize;
}

//不太好的hash函数
Index Hash(const char *key, int TableSize)
{
     return (key[0] + 27*key[1] + 729*key[2])   % TableSize;
}

//一个好的散列函数
Index Hash(const char *key, int TableSize)
{
     unsigned int HashVal = 0;
      while(*key != '\0')    HashVal = (HashVal << 5) + *key++;
      return HashVal % TableSize;
}

如果当一个元素被插入时另一个元素已经存在（散列值相同），那么就产生一个冲突，这个冲突需要消除。一般有两种：分离连接法和开放定址法。 分离链接法的做法就是将散列到同一个值的所有元素保留到一个表中。

分离链接散列表的类型声明：

#ifndef _HASHSEP_H

struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable(int TableSize);
void DestoryTable(HashTable H);
Position Find(ElementType Key, HashTable H);
void Insert(ElementType Key, HashTable H);
ElementType Retrieve(Position P);

#endif

struct ListNode{
       ElementType Element;
       Position Next;
};

typedef Position List;

struct HashTbl{
     int TableSize;
     List *TheLists;
}

分离链接散列表的初始化：

HashTable IinitializeTable(int TableSize)
{
     HashTable H;
     int i;
     
     if(TableSize < MinTableSize)
     {
          Error("TableSize too small");
     }

    H = malloc(sizeof(struct HashTbl));
    if(H == NULL)   Error("Out of space");
    
    H -> TableSize = NextPrime(TableSize);
    
    H -> TheLists = malloc(sizeof(List) * H -> TableSize);
    if(H -> TheLists == NULL)   Error("Out of space");
    
    for(i = 0; i < H -> TableSize; i++)
   {
           H -> TheList[i] = malloc(sizeof(struct ListNode));
           if(H -> TheLists[i] == NULL)   Error("Out of Space");
           else
                   H -> TheLists[i]  -> Next = NULL;
   }

   return H;
}

分离链接散列表的Find:

Position Find(ElementType Key, HashTable H)
{
    Position P;
    List L;
    
    L = H ->TheLists[Hash(Key, H -> TableSize)];
    P = L ->Next;
    while(P != NULL && P -> Element != Key)
   {
       P = P -> Next;
   }
   
   return P;
}

分离链接散列表的Insert:

void Insert(ElementType Key, HashTable H)
{
    Position Pos, NewCell;
    List L;
    
    Pos = Find(Key, H);
    
    if(Pos == NULL) 
    {
        NewCell = malloc(sizeof(struct ListNode));
        if(NewCell == NULL)    Error("Out of space");
        else
        {
             L = H -> TheLists[Hash(Key, H->TableSize)];
             NewCell -> Next = L -> Next;
             NewCell -> Element = Key;
             L -> Next = NewCell;
        }
    } 
}

开放定址法：

开放定址法有三种冲突解决方法：线性探测，平方探测，双散列。 平方探测是消除线性探测探测中一次聚集的问题。平方探测就是冲突函数为二次函数的探测方法。对于线性探测，让元素几乎填满散列表并不是个好主意，因为此时表的性能会下降。 定理：如果使用平方探测法，且表的大小是素数，那么当表至少有一半是空的时候，总能插入一个新元素。 开放定址散列表的类型声明：

#ifndef _HASHQUAD_H

typedef unsigned int Index;
typedef Index Position;

struct HashTbl;
typedef HashTbl *HashTable;

HashTable InitializeTable(int TableSize);
void DestoryTable(HashTable H);
Position Find(ElementType Key, HashTable H);
void Insert(ElementType Key, HashTable H);
ElemenType Retrieve(Position P, HashTable H);
HashTable Rehash(HashTable H);

#endif

enum KindOfEntry{
        Legitimate,
        Empty,
        Deleted
};


struct HashEntry{
           ElementType Element;
           enum KindOfEntry Info;
};

typedef struct HashEntry Cell;
 
struct HashTbl{
     int TableSize;
     Cell  *TheCells;
};

初始化开放定址表：

HashTable  InitializeTable(int TableSize)
{
    HashTable H;
    int i;
     
      if(TableSize < MinTableSize)
     {
          Error("TableSize too small");
     }

    H = malloc(sizeof(struct HashTbl));
    if(H == NULL)  Error("Out of space");
    
     H -> TableSize = NextPrime(TableSize);
     
     H -> TheCells = malloc(sizeof(Cell) * H -> TableSize);
     if(H -> TheCells == NULL)   Error("Out of space");
     
     for(i = 0; i < H -> TableSize; i++)
     {
         H -> TheCells[i].Info = Empty;
     }
     return H;
}

使用平方探测散列表的Find

Position Find(ElementType Key, HashTable H)
{
     Position CurrentPos;
     int CollisionNum;
     
     CollisionNum = 0;
     CurrentPos = Hash(Key, H -> TableSize);
     while(H -> TheCells[CurrentPos].Info != Empty &&
               H ->TheCells[CurrentPos].Element !=Key  )
     {
         CurrentPos += 2* ++CollisionNum -1;
         if(CurrentPos >= H -> TableSize)     CurrentPos -= H -> TableSize;
     }

     return CurrentPos;
}

使用平方探测散列表的插入：

void Insert(ElementType Key, HashTable H)
{
    Position Pos;
    
    Pos = Find(Key, H);
    if(H -> TheCells[Pos].Info != Legitmate)
    {
         H -> TheCells[Pos].Info = Legitmate;
         H -> TheCells[Pos].Element = Key;
    }
}

再散列：

HashTable Rehash(HashTable H)
{
    int i, OldSize;
    Cell *OldCells;
    
    OldCells = H -> TheCells;
    OldSize = H -> TableSize;

    H = InitializeTable(2*OldSize);

    for(i = 0; i <  OldSize; i++)
    {
        if(OldCells[i].Info == Legitmate)
               Insert(OldCells[i].Element, H);

    }
    free(OldCells);
    
    return H;
}

总结： 散列表有丰富的应用。编译器使用散列表跟踪源代码中声明的变量，符号表。游戏中的变换表。拼写纠错。

1。模型

2.一些简单实现

3.二叉堆

3.1结构性质

优先队列的声明

#ifndef _BINHEAP_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H); 
void Insert(ElementType X, PriorityQueue H);
ElementType DeleteMin(PriorityQueue H);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);

#endif

struct HeapStruct{
   int Capacity;
   int Size;
   ElementType *Elements;
};

3.2堆序性质

初始化优先队列：

PriorityQueue Initialize(int  MaxElements)
{
    PriorityQueue H;
    
    if(MaxElements < MinPQSize)  Error("PQ is too small!");
    
    H = malloc(sizeof(struct HeapStruct));
    if(H == NULL)     Error("Out of space!");
    
    H -> Elements = malloc((MaxElements + 1) * sizeof(ElementType));
    if(H -> Elements == NULL)  Error("Out of space");

    H -> Capacity = MaxElemets;
    H -> Size = 0;
    H -> Elements[0] = MinData;
   
    return H;
}

3.3基本的堆操作

插入过程：

void Insert(ElementType X, PriorityQueue H)
{
     int i;
     
     if(IsFull(H))
    {
           Error("PQ is Full");
           return;
    }
    
   for(i = ++ H-> Size; H -> Elements[i / 2] > X;  i /= 2)
         H -> Elements[i] =  H -> Elements[i / 2];

   H -> Elements[i] = X;
   
}

删除最小元：

ElementType DeleteMin(PriorityQueue H)
{
    int i, Child;
    ElementType MinElement, LastElement;
    
    if(IsEmpty(H)) 
   {
          Error("PQ is empty!");
          return H -> Elements[0];
   }    
   MinElement =  H -> Elements[1];
   LastElement = H -> Elements[H -> Size --];
   
   for(i = 1; i * 2  <= H -> Size; i = Child)
  {
      Child = i * 2;
      if(Child != H -> Size && H -> Elements[Child + 1] < Elements[Child])
           Child++;
      
     if(LastElement > H -> Elements[Child])
             H -> Elements[i] = H -> Elements[Child];
      else
          break;

     H -> Elements[i] = LastElement;
     
     return MinElement;
  }
}

3.4其他的堆操作

3.5优先队列的应用 1.选择问题 2.事件模拟

1.插入排序

void InsertionSort(ElementType A[], int N)
{
    int j, P;
    
   ElementType Tmp;

   for(P = 1; P < N; P++)
   {
       Tmp = A[P];
       for(j = P; j > 0 && A[j - 1] > Tmp ; j--)
            A[j] = A[j - 1];
       A[j] = Tmp;

   }
}

插入排序分析

一些简单排序算法的下界

2.希尔排序 希尔排序有时候也叫做缩小增量排序 希尔排序使用一个序列h1,h2,h3,....ht,叫做增量序列。 希尔排序的一个重要性质是，一个hk-排序的文件（此后将是h(k-1)-排序的）保持它的hk 排序性。 增量序列的一种流行（但是不好）的选择是使用shell建议的序列：ht = floor[N / 2]和hk = floor[h(k+1) / 2]. TIPS：t 和k和k-1，k+1都是下标.

void ShellSort(ElementType A[], int N)
{
    int i, j, Increment;
   ElementType Tmp;

   for(Increment = N / 2; Increment > 0; Inrement /= 2)
       for(i = Increment; i < N; i++)
       {
              Tmp = A[i];
              for(j = i; j >= Increment; j-= Increment)
                      if(Tmp < A[j - Increment])
                             A[j] = A[j - Increment];
                      else
                             break;
             A[j] = Tmp;
       }
}

希尔排序的最坏情形分析

使用希尔增量时希尔排序的最坏情形运行时间为Theta(N^2)。 使用Hibbard增量的希尔排序最坏情形运行时间为theta(N^(3 / 2))。 希尔排序的性能在实践中是可以完全接受的，即使是对于数以万计的N仍然如此。编程的简单特点使得它成为对适度大量的输入数据经常选用的算法。 堆排序 优先队列可以用于花费O(N log N)时间的排序。基于该想法的算法叫做堆排序 ，并给出我们至今所见到的最佳大O运行时间。然而，在实践中它却慢于使用Sedgewick增量序列的希尔排序。 该算法的主要问题是它使用了一个附加数组。因此存储需求增加一倍。将第二个数组拷贝回第一个数组的额外时间消耗只是O(N)，这不可能显著影响运行时间。避免使用第二个数组的聪明做法是利用这样一个事实：在每次DeleteMin之后，堆缩小了1.因此位于堆中最后的单元可以用来存放刚刚删去的元素。

#define LeftChild(i)  (2*(i) + 1)

void PercDown(ElementType A[], int i, int N)
{
     int Child;
     ElemenType Tmp;

     for(Tmp =  A[i]; LeftChild(i) < N; i = Child) 
    {
            Child =  LeftChild(i);
            if(Child != N -1 && A[Child + 1] > A[Child])
                 Child ++;
            if(Tmp < A[Child])
                A[i] = A[Child];
            else
                break;
    }
    A[i] = Tmp;


}


void HeapSort(ElemenType A[], int N)
{
     int i;
   
     for(i = N / 2; i >= 0; i--)
          PercDown(A, i, N);
     for(i = N - 1; i > 0; i--)
     {
           Swap(&A[0], &A[i]);
           PercDown(A, 0, i);
     }
}

堆排序的分析 堆排序是一个非常稳定的算法：它平均使用的比较只比最坏情形情况界指出的略少。然而直到最近，还没有人能够指出堆排序平均运行时间的非平凡界。 对于N个互异项的随机排列进行堆排序，所用的比较平均次数为2N log N - O(N log logN). 堆排序总是使用至少N log N - O(N)次比较，而且存在输入数据能够达到这个界。 归并排序 归并排序以O(N log N)最坏情形时间运行，而所使用的比较次数几乎是最优的。 这个算法中基本的操作是合并两个已排序的表。 基本的合并算法是取两个输入数组A和B，一个输入数组C，以及三个计数器Aptr，Bptr,Cptr,它们初始置于对应数组的开端。A[Aptr]和B[Bptr]中的较小者被拷贝到C中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完的时候，则将另一个表中剩余的部分拷贝到C中。 合并两个已排序的表的时间显然是线性的，最多进行了N - 1次比较，其中N是元素的总数。

//合并序列
void Merge(ElemenType A[], ElemenType TmpArray[], int Lpos, int Rpos, int RightEnd)
{
     int i, LeftEnd, NumElements, TmpPos;

     LeftEnd = Rpos - 1;
     TmpPos = Lpos;
     NumElements = RightEnd - Lpos + 1;

     while(Lpos <= Left && Rpos <= RightEnd)
    {
          if(A[Lpos] <= LeftEnd && Rpos <= RightEnd)
                 TmpArray[Tmp ++] = A[Lpos ++];
          else
                 TmpArray[TmpPos++] = A[Rpos ++];

    }

    while(Lpos <= LeftEnd)
          TmpArray[TmpPos++] = A[Lpos ++];
    while(Rpos <= RightEnd)
          TmpArray[TmpPos++] = A[Rpos ++];

    for(i = 0; i < NumElemenTypes; i++,RightEnd --)
          A[RightEnd] = TmpArray[RightEnd];
}



//分路
void MSort(ElemenType A[], ElemenType TmpArray[], int Left, int Right)
{
     int Center;

     if(Left < Right)
     {
            Center = (Left + Right) / 2;
            MSort(A, TmpArray, Left, Center);
            MSort(A, TmpArray, Center + 1, Right);
            Merge(A, TmpArray,Left,Center + 1, Right);
     }
}

//主排序入口
void MergeSort(ElemenType A[], int N)
{
    ElemenType *TmpArray;
    
    TmpArray = malloc(N * sizeof(ElemenType));
    if(TmpArray != NULL)
    {
          MSort(A, TmpArray, 0, N - 1);
          free(TmpArrary);
    }
    else
        Error("No Space for TmpArray!");

}

虽然归并排序的运行时间是O(N log N),但是它很难用于主存排序，主要问题在于合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加工作，其结果严重放慢了排序的速度。 3.快速排序 快速排序是在实践中最快的已知排序算法，它的平均时间是O(N log N)。该算法之所以特别快，主要是由于非常精炼的高度优化的内部循环。 基本由下列简单四个步骤组成： 1.如果S中元素个数是0或1，则返回 2.取S中任一元素v，称之为枢纽元（pivot） 3.将S - {v}（S中其余的元素）分成两个不相交的集合：S1 = {x ∈ S - {v} | x <= v}和S2 = {x ∈ S - {v} | x >= v} 4.返回{quicksort(S1)后，继续v，继而quicksort（S2）}。 选取枢纽元 一般是三数中值分割（随机一串数组，首位两端的元素相加除以2得到的值作为这个数组的索引取得的元素为枢纽元。） 小数组 对于很小的数组（N <= 20）,快速排序不如插入排序好。

#define Cutoff (3)

ElementType Median3(ElementType A[], int Left, int Right)
{
      int Center = (Left + Right) / 2;
      
      if(A[Left] > A[Center])
         Swap(&A[Left], &A[Center]);
      if(A[Left] > A[Right])
         Swap(&A[Left], &A[Right]);
      if(A[Center] > A[Right])
         Swap(&A[Center], &A[Right]);

      Swap(&A[Center], & A[Right - 1]);  //Hide pivot
      return A[Right - i];
}

void Qsort(ElementType A[], int Left, int Right)
{
       int i, j;
       ElemenType Pivot;
       
       if(Left + Cutoff <= Right)
       {
           Pivot = Median3(A, Left,Right);
           i = Left; j = Right - 1;
           for(;;)
           {
                while(A[++i] < Pivot){}
                while(A[--j] >  Pivot){}
                 if( i < j)
                    Swap(&A[i], &A[j]);
                 else
                    break; 
           }
           Swap(&A[i], &A[Right - 1]);

           Qsort(A, Left, i -1);
           Qsort(A, i + 1, Right);

       }
       else
            InsertSort(A + Left, Right - Left + 1);
}
void QuickSort(ElementType A[], int N)
{
     Qsort(A, 0, N - 1);
}

可以修改快速排序以解决选择问题 查找集合S中第k个最小元素的算法几乎与快速排序相同。 与快速排序相比，快速选择只做了一次递归调用而不是两次。快速选择的最坏情况和快速排序的相同，也是O(N^2)。但是使用三数中值选取枢纽元的方法使得最坏情况发生的机会几乎微不足道。

void Qselect(ElementType A[], int k, int Left, int Right)
{
       int i, j;
       ElemenType Pivot;
       
       if(Left + Cutoff <= Right)
       {
           Pivot = Median3(A, Left,Right);
           i = Left; j = Right - 1;
           for(;;)
           {
                while(A[++i] < Pivot){}
                while(A[--j] >  Pivot){}
                 if( i < j)
                    Swap(&A[i], &A[j]);
                 else
                    break; 
           }
           Swap(&A[i], &A[Right - 1]);
           
           if(k <= i)     Qselect(A, k, Left, i -1);
           else  if(k > i + 1)  Qselect(A, k, i + 1, Right);

         
       }
       else
            InsertSort(A + Left, Right - Left + 1);
}

大型结构的排序 我们常常需要通过关键字对大型结构进行排序。例如：工资名单，每个记录由电话，地址，姓名，电话号码等信息组成。如果真交换两个结构是非常昂贵的操作。在这种情况下，实际的解法是让输入数组包含指向结构的指针。我们通过比较指针指向的关键字，并在必要时交换指针来进行排序。这意味着，所有数据运动基本上就像我们对整数排序那样进行过，我们称之为间接排序。 排序的一般下界 归并排序和堆排序在一个常数因子范围内是最优的。 快速排序在相差一个常数因子的范围内平均是最优的。 只用到比较的任何排序算法在最坏情况下都需要upper(log(N!))次比较并平均需要log(N!)次比较。 令T是深度为d的二叉树，则T最多有2^d个树叶。 具有L片树叶的二叉树深度至少是upper(log L) 只使用元素间比较的任何排序算法在最坏情况下至少需要upper(log (N!))次比较 只使用元素间比较的任何排序算法需要进行Ω(N log N)次比较。 外部排序 因为输入的数据不能全部装进内存，所以要提出外部排序。 任何算法都将需要Ω(N^2)次磁带访问。 一般用多路合并。多相合并。 总结： 对于一般的内部排序应用程序，选用的方法不是插入排序，希尔排序，就是快速排序。如果需要对一些大型文件排序，快速排序是应该被选用的方法。合并时外部排序的中心思想。

等价关系

等价关系是满足下列三个性质的关系R：

动态等价性问题 TIPS: 给定一个等价关系"~".

基本数据结构

采纳Union(X,Y)后新的根是X的约定(可以自由定义)。 不相交集合的类型声明

#ifndef _DISJSET_H_

typedef int DisjSet[Number + 1];
typedef int SetType;
typedef int ElementType;

void Initialize(DisjSet S);
void SetUnion(DisjSet S, SetType Root1, SetType Root2);
SetType Find(ElemenType X, DisjSet S);

#endif

void Initialize(DisjSet S)
{
      int i;
      
      for(i = NumSets; i > 0; i--)
             S[i] = 0;
}


//Union例程（不是最好）
void SetUnion(DisjSet S, SetType Root1, SetType Root2)
{
      S[Root2] = Root1;
}

SetType Find(ElementType X, DisjSet S)
{
    if( S[X] <= 0 )
        return X;
    else
        return Find(S[X], S);
}

灵巧的求并算法 1.对以上的方法简单改进，是借助任意方法打破现有关系，使得总让较小的树成为较大的树的子树，这种方法称为按大小求并。如果这些Union都是按大小求并，那么任何节点的深度均不会超过log N。 2.按高度求并，同样保证所有树的深度最多是O(log N).我们跟踪每棵树的高度而不是大小并执行那些Union使得浅的树成为深的树的子树。。这是一种平缓的算法，因为只有当两颗相等的树求并时树的高度才增加（此时树的高度增1）。

// assume Root1 and Root2 are roots
void SetUnion(DisjSet S, SetType Root1, SetType Root2)
{
     if( S[Root2] < S[Root1])
           S[Root1] = Root2;
     else
     {
            if(S[Root1] == S[Root2])
                  S[Root1]--;
            S[Root2] = Root1;
     }
}

路径压缩

SetType Find(ElementType X, DisjSet S)
{
     if(S[X] <= 0)
        return X;
     else
         return S[X] = Find(S[X], S);
}

Union/Find的算法分析

若干定义

图的表示

拓扑排序

Dijistra算法（对于赋权图）

具有负边值的图

最小生成树 1.Prim算法 2.krushal算法 NP-完全性介绍

贪婪算法

huffman编码

跳跃表

素性测试 费马定律：

博弈问题 极大极小策略，alpha-beta裁剪。