快速排序+折半查找 c++

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了快速排序+折半查找 c++，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1693字，纯文字阅读大概需要3分钟。

内容图文

#include <iostream>
using namespace std;


//快排
void quickSort(double *q ,int n)   //一个double型数组还有一个代表这个数组的位数。 
{

    double *left,*right;
    left = &q[0];
    right = &q[n-1];
    double middle = q[0];
//    cout<<"left指向数组第一位，值为"<<*left<<endl;
//    cout<<"right指向数组最右一位，值为"<<*right<<endl;
    while(left != right)
    {
        if (*right < middle)
        {
            *left = *right;
            while (*left < middle)
            {
                left++;
                if (left == right)
                {
                    break;
                }
            }
            *right = *left;
        } else {
            right--;
        }

    }
    //左右指针指向一致时把middle给这个位置
    *left = middle;

    //接下来取得*left和*right指向数组的位数
    int count = 0;   //count1表示有count1个数在middle左边，最小为0
    for(;q[count]<middle;count++) { }
    //
    //处理middle的左边
    if (count>1)
    {
        double *qq = new double[count];
        qq = q;
        quickSort(qq,count);
    }
    
    //处理middle的右边
    int count2 = n-count-1; //count2表示有count2个数在middle右边，最小为0
    if (count2 > 1)
    {
        double *ww = new double[count2];
        ww = left+1;
        quickSort(ww,count2);
    }
    
}


//折半查找
void binarySearch(double *p ,int length,double g) {
    bool b = false;
    int left = 1,right = length;
    int middle = (left + right) / 2;
    if (g == p[middle-1])
    {
        cout<<"该数字是第"<<middle<<"位"<<endl;
    } else {
        while (g != p[middle-1])
        {
            if (left == right)
            {
                cout<<"该数字不在数组中"<<endl;
                b = true;
                break;
            }
            if (g>p[middle-1])   //因为数组从零开始所以减一
            {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
            middle = (left + right) / 2;
        }
        if (b == false)
        {
            cout<<"该数字是第"<<middle<<"位"<<endl;
        }
        
        
    }
}



int main() {
    cout<<"请输入数组长度";
    int n;
    cin>>n;
    double *p = new double[n];
    for (int i = 0;i<n;i++)
    {
        cin>>p[i];
    }
    quickSort(p,n);
    for (int xxx = 0;xxx<n;xxx++)
    {
        cout<<p[xxx]<<"    ";
    }


    cout<<endl<<endl;
    //设(left+right)/2是中间位置
    double g;
    cout<<"输入要查的数字"<<endl;
    cin>>g;
    binarySearch(p,n,g);
    return 0;
}

结果如图

 

内容总结

以上是互联网集市为您收集整理的快速排序+折半查找 c++全部内容，希望文章能够帮你解决快速排序+折半查找 c++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---