实验一，线性表、链接存储

• 编写程序，完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。

#include <stdio.h>
#include <iostream>
using namespace std;

struct Node{
    int element;
    Node *link;
};

struct HeaderList{
    Node *head;
    int n;
};

// 1、初始化
void Init(HeaderList *L){
    L->head=(Node*)malloc(sizeof(Node));
    L->head->link=NULL;
    L->n=0;
}

// 2、查找运算，时间复杂度:O（n） 
int Find (HeaderList *L, int i){
    if(i<0 || i>L->n-1) return -1;
    Node *p = L->head;
    for (int j=0;j<i;j++){
        p=p->link;  
    }
    int x=p->element; 
    return x;
}

// 3、插入运算，时间复杂度:O（n） 
void Insert (HeaderList *L, int i, int x){ 
    if (i<0 || i>L->n-1)    return;
    Node *p = L->head;
    for(int j=0;j<=i;j++)   p=p->link;
    Node *q=(Node*)malloc(sizeof(Node));
    q->link=p->link;
    p->link=q;
    L->n++;
}

// 4、删除运算，时间复杂度:O（n）    
void Delete(HeaderList *L, int i){ 
    if (!L->n)  return;
    if (i<0 || i>L->n-1)    return; 
    Node *p=L->head;
    for(int j=0; j<=i-1; j++)   p=p->link;
    Node *q=(Node*)malloc(sizeof(Node));
    q=p->link;
    p->link=q->link;
    free(p);
    L->n--;
}

// 5、撤销操作   
void Destroy(HeaderList *L){ 
    Node *p;
    while(L->head){
        p=L->head->link;
        free(L->head);
        L->head=p;
    }
}

// 6、输出操作 
void Output(HeaderList *L){
    Node *p=L->head;
    cout<<"element: " ; 
    if (!L->n){
        cout<<"\n"; 
        return;
    }
    do{
        cout<<p->element<<"  ";
        p = p->link;
    }while (p!= NULL);
    cout<<endl;
}

实验二，二叉树、哈夫曼编码

• 编写程序，完成二叉树的先序创建、先序、中序、后序遍历等操作。
• 编写程序，实现求二叉树结点个数、叶结点个数、二叉树的高度以及交换二叉树所有左右子树的操作。
• 编写程序，实现哈夫曼树的创建、哈夫曼编码以及解码的实现。

#include<stdio.h>
#include <iostream>
using namespace std; 

struct Tree{ //链表存储表示 
    int a;
    struct Tree *r;      
    struct Tree *l;   
};      
             
struct Tree *CreateTree(){ //先序构建二叉树 
    struct Tree *p;      
    int x;  cin>>x;    
    if(x==0)          
        p=NULL;
    else{
        p=(struct Tree *)malloc(sizeof(struct Tree));
        p->a=x;                
        p->l=CreateTree();      
        p->r=CreateTree();      
   }
   return p;         
}

void PreOrder(struct Tree *p){ //先序遍历 
    if(p){
        cout<<p->a; 
        PreOrder(p->l);
        PreOrder(p->r);
    }
}
void InfixOrder(struct Tree *p){ //中序遍历 
    if(p){
        InfixOrder(p->l);
        cout<<p->a; 
        InfixOrder(p->r);
    }
}
void PostOrder(struct Tree  *p){ //后序遍历 
    if(p){
        PostOrder(p->l);
        PostOrder(p->r);
        cout<<p->a;
    }
}

// 1、二叉树结点个数 
int sumnode = 0;
void SumNode(Tree *p){
    if (p){
        if(p->l)
            SumNode(p->l);
        if(p->r)
            SumNode(p->r);
        sumnode++;
    }
}

// 2、叶子结点个数
int SumLeaf(Tree *p){
    int m,n;
    if(!p) 
        return 0;
    if(!p->l && !p->r)          
        return 1;
    else{
        m = SumLeaf(p->l);
        n = SumLeaf(p->r);
        return m+n;
    }
}

// 3、二叉树的高度
int Height(Tree *p){
    if(p){  
       int lheight = Height(p->l); 
       int rheight = Height(p->r); 
       return (rheight>lheight) ? lheight+1:rheight+1;
   } 
}  

// 4、交换左右子树
void Exchange(Tree *p){
    Tree *temp = NULL;
    temp = p->l;
    p->l = p->r;
    p->r = temp;
    if(p->l)
        Exchange(p->l);
    if(p->r)
        Exchange(p->r);
}

int main(){
    struct Tree *p;
    cout<<"\n先序构建二叉树："; p=CreateTree();
    cout<<"\n先序遍历：";    PreOrder(p);
    cout<<"\n中序遍历：";    InfixOrder(p);
    cout<<"\n后序遍历：";    PostOrder(p); 
    cout<<"\n树的结点个数：";  SumNode(p); cout<<sumnode;
    cout<<"\n叶子结点个数：";  cout<<SumLeaf(p);
    cout<<"\n二叉树的高度：";  cout<<Height(p);
    cout<<"\n交换左右子树：";  Exchange(p);    PreOrder(p);
    return 0;
} 

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define MAX 20 
 
struct node{ //树节点
    char val;
    int weigh;
    struct node *p, *l, *r; 
        
}; 
struct lnode{ //链表节点
    node *ln;   
    struct lnode *llink;
    struct lnode *rlink;
};
struct Tree{ //树头结点
    node *head; 
};
struct list{ //链表头
    lnode *head;    
};
 
char S[ MAX ]; //字符串数组
int w[ MAX ]; //权重数组
 
void Sort(char *s, int low, int high){ //1、对字符串进行排序 
    char s1=s[low];
    int i = low;
    int j = high;
    while(i<j){
        while(i<j && s[j]>=s1) 
            j--;
        if(i<j) 
            s[i++]=s[j];
        while(i<j && s[i]<=s1) 
            i++;
        if(i<j) 
            s[j]=s[i];
    }   
    s[i]=s1;
    if((i-1)>low)
        Sort(s,low,i-1);
    if((i+1)<high)
        Sort(s,i+1,high);
}
void GetWeigh(char *ch,int s){ //2、得到有效字符和对应权重
    char a=ch[0];
    int i=0,j=0;
    while(i<s){
        if(ch[i]==a){           
            w[j]++;
            i++;    
        }   
        else{
            S[j]=a;
            j++;
            a=ch[i];
        }       
    }
    S[j]=a; 
}

void AddList(list *l,node *x){ //3、向链表中添加结点 
    lnode *n=l->head;
    lnode *y=(lnode*)malloc(sizeof(lnode));
    y->llink = y->rlink = NULL;
    y->ln=x;    
    if(l->head->rlink==NULL){
        l->head->rlink=y;
        y->llink=l->head;   
        return;
    } 
    while(n->rlink!=NULL){
        if(n->rlink->ln->weigh > x->weigh){
            y->llink = n->rlink->llink;
            y->rlink = n->rlink;
            n->rlink=y;
            y->rlink->llink=y;
            n=n->rlink;
            break;
        }
        else {  
            n=n->rlink;
        }
    }
    if(n->rlink==NULL){
        n->rlink=y;
        y->llink=n;
    }
}
 
void OutPut1(list *l){ //4、打印链表；
    lnode *lx=l->head->rlink;
    while(lx!=NULL){
        printf("val= %c ,weigh= %d \n",lx->ln->val,lx->ln->weigh);  
        lx=lx->rlink;
    }   
}

void DeleteNode(list *l,lnode *p){
    lnode *lx=l->head->rlink;
    while(lx!=NULL){
        if(lx == p){
            if(lx->rlink == NULL){
                l->head->rlink=NULL;
                free(p);
            }
            else{
                lx->llink->rlink=lx->rlink;
                lx->rlink->llink=lx->llink;
                node *s=p->ln;
                free (p);
            }
            break;
        }
        lx=lx->rlink;
    }
}

void CreateTree(Tree *hr, list *l){ //5、创建哈夫曼树
        node *hx=hr->head;
        lnode *lx=l->head->rlink;
        while(lx!=NULL && lx->rlink!=NULL){
            node *x=(node*)malloc(sizeof(node));
            x->val='\0';
            x->weigh = lx->ln->weigh + lx->rlink->ln->weigh;
            x->l=lx->ln;
            x->r=lx->rlink->ln;
            x->p=NULL;
            
            lx->ln->p=x;
            lx->rlink->ln->p=x;
            DeleteNode(l,lx);
            DeleteNode(l,lx->rlink);
            AddList(l,x);
            lx=l->head->rlink;
        }
        if(l->head->rlink != NULL)
            hr->head=l->head->rlink->ln;
}

void reverse(char *p){ //反转字符串
    int l=strlen(p);
    int i=0;
    for(i;i<l-i;i++){
        char t;
        t=p[i];
        p[i]=p[l-i-1];
        p[l-i-1]=t;
    }   
}
 
void OutPut2( node *n){ //6、遍历哈夫曼树
    node *x=n;
    if(x!=NULL){
        OutPut2(x->r);
        OutPut2(x->l);
        node *sn=x;
        if(x->val != '\0'){
            printf("%c  ",x->val);
            char p[10]={};
            int i=0;
            while(sn->p != NULL){
                if(sn->p->l==sn){
                    p[i]='0';
                    i++;
                }
                if(sn->p->r==sn){
                    p[i]='1';
                    i++;    
                }
                sn=sn->p;   
            }
            reverse(p);
            cout<<p<<"\n";
        }
    }       
}
 
int main(int argv,char **argc){
    Tree h;
    list l; 
    h.head=(node*)malloc(sizeof(node));
    h.head->p = h.head->l = h.head->r = NULL;
    l.head=(lnode*)malloc(sizeof(lnode));
    l.head->rlink = l.head->llink = NULL;
    
    int i=0;
    strcpy(S,"ksajcbksjacbiudghckjdvbjdcbidhcoiwhcwoiwh");
    Sort(S,0,strlen(S)-1);
    GetWeigh(S,strlen(S));

    for(i=0; w[i]!=0; i++){ //创建有序链表
        node *x=(node*)malloc(sizeof(node));
        x->val=S[i];
        x->weigh=w[i];
        x->p = x->l = x->r = NULL;
        AddList(&l,x); 
    }
    OutPut1(&l);
    CreateTree(&h,&l);
    OutPut2(h.head);
    return 0;
}

实验三，邻接矩阵、邻接表

• 编写程序，完成邻接矩阵的初始化、撤销、边的搜索、插入、删除等操作。
• 以邻接矩阵为存储结构，编写程序，实现图的深度、宽度优先遍历。
• 编写程序，完成邻接表的初始化、撤销、边的搜索、插入、删除等操作。
• 以邻接表为存储结构，编写程序，实现图的深度、宽度优先遍历。

#include<stdio.h>
#include<windows.h>

typedef struct{
    int **a;     //邻接矩阵
    int n;       //图的顶点数
    int e;       //图的边数
}mGraph;

void Init(mGraph *mg,int nSize){
    int i,j;
    mg->n = nSize;               
    mg->e = 0;                      
    mg->a = (int**)malloc(nSize*sizeof(int *));  
    for(i=0; i<mg->n; i++){ //初始化权重为-1
        mg->a[i] = (int*)malloc(nSize*sizeof(int));
        for(j = 0;j < mg->n;j ++){ 
            mg->a[i][j] = -1;  
        }
        mg->a[i][i] = 0; //自回路设置为0
    }
}
 
void Insert(mGraph *mg,int u,int v,int w){
    if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v) return; //错误输入
    if(mg->a[u][v] != -1) return; //边已存在 
    mg->a[u][v] = w; //插入新边
    mg->e ++;  
}

int Exist(mGraph *mg,int u,int v){
    if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v) return 0; //错误输入
    if(mg->a[u][v] == -1) return 0; //边不存在 
    return 1;
}

int Remove(mGraph *mg,int u,int v){
    if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v) return 0; //错误输入
    if(mg->a[u][v] == -1) return 1; //边不存在 
    mg->a[u][v] = -1; //删除边
    mg->e--;
    return 1;
}

int Destory(mGraph *mg){
    int i;
    for(i=0; i<mg->n; i++){
        free(mg->a[i]);  
    }
    free(mg->a);         
}

typedef struct{
    int front;
    int rear;
    int maxSize; 
    int *element;
}Queue;

//初始化一个空队列 
void Create(Queue *Q,int mSize){
    Q->maxSize=mSize;
    Q->element=(int*)malloc(sizeof(int)*mSize);
    Q->front=Q->rear=0;
}
 
//判断队列是否为空
BOOL IsEmpty(Queue *Q){
    return Q->front==Q->rear;
}
 
//判断队列是否已满
BOOL IsFULL(Queue *Q){
    return (Q->rear+1)%(Q->maxSize)==Q->front;
}
 
//获取队头元素 
void Front(Queue *Q,int *x){
    if(IsEmpty(Q)) return;
    *x=Q->element[(Q->front+1)%(Q->maxSize)];
}
 
//队尾插入元素
BOOL EnQueue(Queue *Q,int x){
    if(IsFULL(Q)) return 0;
    Q->rear=(Q->rear+1)%(Q->maxSize); 
    Q->element[Q->rear]=x;
    return 1;
}
 
//删除队头元素
BOOL DeQueue(Queue *Q){
    if(IsEmpty(Q)) return 0;
    Q->front=(Q->front+1)%(Q->maxSize);
    return TRUE;
}

//单一顶点 DFS
void DFS(int i,int visited[],mGraph g){
    printf("%d ",i);              
    visited[i] = 1;               //修改访问标记       
    for(int j=0; j<g.n; j++){     //遍历邻接点
        if(!visited[j] && g.a[i][j]){  //若未被访问且有权值
            DFS(j,visited,g);
        }
    }
}
 
//全图 DFS
void DFSGraph(mGraph g){
    int *visited = (int*)malloc(g.n*sizeof(int)); //访问标记 
    for(int i=0; i<g.n; i++){
        visited[i] = 0;        
    }                           
    for(int i=0; i<g.n; i++){    
        if(!visited[i]){ //若未被访问
            DFS(i,visited,g);
        }
    }                      
    free(visited);                    
}
 
//单一顶点 BFS
void BFS(int i,int visited[],mGraph g){
    Queue q;
    Create(&q,g.n);  
    visited[i] = 1;   
    printf("%d ",i);                                                                
    EnQueue(&q,i); //入队操作 
    while(!IsEmpty(&q)){
        Front(&q,&i); //队头元素                     
        DeQueue(&q); //出队操作 
        for(int j=0; j<g.n; j++){      
            if(!visited[j] && g.a[i][j]>0){ //若未被访问且有权值
                visited[j] = 1;
                printf("%d ",j);
                EnQueue(&q,j); //入队操作 
            }
        }
    }
}
 
//全图 BFS
void BFSGraph(mGraph g){
    int *visited = (int*)malloc(g.n*sizeof(int)); //访问标记 
    for(int i=0; i<g.n; i++){ 
        visited[i] = 0;
    }
    for(int i=0; i<g.n; i++){                      
        if(!visited[i]){ //若未被访问
            BFS(i,visited,g);
        }
    }
    free(visited);
}
 
int main(){
    mGraph g;
    int nSize,edge,u,v,i,j,w;
    printf("\n  Please enter the size of the mgraph:"); scanf("%d",&nSize);
    //1、邻接矩阵的初始化
    Init(&g,nSize); 
    printf("    Please enter the number of the edges:"); scanf("%d",&edge);
    //2、邻接矩阵边的插入
    for(i = 0;i < edge;i ++){ 
        printf("    Please enter the edge:"); scanf("%d%d%d",&u,&v,&w);
        Insert(&g,u,v,w);
    }
    //6、深度优先遍历 DFS
    printf("    DFS:"); DFSGraph(g);
    //7、宽度优先遍历 BFS
    printf("\n  BFS:"); BFSGraph(g);
    printf("\n  Please enter the deleted edge:"); scanf("%d%d",&u,&v);
    //3、邻接矩阵边的搜索
    if(Exist(&g,u,v)) printf("  Succeed to search to the edge.\n");
    else printf("   Failed to search to the edge.\n");
    //4、邻接矩阵边的删除 
    if(Remove(&g,u,v)) printf(" Succeed to delete the edge.\n");
    else printf("   Failed to delete the edge.\n");
    //5、邻接矩阵撤销操作 
    if(Destory(&g)) printf("    Succeed to remove the matrix.\n");
    else printf("   Failed to remove the matrix.\n");
    return 0;
}

#include<stdio.h>
#include <windows.h>
 
typedef struct ENode{
    int adjVex;        //相邻顶点
    int w;             //边的权值
    struct ENode *next;  //指向下一顶点
}ENode;
 
typedef struct{
    int n;             //顶点数
    int e;             //边数
    ENode **a;         
}graph;
 
void Init(graph *g,int n){
    int  i;
    g->n = n;
    g->e = 0;
    g->a = (ENode**)malloc(n*sizeof(ENode*));  
    for(i=0; i<g->n; i++){
        g->a[i] = NULL;                        
    }
    return;
}

BOOL Exist(graph *g,int u,int v){
    if(u < 0||v < 0||u > g->n-1 ||v > g->n-1 ||u == v) return 0; //输入错误 
    ENode *p = g->a[u];                   
    while(p!=NULL && p->adjVex != v){
        p = p->next;
    }
    if(!p) return 0; //未找到此边
    else return 1; //找到此边 
}

void Insert(graph *g,int u,int v,int w){
    if(u < 0||v < 0||u > g->n-1||v > g->n-1 ||u == v) return; //输入错误 
    if(Exist(g,u,v)) return;  //边已存在
    ENode *p = (ENode*)malloc(sizeof(ENode));   
    p->adjVex = v;
    p->w = w;
    p->next = g->a[u];         
    g->a[u] = p;
    g->e ++;                            
}
 
BOOL Remove(graph *g,int u,int v){
    if(u < 0||v < 0||u > g->n-1||v > g->n-1 ||u == v) return 0; //输入错误 
    ENode *p = g->a[u];
    ENode *q = NULL;
    while(p && p->adjVex!=v){      
        q = p; //q是 p前一结点 
        p = p->next;
    }
    if(!p) return 0; //未找到待删除边 
    if(q) q->next = p->next; //删除此边 
    else g->a[u] = p->next;
    free(p);
    g->e --;
    return 1;
}
 
int Destory(graph *g){
    ENode *p,*q;
    for(int i=0; i<g->n; i++){
        p = g->a[i];                 
        q = p;
        while(p){                     
            p = p->next;
            free(q);
            q = p;
        }
    }
    free(g->a);                     
    return 1;                       
}

typedef struct{
    int front;
    int rear;
    int maxSize; 
    int *element;
}Queue;

//初始化一个空队列 
void Create(Queue *Q,int mSize){
    Q->maxSize=mSize;
    Q->element=(int*)malloc(sizeof(int)*mSize);
    Q->front=Q->rear=0;
}
 
//判断队列是否为空
BOOL IsEmpty(Queue *Q){
    return Q->front==Q->rear;
}
 
//判断队列是否已满
BOOL IsFULL(Queue *Q){
    return (Q->rear+1)%(Q->maxSize)==Q->front;
}
 
//获取队头元素 
void Front(Queue *Q,int *x){
    if(IsEmpty(Q)) return;
    *x=Q->element[(Q->front+1)%(Q->maxSize)];
}
 
//队尾插入元素
BOOL EnQueue(Queue *Q,int x){
    if(IsFULL(Q)) return 0;
    Q->rear=(Q->rear+1)%(Q->maxSize); 
    Q->element[Q->rear]=x;
    return 1;
}
 
//删除队头元素
BOOL DeQueue(Queue *Q){
    if(IsEmpty(Q)) return 0;
    Q->front=(Q->front+1)%(Q->maxSize);
    return TRUE;
}

//单一顶点 DFS
void DFS(int i,int visited[],graph g){
    printf("%d ",i);                           
    visited[i] = 1;      
    ENode *w;                      
    for(w=g.a[i]; w; w=w->next){          
        if(!visited[w->adjVex]){ //若邻接结点未被访问 
            DFS(w->adjVex,visited,g);          
        }
    }
}
 
//全图 DFS
void DFSGraph(graph g){
    int *visited = (int*)malloc(g.n*sizeof(int)); //访问标记 
    for(int i=0; i<g.n; i++){
        visited[i] = 0;                             
    }
    for(int i=0; i<g.n; i++){                        
        if(!visited[i]){
            DFS(i,visited,g);
        }
    }
    free(visited);                                
}
 
//单一顶点 BFS
void BFS(int v,int visited[],graph g){
    printf("%d ",v);  
    visited[v] = 1;                        
    ENode *w;
    Queue q;
    Create(&q,g.n);                                            
    EnQueue(&q,v); //入队操作 
    while(!IsEmpty(&q)){
        Front(&q,&v); //队头元素
        DeQueue(&q); //出队操作                   
        for(w=g.a[v]; w; w=w->next){  
            if(!visited[w->adjVex]){ //若未被访问  
                printf("%d ",w->adjVex);     
                visited[w->adjVex] = 1;
                EnQueue(&q,w->adjVex); //入队操作 
            }
        }
    }
}

//全图 BFS 
void BFSGraph(graph g){
    int *visited = (int*)malloc(g.n*sizeof(int));  
    for(int i=0; i<g.n; i++){                        
        visited[i] = 0;
    }
    for(int i=0; i<g.n; i++){                   
        if(!visited[i]){
            BFS(i,visited,g);
        }
    }
    free(visited);
}

int main(){
    graph g;
    int i,u,v,node,edge,w;
    printf("\n  Please enter the number of the node:"); scanf("%d",&node);
    //1、邻接表的初始化
    Init(&g,node);
    printf("    Please enter the number of the edges:"); scanf("%d",&edge);
    //2、邻接表的插入边
    for(i=0; i<edge; i++){
        printf("    Please enter the edge:");
        scanf("%d%d%d",&u,&v,&w);
        Insert(&g,u,v,w);
    }
    //6、深度优先遍历 DFS
    printf("    DFS:"); DFSGraph(g);
    //7、宽度优先遍历 BFS
    printf("\n  BFS:"); BFSGraph(g);
    printf("\n  Please enter the deleted edge:"); scanf("%d%d",&u,&v);
    //3、邻接表的搜索边
    if(Exist(&g,u,v)) printf("  Succeed to search to the edge.\n");
    else printf("   Failed to search to the edge.\n");   
    //4、邻接表的删除边 
    if(Remove(&g,u,v)) printf(" Succeed to delete the edge.\n");
    else printf("   Failed to delete the edge.\n");
    //5、邻接表撤销操作 
    if(Destory(&g)) printf("    Succeed to remove the table.\n");
    else printf("   Failed to remove the table.\n");
    return 0;
}

实验四，各种内排序算法

• 实现六种排序算法：直接插入、简单选择、冒泡、快排、归并、堆排（选做）
• 用随机发生器产生随机序列，比较这几种算法的计算时间

#include <stdio.h>
#include <iostream>
#include <time.h>
#include <sys/time.h>
using namespace std;


//1、直接插入排序
void InsertSort(int key[], int n){
    int i,j;                                
    for(i=1; i<n; i++){ //遍历第 2~n-1 个元素
        int insert = key[i]; 
        for(j=i-1; j>=0; j--){
            if(insert < key[j]){
                key[j+1] = key[j];
            }
            else break;
        }
        key[j+1] = insert;          
    }
}

//2、简单选择排序
void SelectSort(int key[], int n){
    int small,i,j;
    for(i=0; i<n-1; i++){ //遍历第 1~n-1 个元素 
        small = i; 
        for(j=i+1; j<n; j++){ ////遍历第 i+1~n 个元素
            if(key[j] < key[small]){  
                small = j;
            }
        }
        if(small != i)                         
            swap(key[i], key[small]);  
    }
}

//3、冒泡排序
void BubbleSort(int key[], int n){
    int i,j;                    
    for(i=n-1; i>0; i--){ //遍历第 2~n 个元素
        bool isSwap = false;   
        for(j=0; j<i; j++){ //遍历第 1~i 个元素
            if(key[j] > key[j+1]){
                swap(key[j],key[j+1]);
                isSwap = true;
            }
        }
        if(!isSwap) break;     
    }
}

//4、快速排序 
int Partition(int key[], int low,int high){
    int i = low,j = high + 1;
    int flag = key[low]; //当前分割元素
    do{
        do i++;
        while(key[i] < flag);      
        do j--;
        while(key[j] > flag);     
        if(i < j)
            swap(key[i], key[j]);
            
    }while(i < j);
    swap(key[low], key[j]);
    return j; //下一个分割元素 
}

void QuickSort(int key[], int low, int high){   
    int k;
    if(low < high){                            
        k = Partition(key,low,high);
        QuickSort(key,low,k-1);
        QuickSort(key,k+1,high);
    }
}

void QuickSort(int key[], int n){                 
    QuickSort(key,0,n-1);
}

//5、归并排序
void _merge(int key[], int low, int mid, int high) { //合并
    for (int i = 0; i < mid; i++) { 
        for (int j = mid; j < high; j++) {
            if (key[i] > key[j]) {
                swap(key[i], key[j]);
            }
        }
    }
}


void MergeSort(int key[], int low, int high) {
    if (low < high) {
        int length = high - low;
        if (length == 1) {
            if (key[low] > key[high])
                swap(key[low],key[high]);
        }
        for (int i=length/2; i>0; i=i/2) { //分治 
            MergeSort(key, low, low + i);
            MergeSort(key, high - i, high);
            _merge(key, low, i, high); //i为有序序列长度 
        }
    }
}

//6、堆排序
void AdjustDown(int heap[], int current, int border){
    int tmp = heap[current];
    while (2*current+1<=border){
        int child = 2*current+1; //左孩子 
        if (child+1<=border && heap[child]<heap[child+1]){
            child++;
        }
        if (heap[child] > heap[current]) {
            heap[current] = heap[child];
            heap[child] = tmp;
        }
        else break;
        current=child;
    }
}

void HeapSort(int heap[],int n){
    for(int i=(n-2)/2; i>=0; i--){ //初始调整 
        AdjustDown(heap,i,n-1);
    }
    for(int j=n-1; j>0; j--){
        swap(heap[0],heap[j]); //交换 
        AdjustDown(heap, 0, j-1); //调整 
    }
}

//7、产生随机序列 
void Init(int key[], int n){
    cout<<"\t随机序列：";
    for(int i=0; i<n; i++){
        key[i] = rand()%1000;
        cout<<key[i]<<" ";
    }
    cout<<" -> "; 
} 

//8、输出有序序列 
void output(int key[], int n){
    for(int i=0; i<n; i++){
        cout<<key[i]<<" ";
    }
    cout<<" -> "; 
}

int main(){
    int key[500000], n; 
    cout<<"\n\t输入随机序列长度："; cin>>n; cout<<endl;
    srand((int)time(NULL)); //随机发生器
    timeval start, end; //计时器 
    
    Init(key,n); gettimeofday(&start,0); InsertSort(key,n); gettimeofday(&end,0);
    cout<<"\t直接插入排序："; output(key,n); 
    double time = 1000000*(end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec; 
    time/=1000; cout<<"\t排序时长:"<<time<<"ms\n\n";
    
    Init(key,n); gettimeofday(&start,0); SelectSort(key,n); gettimeofday(&end,0);
    cout<<"\t简单选择排序："; output(key,n); 
    double time2 = 1000000*(end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec; 
    time2/=1000; cout<<"\t排序时长:"<<time2<<"ms\n\n";

    Init(key,n); gettimeofday(&start,0); BubbleSort(key,n); gettimeofday(&end,0);
    cout<<"\t冒泡排序："; output(key,n); 
    double time3 = 1000000*(end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec; 
    time3/=1000; cout<<"\t排序时长:"<<time3<<"ms\n\n";

    Init(key,n); gettimeofday(&start,0); QuickSort(key,n); gettimeofday(&end,0);
    cout<<"\t快速排序："; output(key,n);
    double time4 = 1000000*(end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec; 
    time4/=1000; cout<<"\t排序时长:"<<time4<<"ms\n\n";
    
    Init(key,n); gettimeofday(&start,0); MergeSort(key,0,n-1); gettimeofday(&end,0);
    cout<<"\t归并排序："; output(key,n); 
    double time5 = 1000000*(end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec; 
    time5/=1000; cout<<"\t排序时长:"<<time5<<"ms\n\n";
    
    Init(key,n); gettimeofday(&start,0); HeapSort(key,n); gettimeofday(&end,0);
    cout<<"\t堆排序："; output(key,n);
    double time6 = 1000000*(end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec; 
    time6/=1000; cout<<"\t排序时长:"<<time6<<"ms\n\n";
    
    return 0;
}

简化版，太快了，纳秒计时都不行