排序总结

/*排序基础：冒泡，起泡... 注意加等号的意义何在... */#include<iostream>#include<cstdio>using namespace std;#define manx 5000int x[manx];void sort(int n){  //// 冒泡     for(int i=0;i<n;i++)        for(int j=1;j<n-i;j++)            if(x[j-1]>=x[j]) swap(x[j-1],x[j]);  //////加等号 }void sort1(int n){  /// 起泡     for(int i=0;i<n;i++)        for(int j=n-1;j>i;j--)            if(x[j-1]>=x[j]) swap(x[j-1],x[j]);  //////加等号 }int main(){    int n;    while(cin>>n){        for(int i=0;i<n;i++)             scanf("%d",&x[i]);        sort1(n);        for(int i=0;i<n;i++)            printf("%d ",x[i]);        printf("\n");    }}

/*选择排序：时间复杂度 n^2 ..注意模型，把模型翻译成代码，OK，每次从 i+1 ~ n 中找出最小的值与 i 交换 */ #include<iostream>#include<cstdio>using namespace std;#define manx 5000 int x[manx];void sort(int n){    for(int i=1;i<n;i++){        int temp = x[i];        int ans = i;  //// 记录位置         for(int j=i+1;j<=n;j++){            if(x[j]<temp) {                temp = x[j];                ans = j;            }            }        if(ans!=i) swap(x[i],x[ans]);    } }int main(){    int n;    while(cin>>n){        for(int i=1;i<=n;i++) scanf("%d",&x[i]);        sort(n);        for(int i=1;i<=n;i++)            printf("%d ",x[i]);        printf("\n");    }    }

/*二叉排序树也叫二叉查找树.. 之所以把二叉排序树，放排序来也是有道理的，以为它可以实现排序的功能..注意等号的意义... */#include<iostream>#include<malloc.h>#include<cstdio>#define manx 1000009using namespace std;struct node{    int val;    struct node*rch;    struct node*lch;} ;void init(node *&tree){    tree = (node*)malloc(sizeof(node));    tree->rch=NULL;    tree->lch=NULL;}void creat(int a,node *&tree){    if(tree==NULL){        node *te;        init(te);        te->val = a;        tree = te;        return ;     }    if(a < tree->val)  creat(a,tree->rch);    if(a >= tree->val)  creat(a,tree->lch);    return ;}void bfs(node*&tree){  /// 遍历中序就 OK 了     if(tree==NULL) return;    bfs(tree->rch);    printf("%d ",tree->val);    bfs(tree->lch);    return ;}int main(){    int n;    node *tree;    while(cin>>n){        init(tree);        int m=0;        for(int i=1;i<=n;i++){            scanf("%d",&m);            if(i==1) { tree->val=m; continue; }            creat(m,tree);        }        bfs(tree);        printf("\n");    }    }

/*快速排序：最差的情况下，时间复杂度为 n^2但是平均时间复杂度是 n*lgn ... 值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。*/#include<iostream>#include<cstdio>using namespace std;#define manx 1000009int x[manx];void qsort(int st,int ed){    if(st==ed || st>ed) return;    int flag=st;    for(int i=st,j=st+1;j<=ed;j++){        if(x[j]<x[st]){            swap(x[i+1],x[j]);            i++;            flag = i;            continue;        }    }    swap(x[st],x[flag]);    qsort(st,flag-1);    qsort(flag+1,ed);    return ; }int main(){    int n;    while(cin>>n){        for(int i=0;i<n;i++)            scanf("%d",&x[i]);        qsort(0,n-1);        for(int i=0;i<n;i++)            printf(" %d",x[i]);        printf("\n");    }}/*86 10 13 5 8 3 2 11*/

 /*归并排序：我的程序有些缺陷，实现的时间复杂度是 2n*lgn（待优化） ..开的数组可以使用动态开辟，从而节省空间.. 所以其他的也没什么的，不用写的很复杂... */ #include<iostream>#include<cmath>using namespace std;#define manx 1000009int x[manx];void sort(int st,int ed){    if(st==ed) return ;    int mid=(st+ed)>>1;    sort(st,mid);    sort(mid+1,ed);    int flag = st;    int *z = new int[manx];    for(int i=st,j=mid+1; i<=mid || j<=ed;  ){  /////////        if( i>mid ) {  /////////            z[flag++] = x[j];            j++;            continue;        }         if( j>ed ) {   //////////            z[flag++] = x[i];            i++;            continue;        }        if(x[i]<=x[j]){  //// 注意等号的意义...             z[flag++] = x[i];            i++;            continue;        }        if(x[i]>x[j]){            z[flag++] = x[j];            j++;            continue;        }    }    for(int i=st;i<=ed;i++) x[i]=z[i];  ////蛋疼..这里花多了一倍的时间..待优化     delete []z;    return ; }int main(){    int n;    while(cin>>n){        for(int i=1;i<=n;i++)            scanf("%d",&x[i]);        sort(1,n);        for(int i=1;i<=n;i++)            cout<<x[i]<<" ";        cout<<endl;    }}