【算法设计】二分搜索技术+线性时间选择+堆排序+快速搜索+

本文主要是介绍【算法设计】二分搜索技术+线性时间选择+堆排序+快速搜索+，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

>>有机会了再挨行解释吧

.cpp

#include <iostream>
#include "sort.h"
using namespace std;

int main()
{
    int a1[9]={3,2,4,5,6,7,8,9,1};
    cout<<"输出一个a1数组"<<endl;
    for(int i=0;i<9;i++){
        cout<<a1[i];}
        cout<<endl ;
    cout<<"元素4在数组中的位置为:"<<endl;
    cout<<BinarySearch(a1,4,9)<<endl;




int a2[9]={3,5,1,7,9,4,6,8,2};
int  b[9];
    cout<<"输出一个a2数组"<<endl;
    for(int i=0;i<9;i++){
        cout<<a2[i];}
        cout<<endl ;
    cout<<"合并排序之后的a2数组为"<<endl;
    MergeSort(a2,b,0,8);
    for(int i=0;i<9;i++){
        cout<<a2[i];
    }
    cout<<endl ;



    int a3[9]={5,3,6,1,8,7,9,2,4};
    cout<<"输出一个a3数组"<<endl;
    for(int i=0;i<9;i++){
        cout<<a3[i] ;}
        cout<<endl ;
    cout<<"快速之后的a3数组为"<<endl;
    QuickSort(a3,0,8);
    for(int i=0;i<9;i++){
        cout<<a3[i];
    }
    cout<<endl ;

int a4[9]={3,5,6,4,8,7,9,2,1};
    cout<<"输出一个a4数组"<<endl;
    for(int i=0;i<9;i++){
        cout<<a4[i] ;}
        cout<<endl ;
    cout<<"堆排序后的数组为"<<endl;
    HeapSort(a4,9);
    for(int i=0;i<9;i++){
        cout<<a4[i];
    }
    cout<<endl ;


     int a5[9]={3,5,4,6,9,1,7,2,8};
    cout<<"输出一个数组a5为"<<endl ;
    for(int i=0;i<9;i++){
        cout<<a5[i];}
    cout<<("数组d中第二个小的元素为:");
    cout<<Select(a5,0,8,2)<<endl ;
    cout<<endl;

}

sort.h

#ifndef SORT_H_INCLUDED
#define SORT_H_INCLUDED


template<class Type>
int BinarySearch(Type a[],const Type&x,int n){
    int l=0;
    int r=n-1;
    while(l<=r){
        int m=(l+r)/2;
        if(x==a[m])
            return m;
        if(x>a[m])
            l=m+1;
        else
            r=m-1;
    }
   return -1;
}




template<class Type>
void Merge(Type c[],Type d[],int l,int m,int r)
{
    int i=l,j=m+1,k=l;
    while ((i<=m)&&(j<=r))
    {
        if(c[i]<=c[j])
            d[k++]=c[i++];
        else
            d[k++]=c[j++];
    }
    if(i>m)
    {
        for(int q=j;q<=r;q++)
            d[k++]=c[q];
    }
    if(j>r)
    {
        for(int q=i;q<=m;q++)
            d[k++]=c[q];
    }
}
template<class Type>
void MergeSort(Type a[],Type b[],int left,int right)
{
    if(left<right)
    {
        int i=(left+right)/2;
        MergeSort(a,b,left,i);
        MergeSort(a,b,i+1,right);
        Merge(a,b,left,i,right);
        for(int k=left;k<=right;k++)
        {
            a[k]=b[k];
        }
    }
}

template<class Type>
int Partition(Type r[],int first,int end)
{
    int i=first,j=end;
    while(i<j)
    {
        while(i<j&&r[i]<=r[j])
        {
            j--;
        }
        if(i<j)
        {
            Type c=r[i];
            r[i]=r[j];
            r[j]=c;
            i++;
        }
        while(i<j&&r[i]<=r[j])
        {
            i++;
        }
        if(i<j)
        {
            Type c=r[i];
            r[i]=r[j];
            r[j]=c;
            j--;
        }
    }
    return i;
}


template<class Type>
void QuickSort(Type a[],int p,int r)
{
    if(p<r)
    {
        int q=Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}

template<class Type>
void sift(Type r[],int k,int m)
{
    int i=k,j=2*i;
    while(j<=m)
    {
        if(j<m&&r[j-1]<r[j])
            j++;
        if(r[i-1]>r[j-1])
            break;
        else
        {
            Type c=r[i-1];
            r[i-1]=r[j-1];
            r[j-1]=c;
            i=j;
            j=2*i;
        }
    }

}

template<class Type>
void HeapSort(Type r[],int n)
{
    for(int i=n/2;i>=1;i--)
    {
        sift(r,i,n);
    }
    for(int i=1;i<n;i++)
    {
        Type c=r[0];
        r[0]=r[n-i];
        r[n-i]=c;
        sift(r,1,n-i);
    }
}


template<class Type>
Type Select(Type a[],int p,int r,int k)
{
    if(p==r)
        return a[p];
    int i=Partition(a,p,r),j=i-p+1;
    if(k<=j)
        return Select(a,p,i,k);
    else
        return Select(a,i+1,r,k-j);
}



#endif // SORT_H_INCLUDED

这篇关于【算法设计】二分搜索技术+线性时间选择+堆排序+快速搜索+的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！