天天看点

直接查找排序,归并排序,快速排序,计数排序 ,堆排 C++实现

#include<iostream>

using namespace std;

void insertion(int* a);

void main()

{

    int arraya[10]={2,4,6,8,7,9,12,1,11,0};

    insertion(arraya);

    cout<<"the arraya after insertion:";

    for(int i=0;i<10;i++)

        cout<<" "<<arraya[i];

    system("pause");

}

void insertion(int* a )

{

    int i,j;

    int length=10;

    for(i=1;i<length;i++)

    {

        int key=a[i];

        j=i-1;

        while(j>=0&&a[j]>key)

            {

                a[j+1]=a[j];

                j--;

            }

        a[j+1]=key;

    }

}

#include<iostream>

using namespace std;

void merge(int a[], int p, int q, int r)

{

    int i,j,k,n1,n2;

    n1=q-p+2;//n1和n2要多留一位给INT_MAX; 所以一个要加2,一个要加1;

    n2=r-q+1;

    int l[11];

    int m[11];

    int pp=p;//P是中间那个数,不能动。所以我们重新复制给PP;

    for(i=0;i<n1-1;i++)

    {

        l[i]=a[pp];

        pp++;//别忘了pp也要自加,我之前就忘了这点,同理qq也是

    }

    l[n1-1]=INT_MAX;//因为我是用数组做的,而不是vector,所以没法动态分配。只能用类库里的INT_MAX来限制每次大小不一样的数组长度

    int qq=q+1;

    for(j=0;j<n2-1;j++)

    {

        m[j]=a[qq];

        qq++;

    }

    m[n2-1]=INT_MAX;

    i=j=0;

    for(k=p;k<=r;k++)

    {

        if(l[i]<=m[j])//如果数组l的值小就把l数组的值放进原先数组里

        {

            a[k]=l[i];

            i++;

        }

        else

        {

            a[k]=m[j];

            j++;

        }

    }

}

void mergesort(int a[], int p, int r)

{

    if(p<r)

    {

        int q;

        q=(p+r)/2;

        mergesort(a,p,q);

        mergesort(a,q+1,r);

        merge(a, p,q, r);

    }

}

void main()

{

    int arraya[10]={1,3,2,5,6,4,7,12,9,10};

    mergesort(arraya,0,9);

    for(int i=0;i<10;i++)

        cout<<arraya[i]<<" ";

    cout<<endl;

    system("pause");

}

#include<iostream>

using namespace std;

#include<vector>

void merge(vector<int>&A,vector<int>&temp,int p, int q, int r);

void mergesort(vector<int>&A, vector<int>&temp,int p, int r);

void mergeSort(vector<int>&A);

void main()

{

    vector<int> ve;

        ve.push_back(3);

        ve.push_back(5);

        ve.push_back(1);

        ve.push_back(2);

        ve.push_back(6);

        ve.push_back(4);

        ve.push_back(0);

        ve.push_back(9);

        ve.push_back(8);

        ve.push_back(7);    

    mergeSort(ve);

    for(int i=0;i<ve.size();i++)

        cout<<ve[i];

    cout<<endl;

}

void merge(vector<int>&A,vector<int>&temp,int p, int q, int r)

{

    int i=p;

    int j=q+1;

    int t=p;

    while(i<=q&&j<=r)

    {

        if(A[i]<A[j])

            temp[t++]=A[i++];

        else

            temp[t++]=A[j++];

    }

    while(i<=q)

        temp[t++]=A[i++];

    while(j<=r)

        temp[t++]=A[j++];

    for(int k = p; k<= r; ++k)

        A[k] = temp[k];

}

void mergesort(vector<int>&A, vector<int>&temp,int p, int r)

{

    if(p<r)

    {    

        int    q;

        q=(p+r)/2;

        mergesort(A,temp,p,q);

        mergesort(A,temp,q+1,r);

        merge(A,temp,p,q,r);

    }

}

void mergeSort(vector<int>&A)

{

    vector<int>temp(A.size());

    mergesort(A,temp,0,A.size()-1);

}

#include<iostream>

using namespace std;

struct node

{

    node(int v =0, node *n =0 )

        :value(v),next(n)

    {}

    int value;

    node* next;

};

void frontbacksplit(struct node* source, struct node **frontRef, struct node **backRef)

{    

    struct node *slow;

    struct node *fast;

    slow=source;

    fast=source->next;

    while(fast!=NULL)

    {

        fast=fast->next;

        if(fast!=NULL)

        {

            slow=slow->next;

            fast=fast->next;

        }

    }

    *frontRef=source;

    *backRef=slow->next;

    slow->next=NULL;

}

struct node* sortedmerge(struct node *a, struct node *b)

{

    struct node *result=NULL;

    struct node** lastptrref=&result;

    while(a!=0&&b!=0)

    {

        if(a->value<=b->value)

        {

            *lastptrref=a;

            a=a->next;

            lastptrref=&((*lastptrref)->next);

        }

        else

        {    

            *lastptrref=b;

            b=b->next;

            lastptrref=&((*lastptrref)->next);

        }

    }

    if(a!=0)

        *lastptrref=a;

    if(b!=0)

        *lastptrref=b;

    return(result);

}

void mergesort(struct node** headRef)

{

    if((*headRef)==0||(*headRef)->next==0)

        return;

    struct node* head=*headRef;

    struct node* a=NULL;

    struct node* b=NULL;

    frontbacksplit(head,&a,&b);

    mergesort(&a);

    mergesort(&b);

    *headRef=sortedmerge(a,b);

}

void main()

{

    node *node9=new node(1);

    node *node8=new node(2,node9);

    node *node7=new node(3,node8);

    node *node6=new node(4,node7);

    node *node5=new node(5,node6);

    node *node4=new node(6,node5);

    node *node3=new node(7,node4);

    node *node2=new node(8,node3);

    node *node1=new node(9,node2);

    node *head=node1;

    node *runner;

    runner=head;

    while(runner)

    {

        std::cout<<runner->value<<" ";

        runner=runner->next;

    }

    std::cout<<"\n";

    mergesort(&head);

    runner=head;

    while(runner)

    {

        std::cout<<runner->value<<" ";

        runner=runner->next;

    }

    std::cout<<"\n";

    system("pause");

}

#include<iostream>

using namespace std;

int partition(int A[8],int size,int p, int r)

{

    int i,j,x,temp;

    x=A[r];

    i=p-1;

    for(j=p;j<=r-1;j++)

    {

    if(A[j]<=x)

        {

            i=i+1;

            temp=A[i];

            A[i]=A[j];

            A[j]=temp;

        }

    cout<<endl;

    for(int z=0;z<8;z++)

        cout<<A[z]<<" ";

    cout<<endl;

    }

    temp=A[i+1];

    A[i+1]=A[r];

    A[r]=temp;

    return i+1;

}

void quicksort(int A[8],int size, int p, int r)

{

    if(p<r)

    {int q=partition(A,size,p,r);

    quicksort(A,size,p,q-1);

    quicksort(A,size,q+1,r);}

}

int main()

{

    int A[8]={2,8,7,1,3,5,6,4};

    int z;

    cout<<"before quicksort: ";

    for(z=0;z<8;z++)

    {

    cout<<A[z]<<" ";

    }

    cout<<endl;

    quicksort(A,8,0,7);

    cout<<"after quicksort: ";

    for(z=0;z<8;z++)

    {

    cout<<A[z]<<" ";

    }

    cout<<endl;

    system("pause");

    return 0;

}

#include<iostream>

using namespace std;

#include<ctime>

#include<cstdlib>

int random(int p, int r)

{

    int size=r-p+1;

    return p+rand()%size;

}

int partition(int A[8],int size,int p, int r)

{

    int i,j,x,temp,s;

    s=random(p,r);

    temp=A[r];

    A[r]=A[s];

    A[s]=temp;

    x=A[r];

    i=p-1;

    for(j=p;j<=r-1;j++)

    {

    if(A[j]<=x)

        {

            i=i+1;

            temp=A[i];

            A[i]=A[j];

            A[j]=temp;

        }

    cout<<endl;

    for(int z=0;z<8;z++)

        cout<<A[z]<<" ";

    cout<<endl;

    }

    temp=A[i+1];

    A[i+1]=A[r];

    A[r]=temp;

    return i+1;

}

void quicksort(int A[8],int size, int p, int r)

{

    if(p<r)

    {int q=partition(A,size,p,r);

    quicksort(A,size,p,q-1);

    quicksort(A,size,q+1,r);}

}

int main()

{

    int A[8]={2,8,7,1,3,5,6,4};

    int z;

    cout<<"before quicksort: ";

    for(z=0;z<8;z++)

    {

    cout<<A[z]<<" ";

    }

    cout<<endl;

    quicksort(A,8,0,7);

    cout<<"after quicksort: ";

    for(z=0;z<8;z++)

    {

    cout<<A[z]<<" ";

    }

    cout<<endl;

    system("pause");

    return 0;

}

#include<iostream>

using namespace std;

void countsort(int A[ ], int sizea, int B[], int sizeb,int k)

{

    int i;

    int C[10];

    for(i=0;i<k;i++)

    {

        C[i]=0;

    }

    for(i=0;i<sizea;i++)

    {

        C[A[i]]=C[A[i]]+1;

    }

    for(i=1;i<k;i++)

    {

        C[i]=C[i]+C[i-1];

    }

    for(i=sizea-1;i>=0;i--)

    {

        B[C[A[i]]-1]=A[i];

        C[A[i]]=C[A[i]]-1;

    }

}

void main()

{

    int i;

    int A[]={2,5,3,0,2,3,0,3};

    int B[]={0,0,0,0,0,0,0,0};

    countsort(A,8,B,8,6);

    for(i=0;i<8;i++)

    {

        cout<<B[i]<<" ";

    }

}

#include<iostream>

using namespace std;

void maxheapify(int A[],int i,int size)

{

    int l=2*i+1;

    int r=2*i+2;

    int large=i;

    int temp;

    if(l<=size-1&&A[l]>A[i])

        large=l;

    if(r<=size-1 && A[r]>A[large])

        large=r;

    if(large!=i)

    {

        temp=A[large];

        A[large]=A[i];

        A[i]=temp;

        maxheapify(A,large,size);

    }

}

void buildmaxheap(int A[],int size)

{

    int i;

    for(i=size/2;i>=0;i--)

    {

        maxheapify(A,i,size);

    }

}

void heapsort(int A[],int size)

{

    int i;

    buildmaxheap(A,size);

    for(i=0;i<size;i++)

        cout<<A[i]<<" ";

    cout<<endl;

    for(i=size-1;i>0;i--)

    {

        int temp;

        temp=A[0];

        A[0]=A[i];

        A[i]=temp;

        size--;

        maxheapify(A,0,size);

    }

}

void main()

{

    int i;

    int AA[10]={2,4,23,1,3,5,6,9,7,10};

    heapsort(AA,10);

    for(i=0;i<10;i++)

    {cout<<AA[i]<<" ";}

}