Sean's Blog
0%

算法实现

发表于 更新于 分类于 ，

数据结构中部分算法的代码or伪代码实现

线性表

顺序表

存储

1
2
3
4
5
6
#define  MAXSIZE 100     //最大长度
typedef  struct 
{
 	ElemType  *elem;      //指向数据元素的基地址
  	int  length;                 //线性表的当前长度                        
 }SqList；

初始化

1
2
3
4
5
6
7
Status InitList_Sq(SqList &L)                   //构造一 个空的顺序表L
{
    L.elem= （ElemType*）malloc(MAXSIZE * sizeof(ElemType));   //为顺序表分配空间
    if(!L.elem) exit(OVERFLOW);           //存储分配失败
    L.length=0;				     //空表长度为0
    return OK;
}

取值

取第i个元素，随机存取。

1
2
3
4
5
6
7
int GetElem(SqList L,int i,ElemType &e)
{
  if (i<1||i>L.length) return ERROR;   
   //判断i值是否合理，若不合理，返回ERROR
  e=L.elem[i-1];   //第i-1的单元存储着第i个数据
  return OK;
}

查找

1
2
3
4
5
6
int LocateELem(SqList L,ElemType e)
{
  	for (i=0;i< L.length;i++)
      	if (L.elem[i]==e) return i+1;                
 	 return 0;
}

插入

1
2
3
4
5
6
7
8
9
10
11
Status ListInsert_Sq(SqList &L,int i ,ElemType e)
{
    if(i<1 || i>L.length+1) return ERROR;	         //i值不合法
    if(L.length==MAXSIZE) return ERROR;    //当前存储空间已满     
    for(j=L.length-1;j>=i-1;j--) 
        L.elem[j+1]=L.elem[j];    		//插入位置及之后的元素后移
    L.elem[i-1]=e;                     //将新元素e放入第i个位置
    ++L.length;		     	//表长增1
    return OK;
}

删除

1
2
3
4
5
6
7
8
Status ListDelete_Sq(SqList &L,int i)
{
   if((i<1)||(i>L.length)) return ERROR;	 //i值不合法
   for (j=i;j<=L.length-1;j++)                   
　  　L.elem[j-1]=L.elem[j];       //被删除元素之后的元素前移  
   --L.length;               	                 //表长减1
  return OK;
}

链表

存储

1
2
3
4
5
typedef struct Lnode
{
     ElemType   data;       //数据域
     struct LNode  *next;   //指针域
}LNode,*LinkList;

初始化

1
2
3
4
5
Status InitList_L(LinkList &L){ 
   L=new LNode;		//生成新结点作头结点.用头指针L指向头结点                 	
   L->next=NULL;　　//头结点的指针域置空　　　
   return OK; 
}

取值

1
2
3
4
5
6
7
8
9
Status GetElem_L(LinkList L,int i,ElemType &e){ 
    p=L->next;j=1; //初始化
     while(p&&j<i){	//向后扫描，直到p指向第i个元素或p为空 
       p=p->next; ++j; 
     } 
     if(!p || j>i)return ERROR; //第i个元素不存在 
     e=p->data; //取第i个元素 
     return OK; 
}//GetElem_L

查找

1
2
3
4
5
6
7
LNode *LocateELem_L (LinkList L，Elemtype e) {
 //返回L中值为e的数据元素的地址，查找失败返回NULL
  p=L->next;
  while(p &&p->data!=e)  
        p=p->next;                		
  return p; 	
}

插入

1
2
3
4
5
6
7
8
9
10
Status ListInsert_L(LinkList &L,int i,ElemType e){ 
     p=L;j=0; 
      while(p&&j<i−1){p=p->next;++j;}	//寻找第i−1个结点 
      if(!p||j>i−1)return ERROR;	//i大于表长 + 1或者小于1  
      s=new LNode;			//生成新结点s 
      s->data=e;      		           //将结点s的数据域置为e 
      s->next=p->next;	   	          //将结点s插入L中 
      p->next=s; 
      return OK; 
}//ListInsert_L

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
 Status ListDelete_L(LinkList &L,int i,ElemType &e){
    p=L;j=0; 
    while(p->next &&j<i-1){                  //寻找第i个结点，并令p指向其前驱 
        p=p->next; ++j; 
    } 
    if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 
    q=p->next;                                        //临时保存被删结点的地址以备释放 
    p->next=q->next; 	                  //改变删除结点前驱结点的指针域 
    e=q->data; 	                                //保存删除结点的数据域 
    delete q; 	                                //释放删除结点的空间 
 return OK; 
}//ListDelete_L

创建

  • 头插法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void CreateList_H(LinkList &L,int n){
        L=new LNode;
        L->next=NULL;	//先建立一个带头结点的单链表
        for(i=0;i<n;i++){
            p=new LNode;
            cin>>p->data;
            p->next=L->next;L->next=p;//插入到表头 
        }
    }

  • 尾插法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void CreateList_R(LinkList &L,int n){
        L=new LNode;
        L->next=NULL;
        r=L;		 //尾指针r指向头结点 
        for(i=0;i<n;i++){
            p=new LNode;
            cin>>p->data;
            p->next=NULL;r->next=p;//插入到表尾
            r=p;	 //r指向新的尾结点
        }
    }

双向链表

插入

1
2
3
4
5
6
7
8
9
10
Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
   if(!(p=GetElemP_DuL(L,i))) return ERROR;
   s=new DuLNode; 
   s->data=e;
   s->prior=p->prior;//1  
   p->prior->next=s;//2
   s->next=p;  //3
   p->prior=s;//4
   return OK;
}

删除

1
2
3
4
5
6
7
8
9
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e)
{
   if(!(p=GetElemP_DuL(L,i)))     return ERROR;
   e=p->data;
   p->prior->next=p->next;//1
   p->next->prior=p->prior;/
   delete p; 
   return OK;
}

栈和队列

栈

顺序栈

1
2
3
4
5
6
7
#define  MAXSIZE  100
typedef struct
{
		SElemType   *base;
		SElemType   *top;
		int stacksize;
}SqStack;

初始化

1
2
3
4
5
6
7
8
Status InitStack( SqStack &S )
{
	S.base =new SElemType[MAXSIZE]；
	if( !S.base ) 	return OVERFLOW;
	S.top = S.base;
	S.stackSize = MAXSIZE;
	return OK;
}

进出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status Push( SqStack &S, SElemType e)  
{
	if( S.top - S.base== S.stacksize ) // 栈满
        return ERROR; 	
	*S.top++=e;
	return OK;
}
Status Pop( SqStack &S, SElemType &e)  
{
	if( S.top == S.base ) // 栈空
        return ERROR; 	
	e＝ *--S.top;
	return OK;
}

取栈顶元素

1
2
3
4
5
6
Status GetTop( SqStack S, SElemType &e)  
{
	if( S.top == S.base )	 return ERROR; 	// 栈空
	e = *( S.top – 1 );
	return OK;
}

链栈

1
2
3
4
5
typedef  struct StackNode {
      SElemType  data;
      struct StackNode *next;
 } StackNode,  *LinkStack;
LinkStack S;

初始化

1
2
3
4
void InitStack(LinkStack &S )
{
	S=NULL;
}

进出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status Push(LinkStack &S , SElemType e)
{
    p=new StackNode;      //生成新结点p 
    if (!p) exit(OVERFLOW);
    p->data=e; 
    p->next=S; S=p; //将新结点插入到栈顶指针前，然后将新结点作为栈顶指针
    return OK; 
}
Status Pop (LinkStack &S,SElemType &e)
{
    if (S==NULL) return ERROR;
    e = S-> data;  p = S;   
    S =  S-> next;//栈顶指针指向下一个
    delete p;   return OK;
}

取栈顶元素

1
2
3
4
5
SElemType GetTop(LinkStack S)
{
    if (S==NULL) exit(1)；
    else return S–>data;
}

队列

循环队列

1
2
3
4
5
6
#define MAXQSIZE  100  //最大长度
Typedef struct {
   QElemType *base;  //初始化的动态分配存储空间
   int  front;            //头指针   
   int  rear;             //尾指针
}SqQueue;

初始化

1
2
3
4
5
6
Status InitQueue (SqQueue &Q){
    Q.base =new QElemType[MAXQSIZE] 
    if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}

求长度

1
2
3
int  QueueLength (SqQueue Q){
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;                             
 }

进出

1
2
3
4
5
6
7
8
9
10
11
12
Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
    Q.base[Q.rear]=e;//
    Q.rear=(Q.rear+1)%MAXQSIZE;//
    return OK;
}
Status DeQueue (LinkQueue &Q,QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   e=Q.base[Q.front];//
   Q.front=(Q.front+1)%MAXQSIZE;//
   return OK;
}

链队列

1
2
3
4
5
6
7
8
typedef struct QNode{
   QElemType   data;
   struct Qnode  *next;
}Qnode, *QueuePtr;
typedef struct {
   QueuePtr  front;            //队头指针   
   QueuePtr  rear;             //队尾指针
}LinkQueue;

初始化

1
2
3
4
5
6
Status InitQueue (LinkQueue &Q){
    Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); 
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;//
    return OK;
}

取队头

1
2
3
4
5
Status GetHead (LinkQueue Q, QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   e=Q.front->next->data;
   return OK;
}

进出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status EnQueue(LinkQueue &Q,QElemType e){
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e; p->next=NULL;//1
    Q.rear->next=p;//2
    Q.rear=p;//3
    return OK;
}
Status DeQueue (LinkQueue &Q,QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   p=Q.front->next;//
   e=p->data;//
   Q.front->next=p->next;//
   if(Q.rear==p) Q.rear=Q.front;
   delete p;
   return OK;
}

表达式求值

串&数组&广义表

BF算法

1
2
3
4
5
6
7
8
int  Index(Sstring S,Sstring T,int pos){
   i=pos;   j=1;
   while (i<=S[ 0 ] && j <=T[ 0 ]){
       if ( S[ i ]=T[ j ]) {++i;  ++j; }
       else{ i=i-j+2;    j=1; }//主串指针回到原开始比较的下一个，子串回到第一个位置。
   if ( j>T[ 0 ])   return   i－T[0];//返回值为S中与T匹配的子序列第一个字符的序号
   else return 0;
}

广义表的递归

树

二叉链表

1
2
3
4
5
typedef struct BiNode{
   TElemType   data;
   struct  BiNode   *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;

二叉树遍历

先中后遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Status PreOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     cout<<T->data; //访问根结点
     PreOrderTraverse(T->lchild); //递归遍历左子树
     PreOrderTraverse(T->rchild); //递归遍历右子树
    }
}
Status InOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     InOrderTraverse(T->lchild); //递归遍历左子树
  	 cout<<T->data; //访问根结点
     InOrderTraverse(T->rchild); //递归遍历右子树
    }
}
Status PostOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     PostOrderTraverse(T->lchild); //递归遍历左子树
     PostOrderTraverse(T->rchild); //递归遍历右子树
     cout<<T->data; //访问根结点
    }
}
//对应创建二叉树，如先序遍历创建
void CreateBiTree(BiTree &T）{
cin>>ch;
if (ch==’#’)   T=NULL;  	//递归结束，建空树
else{
    T=new BiTNode;    T-＞data=ch; 	//生成根结点
    CreateBiTree(T-＞lchild);  //递归创建左子树
    CreateBiTree(T-＞rchild); //递归创建右子树
  }									
}

计算二叉树结点总数

1
2
3
4
int NodeCount(BiTree T){
  	if(T == NULL ) return 0;  			    
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;//1
}

计算二叉树叶子结点总数

1
2
3
4
5
6
7
int LeadCount(BiTree T){
 	if(T==NULL) 	//如果是空树返回0
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1; //如果是叶子结点返回1
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}

计算二叉树的深度

1
2
3
4
5
6
7
8
9
int TreeDepth(BiTree T){
    int hl,hr,max;
    if(T){
        hl=TreeDepth(T->lchild);
        hr=TreeDepth(T->rchild);
        return max{hl,hr}+1;/
    }
    else return 0;
}

哈夫曼树

1
2
3
4
typedef  struct
{  int weight;
   int parent,lch,rch;
}*HTNode,*HuffmanTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void CreatHuffmanTree (HuffmanTree HT,int n){
    if(n<=1)return;
    m=2*n-1;
    HT=new HTNode[m+1];//0号单元未用，HT[m]表示根结点   
    for(i=1;i<=m;++i)//初始化
      {HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}
    for(i=1;i<=n;++i)cin>>HT[i].weight;  
    for( i=n+1;i<=m;++i)       //构造  Huffman树
     { //在HT[k](1≤k≤i-1)中选择两个其双亲域为0,且权值最小的结点,并返回它们在HT中的序号s1和s2
        Select(HT,i-1, s1, s2);    
        //s1,s2构造i结点
       	HT[s1].parent=i;   HT[s2].parent=i;//表示从F中删除s1,s2
       	HT[i].lch=s1;    HT[i].rch=s2 ;//s1,s2分别作为i的左右孩子
       	HT[i].weight=HT[s1].weight + HT[s2] .weight;//i 的权值为左右孩子权值之和
        }
    }
}

其他

求树的遍历，深度，转换镜像，判断对称，结点的前驱后继

图

存储

邻接矩阵

1
2
3
4
5
typedef struct{
    VerTexType vex[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum,arcnum;
}MGraph;

邻接表

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct ArcNode{
    int adjvex;			//该边所指向的顶点的位置
    struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{
    VerTexType data;
    ArcNode * firstarc;	//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];
typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}LGraph;

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 int LocateVex(MGraph G,VertexType u)
 {//存在则返回u在顶点表中的下标;否则返回-1
   int i;
   for(i=0;i<G.vexnum;++i)
     if(u==G.vexs[i])
       return i;
   return -1;
 }
Status CreateUDN(AMGraph &G){ 
    //采用邻接矩阵表示法，创建无向网G 
    cin>>G.vexnum>>G.arcnum; 	//输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i)    
      cin>>G.vexs[i];                        	//依次输入点的信息 
    for(i = 0; i<G.vexnum;++i) 	//初始化邻接矩阵，边的权值均置为极大值
       for(j = 0; j<G.vexnum;++j)   
         G.arcs[i][j] = MaxInt;   
    for(k = 0; k<G.arcnum;++k){        //////构造邻接矩阵 
      cin>>v1>>v2>>w;         //输入一条边依附的顶点及权值 
      i = LocateVex(G, v1); 
      j = LocateVex(G, v2);          //确定v1和v2在G中的位置
      G.arcs[i][j] = w;                   //边<v1, v2>的权值置为w 
      G.arcs[j][i] = G.arcs[i][j];    //置<v1, v2>的对称边<v2, v1>的权值为w 
   }//for 
   return OK; 
}//CreateUDN 
Status CreateUDG(ALGraph &G){ 
　//采用邻接表表示法，创建无向图G 
　cin>>G.vexnum>>G.arcnum;       //输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i){          //输入各点，构造表头结点表 
       cin>> G.vertices[i].data;           	//输入顶点值 
       G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL 
    }//for 
	for(k = 0; k<G.arcnum;++k){      //////输入各边，构造邻接表 
        cin>>v1>>v2;                 		//输入一条边依附的两个顶点 
        i = LocateVex(G, v1);  j = LocateVex(G, v2);    
        p1=new ArcNode;               			//生成一个新的边结点*p1 
        p1->adjvex=j;                   			//邻接点序号为j 
        p1->nextarc= G.vertices[i].firstarc;  G.vertices[i].firstarc=p1;  
        //将新结点*p1插入顶点vi的边表头部 
        p2=new ArcNode; //生成另一个对称的新的边结点*p2 
        p2->adjvex=i;                   			//邻接点序号为i 
        p2->nextarc= G.vertices[j].firstarc;  G.vertices[j].firstarc=p2;  
        //将新结点*p2插入顶点vj的边表头部 
    }//for 
    return OK; 
}//CreateUDG

遍历

深度优先

仿树的先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void DFS(AMGraph G,int v){
    cout<<v; visited[v]=true;
    for(w=0;w<G.vexnum;w++)	//依次检查邻接矩阵v所在的行
        //w是v的邻接点，如果w未访问，则递归调用DFS
        if((G.arcs[v][w]!=0)&&(!visited[w]))
   
            DFS(G,w);
}
void DFS(ALGraph G, int v){        //图G为邻接表类型 
    cout<<v;  visited[v] = true;          //访问第v个顶点
    p= G.vertices[v].firstarc;             //p指向v的边链表的第一个边结点 
    while(p!=NULL){              	      //边结点非空 
        w=p->adjvex;               	      //表示w是v的邻接点 
        if(!visited[w])  DFS(G, w); 	     //如果w未访问，则递归调用DFS 
        p=p->nextarc;                	     //p指向下一个边结点 
    } 
}

广度优先

仿树的层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
void BFS (Graph G, int v){ 
    //按广度优先非递归遍历连通图G 
    cout<<v; visited[v] = true;     		//访问第v个顶点
    InitQueue(Q);              			//辅助队列Q初始化，置空         
    EnQueue(Q, v);            			//v进队 
    while(!QueueEmpty(Q)){   		//队列非空 
       DeQueue(Q, u);        			//队头元素出队并置为u 
       for(w = FirstAdjVex(G, u); w>=0; w = NextAdjVex(G, u, w)) 
           if(!visited[w]){               	//w为u的尚未访问的邻接顶点 
               cout<<w; visited[w] = true;	EnQueue(Q, w); //w进队 
           }//if 
    }//while 
}//BFS

最短路径

  • Dijkstra
  • Floyd

最小生成树

  • Prim
  • Kruskal

查找

顺序查找

1
2
3
4
5
int Search_Seq(SSTable ST,KeyType key){
    ST.R[0].key=key;
    for(i=ST.length;ST.R[i].key!=key;--i);
    return i; //如果返回哨兵的地址表示查找失败，此时比较了n+1c
}

折半查找

1
2
3
4
5
6
7
8
9
10
11
int Search_Bin(SSTable ST,KeyType key)
{
    low=1;high=ST.length;       	
    while(low<=high){
        mid=(low+high)/2;	
        if(key==ST.R[mid].key) return mid; 
        else if(key<ST.R[mid].key) high=mid-1;///
        else low=mid+1;       /
    }
    return 0;	
}

递归算法？

二叉排序树

1
2
3
4
5
6
BSTree SearchBST(BSTree T,KeyType key) 
{
   if((!T) || key==T->data.key) return T;       	 
   else if (key<T->data.key)  return SearchBST(T->lchild,key);	//在左子树中继续查找
   else return SearchBST(T->rchild,key);    		   		//在右子树中继续查找
} // SearchBST

插入

除留余数法

排序

插入排序

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
void InsertSort(SqList ＆L)
 { int i,j;
   for(i=2;i<=L.length;++i)
     if( L.r[i].key<L.r[i-1].key)		//将L.r[i]插入有序子表
       {  L.r[0]=L.r[i]; 				// 复制为哨兵
          L.r[i]=L.r[i-1];
          for(j=i-2; L.r[0].key<L.r[j].key;--j)
	            L.r[j+1]=L.r[j]; 		// 记录后移 
          L.r[j+1]=L.r[0]; 				//插入到正确位置
       }
 }

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
void  BInsertSort ( SqList &L )
 { for ( i = 2;  i <= L.length ; ++i )
    {  L.r[0] = L.r[i]; low = 1 ; high = i-1 ;
       while ( low <= high )       
          {  	m = ( low + high ) / 2 ; 
             	if  (  L.r[0].key < L.r[m]. key  )  high = m -1 ;
           		else  low = m + 1; 
           }
       for ( j=i-1; j>=high+1; - - j ) L.r[j+1] = L.r[j];
       L.r[high+1] = L.r[0];
     }
  }  // BInsertSort

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void   ShellInsert(SqList &L，int dk) {
      
for(i=dk+1；i<=L.length； ++ i)
      if(r[i].key < r[i-dk].key) {         
         r[0]=r[i]；
         for(j=i-dk; j>0 &&(r[0].key<r[j].key); j=j-dk)
	           r[j+dk]=r[j]；
        r[j+dk]=r[0]；
       }
}
void   ShellSort(SqList &L，int dlta[ ]，int t){
        //按增量序列dlta[0…t-1]对顺序表L作Shell排序
   for(k=0；k<t；++k)
    　ShellInsert(L，dlta[k])；
　 　//增量为dlta[k]的一趟插入排序
}  // ShellSort

交换排序

起泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void bubble_sort(int arr[]) 			 
{	
    for(i=0;i<arr.len-1;i++)
        for(j=0;j<arr.len-1-i;j++)
            if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]);
}

//flag用来判断该趟是否发生交换，如果没有表示已经有序，提前终止
 void bubble_sort(SqList &R)
 { 
    int flag=1;		//flag标记某一趟排序是否发生交换
	for(i=1;i<n;i++){
		if(!flag) break;
		flag=0;		 //flag置为0, 本趟没有发生交换不执行下一趟
		for(j=1;j<n;j++){
			if(R[j].key>R[j+1].key){
				flag=1;			//flag置为1，本趟发生交换
				swap(R[j].key,R[j+1].key);
			}
        }
 }

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//一次划分
int Partition ( SqList &L,int low,int  high ) 
{  L.r[0] = L.r[low];   pivotkey = L.r[low].key;
   while  ( low < high ) 
    { //后前交替扫描，交换
       while ( low < high && L.r[high].key >= pivotkey )  --high;
       L.r[low] = L.r[high];			//将后面的小于枢纽值的移到前面
       while ( low < high && L.r[low].key <= pivotkey )  ++low;
       L.r[high] = L.r[low];			//将前面的小于枢纽值的移到后面
     }
    L.r[low]=L.r[0]; 					//此时low已经移到临界值，此时将枢纽值置入
    return low;
}

void QSort ( SqList &L,int low,int  high ) 
{  if  ( low < high ) 
    {  pivotloc = Partition(L, low, high ) ;
        Qsort (L, low, pivotloc-1) ; 	//左边的high=临界值-1
        Qsort (L, pivotloc+1, high ) 	//右边的low=临界值+1
     }
}

选择排序

简单选择排序

1
2
3
4
5
6
7
8
9
10
void SelectSort(SqList &K)
 { 
    for (i=1; i<L.length; ++i)
    { //在L.r[i..L.length] 中选择key最小的记录
        k=i;     
        for( j=i+1;j<=L.length ; j++)
            if ( L.r[j].key <L.r[k].key) k=j; 
        if(k!=i) swap(L.r[i],L.r[k]);            
    }  
}

堆排序