数据结构Final汇总

 AbstractDateType LinearList
 {  instances
    ordered finite collections of zero or more elements
    operations
 Create(); 
 Destroy();
 IsEmpty(); 
 Find(k,x); 
 Delete(k,x); 
 Output(out);
 Length();
 Search(x);
 Insert(k,x);
 }  

AbstractDataType Stack{
 instances
 list of elements;  one end is called the  bottom;  the other is the top;
 operations
 Create():Create an empty stack;
 IsEmpty():Return true if stack is empty,return  false otherwise
 IsFull ():Return true if stack if full,return false otherwise;
 Top():return top element of the stack;
 Add(x): add element x to the stack;
 Delete(x):Delete top element from stack and put it in x;
 

 public class StackLi 
{   public StackLi( ){ topOfStack = null; }
 public boolean isFull( ){ return false; }
 public boolean isEmpty( ){ return topOfStack = = null; }
 public void makeEmpty( ){ topOfStack = null; }
 public void push( object x )
 public object top( )
 public void pop( ) throws Underflow
 public object topAndPop( )
 private  ListNode  topOfStack;
 }
 

 public void push( object x )       
{  topOfStack = new ListNode( x, topOfStack );
 }
 public object top( )     
{  if( isEmpty( ) )
 return null;
 return topOfStack.element;
 }

public void pop( ) throws Underflow
 {  if( isEmpty( ) )      
throw new Underflow( );
 topOfStack = topOfStack.next;
 } 
public object topAndPop( )    
{  if( isEmpty( ) )
 return null;
 object topItem = topOfstack.element;
 topOfStack = topOfStack .next;
 return topItem;
 }

AbstractDataType Queue
 {
 instances
 ordered list of elements;one end is called the front; the other is the rear;
 operations
 Create(): Create an empty queue;
 IsEmpty(): Return true if queue is empty,return  false otherwise;
 IsFull(): return true if queue is full, return false  otherwise; 
First(): return first element of the queue;
 Last(): return last element of the queue;
 Add(x): add element x to the queue;
 Delete(x): delete front element from the queue  and put it in x;
 }

 Public class QueueAr
 {   
public QueueAr( )
 public QueueAr( int capacity )
 public boolean isEmpty( ){ return currentsize = = 0; }
 public boolean isfull( ){ return currentSize = = theArray.length; }
 public void makeEmpty( )
 public Object getfront( )
 public void enqueue( Object x ) throw Overflow
 private int increment( int x )
 private Object dequeue( )
 private Object [ ] theArray;
 private int currentSize;
 private int front;
 private int back;
 static final int DEFAULT_CAPACITY = 10;
 }

 template<class T>class LinkedQueue
 {  public:
 LinkedQueue(){front=back=0;}
 ~LinkedQueue();
 bool IsEmpty()const{return ((front)?false:true);}
 bool IsFull()const;
 T First()const;
 T Last()const;
 LinkedQueue<T>&Add(const T& x); 
LinkedQueue<T>& Delete(T& x);
 private:
 Node<T>*front;    Node<T>*back;
 };

class BinaryNode {
    BinaryNode(){Left=Right=0;}
    BinaryNode(Object e)
        {element=e; Left=Right=0;}
    BinaryNode(Object e,  BinaryNode l, BinaryNode r)
        {element=e;  Left=l;  Right=r; }
    Object element;
    BinaryNode left;//left subtree
    BinaryNode right;//right subtree
};

template<class T>class BinaryTree {
    public:
        BinaryTree(){root=0;};
        ~BinaryTree(){};
        bool IsEmpty()const
            {return ((root)?false:true);}
        bool Root(T& x)const;
        void MakeTree(const T& data, BinaryTree<T>& leftch, BinaryTree<T>& rightch);
        void BreakTree(T& data , BinaryTree<T>& leftch, BinaryTree<T>& rightch);
        void PreOrder(void(*visit)(BinaryNode<T>*u)) {PreOrder(visit, root);}
        void InOrder(void(*visit)(BinaryNode<T>*u)) {InOrder(visit, root);}
        void PostOrder (void(*visit)(BinaryNode<T>*u)) {PostOrder(visit, root);}
        void LevelOrder (void(*visit)(BinaryNode<T> *u));
    private:
        BinaryNode<T>* root;
        void PreOrder(void(*visit)(BinaryNode<T> *u),    BinaryNode<T>*t);
        void InOrder(void(*visit)(BinaryNode<T> *u),   BinaryNode<T>*t);
        void PostOrder(void(*visit) (BinaryNode<T> *u),  BinaryNode<T>*t);
};

//递归实现先序遍历
template<class T>
void PreOrder(BinaryNode<T>* t) {
    // preorder traversal of *t.
    if(t){
        visit(t);
        PreOrder(t->Left);
        PreOrder(t->Right);
    }
}

template<class T>
void InOrder(BinaryNode<T>* t) {
    if(t){
        InOrder(t->Left);
        visit(t);
        InOrder(t->Right);
    }
}
//非递归使用stack实现中序遍历
void Inorder(BinaryNode <T>*t){  
    Stack<BinaryNode<T>*> s(10);
    BinaryNode<T>*p = t;
    for (;;){
        //无条件进行循环
        while(p!=NULL){
            //一直进行压栈，直到最左下部分
            s.push(p);
            p = p->Left;
        }
        if(!s.IsEmpty()){
            //出栈输出，然后指向右子树，之后重复上面计算到右子树的最左边的节点。
            p = s.pop();
            cout << p->element;
            p = p->Right;
        }else
            return;
    }
}

template<class T>
void InOrder(BinaryNode<T>* t) {
    if(t){
        InOrder(t->Left);
        InOrder(t->Right);
        visit(t);
    }
}
//非递归实现后序遍历
//结点的实现
struct StkNode {
    BinaryNode <T> * ptr;
    int tag;//用来标记是否标记过了，第一次进栈为1，第二次进栈为2.
}
//非递归实现后序遍历
void Postorder(BinaryNode <T> * t) {
    Stack <StkNode<T>> s(10);
    StkNode<T> Cnode;
    BinaryNode<T>*p = t;
    for(;;) {
        //优先访问到最左下
        while (p!=NULL){
            Cnode.ptr = p;
            Cnode.tag = 0;
            s.push(Cnode);
            p = p->Left;
        }
        //将最左下结点出栈
        Cnode = s.pop();
        p = Cnode.ptr;
        while (Cnode.tag == 1)//从右子树回来 
        {
            //如果已经被访问一次了才进行输出
            cout << p->element;
            if (!s.IsEmpty()){
                Cnode = s.pop();
                p = Cnode.ptr;
            }else{
                //访问结束
                return;
            }   
        }
        Cnode.tag = 1;//从左子树遍历完，而右子树还没有动。
        s.push(Cnode);
        p = p->Right;//从左子树回来
    }//for
}      

void PostOrder(BiTree T){
	InitStack(S);
	p=T;
	r=NULL;
	while(p!=NULL||!IsEmpty(s)){
		if(p！=NULL){				//走到最左边 
			push(S,p);
			p=p->lchild;
		}
		else{				//向右
			GetTop(S,p);	//读栈顶节点（非出栈） 
			if(p->rchild&&p->rchild!=r){	//若右子树存在，且未被访问过 
				p=p->rchild;	//转向右 	
			}
			else{				//否则弹出结点并访问 
				pop(S,p);
				visit(p->data); //访问该结点
				r=p;			//记录最近访问的结点 
				p=NULL;			//结点访问完后，重置p指针
			}
		}
	}

template<class Type> 
ThreadNode<Type>* ThreadInorderIterator<Type>::First( )
 {
 while (current->leftThread= =0) current=current->leftchild;
 return current;
 }
 template<class Type>
 ThreadNode<Type>* ThreadInorderIterator<Type>::Next( )
 {
 ThreadNode<Type>* p=current->rightchild;
 if(current->rightThread= =0)
 while(p->leftThread= =0) p=p->leftchilld;
 current=p;
 return current;
 }
template<class Type> 
void ThreadInorderIterator<Type>:: Inorder( )
 {
 ThreadNode<Type> *p;
 for ( p=First( ); p!=NULL; p=Next( ))
 cout<< p->data<<endl;
 }

Void Inthread(threadNode<T> * T)
 {  stack <threadNode <T> *> s (10)
 ThreadNode <T>  * p = T ; ThreadNode <T> * pre = NULL;
 for (  ;  ;  )
 { 1.while (p!=NULL) 
{ s.push(p); p = p ->leftchild; }
 2.if (!s.IsEmpty( ))
 {  
 p = s.pop;
 if (pre != NULL)
 { if (pre ->rightchild = = NULL)
 { pre ->rightchild = p;  pre ->rightthread = 1;}
 if ( p -> leftchild = = NULL)
 { p -> leftchild = pre ; p ->leftthread = 1;  }
 }
 pre = p ; 
 p = p -> rightchild ;
 }
 else return;
 }//for
 }

public class BinarySearchTree {
    public BinarySearchTree(){ root = null; }
    public void makeEmpty(){ root = null; }
    public boolean isEmpty(){ return root == null;}
    
    public Comparable find( Comparable x )
    {return elementAt( find( x, root));}
    public Comparable findMin()
    {return elementAt( findMin( root ) );}
    public Comparable findMax()
    {return elementAt( findMax( root ) );
    public void insert( Comparable x )
    {root = insert(  x, root );}
    public void remove( Comparable x ) {root = remove( x, root ); }
    public void printTree()//都是外部接口
    
    private BinaryNode root;
    private Comparable elementAt( BinaryNode t ){ return t == null ? Null : t.element; }
    private BinaryNode find( Comparable x, BinaryNode t )
    private BinaryNode findMin( BinaryNode t )
    private BinaryNode findMax( BinaryNode t )
    private BinaryNode insert( Comparable x, BinaryNode t )
    private BinaryNode remove( Comparable x, BinaryNode t )
    private BinaryNode removeMin( BinaryNode t )
    private void printTree( BinaryNode t )
}
//查找某个元素的算法
private BinaryNode find( Comparable x, BinaryNode t ) {
    if( t == null )
        return null;
    if( x.compareTo( t.element ) < 0 )
        return find( x, t.left );
    else if( x.compareTo( t.element ) > 0 )
        return find( x, t.right );
    else
        return t;//Match 
}
//查找值最小的结点
//使用递归查找结点
private BinaryNode findMin( BinaryNode t ) {  
    if( t == null )
        return null;
    else if( t.left == null )
        return t;
    return findMin( t.left );
}
//迭代找最小结点
private BinaryNode findMin(BinaryNode t){
    if(t != null){
        while(t.left != null){
            t = t.left;
        }
    }
    return t;
}
//递归找到最大结点
private BinaryNode findMax( BinaryNode t){
    if(t == null){
        return null;
    }else if(t.right == null){
        return t;
    }
    return findMax(t.right);
}
//迭代找到最大结点
private BinaryNode findMax( BinaryNode t ) { 
    if( t != null )
        while( t.right != null )
            t = t.right;
    return t;
}
//将数值插入固定位置的算法
private BinaryNode insert( Comparable x, BinaryNode t ) {
    //先查找一次，如果找到了就不用进行查找
    if( t == null )
        t = new BinaryNode( x, null, null );
    else if( x.compareTo( t.element ) < 0 )
        t.left = insert( x, t.left );
    else if( x.compareTo( t.element ) > 0 )
        t.right = insert( x, t.right );
    else ;//duplicate; do nothing
    return t;
}

class AVLNode {
    AVLNode(Comparable theElement) {
        this( theElement, null, null);
    }
    AVLNode(Compalable theElement, AVLNode lt, AVLNode rt) {
        element = theElement;
        left = lt;
        right = rt;
        height = 0;
    }
    Comparable element;
    AVLNode left;
    AVLNode right;
    int height;
}
private static int height( AVLNode t ) {   
    return t =s= null ? –1 : t. height;
}

template<class T>class MaxHeap
{
    public:
        MaxHeap(int MaxHeapSize=10);
        ~MaxHeap(){delete[]heap;}
        int size()const{return CurrentSize;}
        T Max(){
            if (CurrentSize==0) throw OutOfBounds();
            return heap[1];
        }
        MaxHeap<T>&insert(const T&x); 
        MaxHeap<T>& DeleteMax(T& x);
        void initialize(T a[], int size,  int ArraySize);
    private:
        int CurrentSize, MaxSize;
        T * heap;
}

template<class T>MaxHeap<T>& MaxHeap<T>:: Insert(const T& x){
    if(CurrentSize= =MaxSize) throw NoMem(); 
    int i=++CurrentSize;
    while(i!=1&&x>heap[i/2]){
        //0不使用
        heap[i]=heap[i/2];
        //不必每次都进行完全交换
        i/=2;
    }
    heap[i]=x;
    return *this;
}

void down(int x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] > h[t]) t++;
    if (h[t] <= h[x]) break;
    std::swap(h[x], h[t]);
    x = t;
  }
}

void build_heap_2() {
  for (i = n; i >= 1; i--) down(i);
}

//simple tree solution to union-find problem 
//使用简单的树结构解决并集的查找问题
void Initialize(int n){
    parent=new int[n+1];
    for(int e=1;e<=n;e++) parent[e]=0;
}
int Find(int e) {
    //向上找到其根结点
    while(parent[e]) e=parent[e];
    return e;
}
void Union(int i, int j) {
    //合并两个结点
    parent[j]=i;
} 

public class DisjSets {
    public DisjSets( int numElements )
    public void union( int root1, int root2 )
    public int find( int x ) private int [] s;
}
//并查集的构造方法
public DisjSets( int numElements ) {
    s = new int [numElements];
    for( int i = 0; i < s.length; i++ )
        s[i] = -1; //一个根结点
}
//并查集的合并
public void union( int root1, int root2 ) {
    s[root2] = root1;
}
//并查集的查找，使用递归完成
public int find( int x ) {
    if( s[x] < 0 )
        return x;
    else
        return find( s[x] );
}

void Initialize(int n) {
    root=new bool[n+1];
    parent=new int[n+1];
    for(int e=1;e<=n;e++) {
        parent[e]=1;
        root[e]=true;
    }
}
int Find(int e) {
    while(!root[e])
        e=parent[e];
    return e;
}
void Union(int i, int j) {
    if(parent[i]<parent[j])
    //i becomes subtree of j
    {
        parent[j]=parent[j]+parent[i];
        root[i]=false;
        parent[i]=j;
    } else {
        parent[i]=parent[i]+parent[j];
        root[j]=false;
        parent[j]=i;
    }
}

AbstractDataType Graph {
    //instances 实例
        a set V of vertices and a set E of edges 顶点集合V 和 边集E
    //operations 操作
        Create(n):create an undirected graph with n vertices and no edges 创建一个n个顶点没有边的无向图
        Exist(i,j): return true if edge(i,j)exists; false otherwise 当且仅当存在边i、j的时候返回true
        Edges():return the number of edges in the graph 返回图的边的个数
        Vertices():return the number of vertices in the graph 返回图的顶点个数
        Add(i,j): add the edge(i,j) to the graph 将i、j边添加到图中
        Delete(i,j):delete the edge (i,j) 删除边i、j 
        Degree(i): return the degree of vertex i 返回顶点i的度数
        InDegree(i): synonym for degree 和度数相同
        OutDegree(i): synonym for degree 和度数相同
  }

const int MaxNumEdges = 50// 最大边数
const int MaxNumVertices = 10//最大顶点数 
template<class NameType, class DistType> class Graph{
    private:
        SeqList<NameType> VerticesList(MaxNumVertices) //顶点表
        DistType Edge [MaxNumVertices] [MaxNumVertices]  //邻接矩阵，一定是方阵
        int CurrentEdges;//当前边数
        int FindVertex (Seqlist <NameType> &L; const  NameType &Vertex)
            {return L.Find(Vertex);}
        int GetVertexPos (const NameTyoe &Vertex)
            {return FindVertex(VerticesList);}// 给出了顶点Vertex在图中的位置
    public:
        Graph (const int sz=MaxNumEdges); 
        int GraphEmpty() const{return VerticesList.IsEmpty();}
        int GraphFull() const{return VerticesList.IsFull() || CurrentEdges= =MaxNumEdges;}

        int NumberofVertices(){return VerticesList.last;}
        int NumberofEdges() {return CurrentEdges;}
        NameType Getvalue(const int i) {return  i>=0 && i<VerticesList.last ? VerticesList.data[i] :  NULL;} 
        DistType Getweight (const int v1,const int v2);
        
        int GetFirstNeighbor(const int v); 
        int GetNextNeighbor(const int v1,const int v2);
        
        void InsertVertex(const NameType & Vertex);
        void InsertEdge(const int v1,const int v2, DistType weight);
        void removeVertex(const int v);
        void removeEdge(cosnt int v1,const int v2);
} 

template<class NameType, class DistType> int Graph<NameType, DistType>::GetFirstNeighbor(int v) {
    if (v!=-1) {
        for(int col=0; col<CurrentVertices; col++)
            if (Edge[v][col]>0 && Edge[v][col]<max)
                return col;
    }
    return -1;
}

//利用的是邻接矩阵来表示的图
//主过程:
template<NameType,DistType> void Graph<NameType,DistType>::DFS( ) {
    int *visited=new int[NumVertices];
    for ( int i=0; i<NumVertices; i++)
        visited[i]=0;
        DFS(0,visited);//从顶点0开始深度优先搜索
        delete[] visited;//释放visited的空间
    }
//子过程
template<NameType,DistType> void Graph<NameType,DistType>::DFS(int v, visited[]) {
    cout<<GetValue(v)<<"";
    visited[v]=1;
    int w = GetFirstNeighbor(v);
    while (w!=-1) {
        if(!visited[w])
            DFS(w,visited);//最坏情况，就是每一次w都没有被访问过
        w = GetNextNeighbor(v,w);
    }
    //无论如何，最坏情况下访问次数，也就只能是图中所有边的个数。
    //也就是对邻接矩阵所有边会被扫一遍
}

template<NameType,DistType> void Graph<NameType,DistType>::BFS(int v) {
    //这个算法使用了队列
    int* visited=new int[NumVertices];
    for (int i=0; i<NumVertices; i++)
        visited[i]=0;
    cout << GetValue(v) << "";

    //访问结点
    visited[v]=1;

    //使用队列来存储顶点
    queue<int> q;
    q.EnQueue(v);
    while(!q.IsEmpty()) {
        v= q.DeQueue();
        int w= GetFirstNeighbor(v);
        while (w!=-1) {
            if(!visited[w]) {
                cout<<GetValue(w)<<""; 
                visited[w]=1;
                q.EnQueue(w);
            }
            w= GetNextNeighbor(v,w);
            //访问完成一层的结点
        }
    }
    delete[] visited;
}

void Graph<string,float>::Kruskal(MinSpanTree&T) {
    //结果赋值给T
    MSTEdgeNode e;
    MinHeap<MSTEdgeNode>H(currentEdges);
    int NumVertices=VerticesList.Last , u , v ;
    Ufsets F(NumVertices);//建立n个单元素的连通分量
    for(u=0;u<NumVertices;u++)
        for (v=u+1;v<NumVertices;v++)
            if(Edge[u][v]!=MAXINT) {
                e.tail=u;
                e.head=v;
                e.cost=Edge[u][v];
                H.insert(e);
                //完成堆的初始化，将每一条边插入到优先级队列中去
            }
    int count=1;//生成树边计数
    while(count<NumVertices) {
        H.RemoveMin(e);
        u=F.Find(e.tail);//找到并查集的树根
        v=F.Find(e.head);//找到并查集的树根
        if(u!=v){
            //并查集做回边检测，在同一个并查集中就是一个回边，不然就不是
            F.union(u,v);
            T.Insert(e);
            count++;//计数已经查找出来的个数
        }
        //最坏的情况时所有的边都被访问一次，比如目标边是最后一条边。
    }
}

//Another version of insertion sort
public static void InsertionSort(int []a, int n) {
    for(int i=0;i<n;i++){
        //insert a[i] into a[0:n-1]
        int t=a[i];
        int j;
        for(j=i-1; j>=0&&t<a[j]; j--)
            a[j+1]=a[j];
        a[j+1]=t;
        //比前面大后推一格
    }
}

//java
public static int binarySearch( Comparable [] a, Comparable x ) {
    int low = 0, high = a.length - 1;
    while( low <= high ) {
        //计算出中点是哪一个
        int mid = (low+high) / 2;
        //调整两端的值
        if( a[mid].compareTo(x) < 0)
            low = mid + 1; 
        else if(a[mid ].compareTo(x) > 0)
            high = mid – 1;
        else  return mid;
    }
    return "NOT-FOUND";
}

public static void shellsort( Comparable [ ] a ) {
    for (int gap = a.length/2 ; gap>0 ; gap/=2 )
        for (int i = gap; i < a.length; i++) {
            //遍历一遍
            Comparable tmp = a[i];
            int j = i;
            for (;j >= gap && tmp.compareTo( a[j-gap] )< 0;j -= gap )
                //完成一遍下滤
                a[j] = a[j – gap];
            a[j] = tmp;
    }
}

//java
public static void Bubble( int [ ] a , int n) {
    //Bubble largest element in a[0:n-1] to right 
    for(int i=0; i<n-1; i++) 
        if(a[i] > a[i+1])
            swap(a[i],a[i+1]);
    }
public static void BubbleSort( int [ ] a, int n) {  
    //Sort a[0:n-1] using a bubble sort 
    for(int i=n ;i>1; i--) 
        Bubble(a,i); 
}

//c++
template <class Type> void QuickSort( datalist <Type>& list, const int left,  const int right ) {
    if (left<right) {
        int pivotpos = partition(list, left, right);
        QuickSort(list, left, pivotpos-1);
        QuickSort(list, pivotpos+1, right);
    }
}
//partition
template <class Type> int partition(datalist<Type> &list, const int low, const int high) {
    int i=low,j=high;  Element<Type>pivot=list.Vector[low];
    while (i != j ) {
        while(list.Vector[j].getkey()>pivot.getkey( ) && i<j)
            j--;
        if (i<j) {
            list.Vector[i]=list.Vector[j];
            i++;
        }
        while(list.Vector[i].getkey()<pivot.getkey( ) && i<j)
            i++;
        if (i<j) {
            list.Vector[j]=list.Vector[i];
            j--;
        }
    }
    list.Vector[i]=pivot;
    return i;
}

//java
public static void SelectionSort(int [] a, int n) {
    //sort the n number in a[0:n-1].
    //找到大数字放置到后面
    for(int size = n; size>1; size--){
        //n-1
        int j = Max(a,size);
        //n-1+n-2+...+1
        swap(a[j],a[size-1]);
    }
} 

//java program
public static void heapsort( Comparable []a) {
    for( int i = a.length / 2; i >= 0; i-- )
        percDown( a, i, a.length );
    for( int i = a.length – 1; i > 0; i-- ) {
        swapReferences( a, 0, i );
        percDown( a, 0, i);
    }
}
private static int leftChild( int i ) {   
    return 2 * i + 1;
}
private static void percDown( Comparable [ ] a, int  i,  int n ) {
    int child;
    Comparable tmp;
    for( tmp = a[i];leftChild(i) < n ; i = child ) {
        child = leftchild( i );
        if( child!=n – 1&& a[child].compareTo( a[ child + 1 ] ) < 0 )
            child ++;
        if( tmp . compareTo( a[ child ] < 0 )
            a[ i ] = a[ child ];
        else
            break;
    }
    a[i] = tmp;
}

public static void Rank( int [] a, int n, int [] r) {
    //Rank the n elements a[0:n-1]
    for(int i=0;i<n;i++){
        r[i]=0;
    }
    //首先将全部的数字重置为0
    for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
            if(a[j]<=a[i])
                r[i]++;
            else
                r[j]++;
            //胜者排名不需要向后增加，而败者需要增加次序。
}
public static void Rearrange( int [ ]a, int n, int[ ] r) {
    //In-place rearrangement into sorted order
    for(int i=0;i<n;i++)
        while(r[i]!=i) {
            //在数组[n]上的应该是第n+1大的数字
            int t=r[i];
            swap(a[i],a[t]);
            swap(r[i],r[t]);
        }
}

//java
public static void mergeSort( Comparable [ ] a ) {
    Comparable [ ] tmpArray = new Comparable[a.length];
    mergeSort( a, tmpArray, 0, a.length – 1 );
}                            
private static void mergeSort( Comparable [ ] a, Comparable [] tmpArray, int left, int right ) {
    if( left < right ) {
        int center = ( left + right ) / 2;
        mergeSort(a, tmparray, left, center );
        mergeSort(a, tmpArray, center + 1, right );
        merge( a, tmpArray, left, center + 1, right );
    }
}
private static void merge( Comparable [ ] a, Comparable [] tmpArray, int leftPos, int rightPos, int rightEnd ) {
    int leftEnd = rightPos – 1;
    int tmpPos = leftPos;
    int numElements = rightEnd – leftPos + 1;
    while( leftPos <= leftEnd && rightPos <= rightEnd )
        if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        else
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];
    while( leftPos <= leftEnd )
        tmpArray[ tmpPos++ ] = a[ leftPos++ ];
    while( rightpos <= rightEnd)
        tmpArray[ tmpPos++] = a[ rightpos++ ];
    for( int i = 0; i < numElements; i++, rightEnd-- )
        a[ rightEnd ] = tmpArray[ rightEnd ];
}