数据结构实验课——各种排序

/************************

INPUT:
20
8 69 84 49 22 85 27 77 8 89 58 85 71 41 42 80 72 51 71 22 

***************************/

#include<bits/stdc++.h>
using namespace std;
int a[105];
int b[105];
int n;
void init()
{
    freopen("in.txt","r",stdin);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>b[i];
}

void print(int a[],int n) {
    for(int i=0;i<n;i++) 
        cout<<a[i]<<" ";cout<<endl;
    cout<<endl;
}

void bubble_sort(int b[],int n)
{
    memcpy(a,b,n*sizeof(int));
    for(int i=0;i<n;i++)
        for(int j=n-1;j>i;j--)
            if(a[j]<a[j-1])
                swap(a[j],a[j-1]);
    puts("bubble_sort:");
    print(a,n);
}

void Select_insert(int b[],int n)
{
    memcpy(a,b,n*sizeof(int));
    for(int i=0;i<n;i++)
    {
        int index=i;
        for(int j=i;j<n;j++)
            if(a[index]>a[j]){
                index=j;
            }
        swap(a[index],a[i]);
    }
    puts("Select_insert:");
    print(a,n); 
}

void Straight_insert_sort(int b[],int n)
{
    memcpy(a,b,n*sizeof(int));
    for(int i=0;i<n;i++)
    {
        int index=-1;
        int temp=a[i];
        for(int j=0;j<i;j++)
            if(a[j]>a[i])
            {
                index=j;
                break;
            }
        if(index!=-1)
        {
            for(int j=i;j>index;j--)
                swap(a[j],a[j-1]);
            a[index]=temp;          
        }

    }
    puts("Straight_insert_sort:");
    print(a,n);     
}

void Binary_insert_sort(int b[],int n)
{
    memcpy(a,b,n*sizeof(int));
    for(int i=0;i<n;i++)
    {
        int index=-1;
        int temp=a[i];

        int l=0;
        int r=i-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(a[mid]<a[i])
            {
                l=mid+1;
            }else{
                index=r;
                r=mid-1;
            }
        }
        if(index!=-1)
        {
            for(int j=i;j>index;j--)
                swap(a[j],a[j-1]);
            a[index]=temp;          
        }

    }
    puts("Binary_insert_sort:");
    print(a,n);     
}

void qsort(int left,int right)
{
    int l=left;
    int r=right;
    int mid=a[(l+r)>>1];
    do
    {

        while(a[l]<mid) l++;
        while(mid<a[r]) r--;
        if(l<=r) 
        {
            swap(a[l],a[r]);
            l++;
            r--;
        }
    }while(l<=r);
    if(left<r)  qsort(left,r);
    if(l<right) qsort(l,right);
}
void Quick_sort(int b[],int n)
{
    memcpy(a,b,n*sizeof(int));
    qsort(0,n-1);
    puts("Quick_sort:");
    print(a,n);     
}

void push_up(int x)
{
    if(x<=1) return;
    if(a[x]<a[x/2]){
        swap(a[x],a[x/2]);
        push_up(x/2);
    }
}

void build_heap(int l,int r)
{
    for(int i=l;i<=r;i++)
        push_up(i);
}

void push_down(int x,int len)
{
    if(x*2+1>len) return;
    int index1=-1;
    int index2=-1;
    if(x*2+1<=len&&a[x*2+1]<a[x]) index1=x*2+1;
    if(x*2  <=len&&a[x*2]<a[x]) index2=x*2;
    int index=-1;
    if(index1==-1&&index2==-1) index=-1;
    else {
        if(index1==-1) index=index1;
        else if(index2==-1) index=index2;
        else{
            if(a[index1]>a[index2]) index=index2;
            else index=index1; 
        }
    }
    if(index!=-1)
    {
        swap(a[x],a[index]);
        push_down(index,len);       
    }

}
int c[200];
void Heap_sort(int b[],int n)
{
    a[0]=0;
    for(int i=1;i<=n;i++)
        a[i]=b[i-1];
    int len=n;
    build_heap(1,n);

    //print(a+1,n); 
    memset(c,0,sizeof(c));
    for(int i=0;i<n;i++)
    {
        c[i]=a[1];
        a[1]=a[len--];
        a[len+1]=0;
        push_down(1,len);
    }
    //build();
    puts("Heap_sort:");
    print(c,n); 
}

void msort(int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)>>1;
    msort(l,mid);
    msort(mid+1,r);
    int i=l;
    int j=mid+1;
    int len=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]<a[j]) c[len++]=a[i++];
        else c[len++]=a[j++];
    }
    if(i>mid){
        for(int t=j;t<=r;t++)
            c[len++]=a[t];
    }else{
        for(int t=i;t<=mid;t++)
            c[len++]=a[t];
    }
    for(int i=l;i<=r;i++)
        a[i]=c[i-l];
}

void Merge_sort(int b[],int n)
{
    memcpy(a,b,n*sizeof(int));
    msort(0,n-1);
    puts("Merge_sort:");
    print(c,n); 
}

int main()
{
    init();
    bubble_sort(b,n);
    Select_insert(b,n);
    Straight_insert_sort(b,n);
    Binary_insert_sort(b,n);
    Quick_sort(b,n);
    Merge_sort(b,n);
    Heap_sort(b,n);
    return 0;
}

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注