快排和二分查找

2018-06-03T17:49:35

一、【实验目的】

  • 掌握二分查找过程及其实现算法;
  • 掌握快速排序过程及其实现算法;

二、【实验要求】

  • 实现整型数组的快速排序算法的程序;
  • 在排序的基础上进行折半(二分)查找算法的实现;
  • 要求:提交实验报告,附排序函数、折半查找函数的源代码,提供实验结果和数据。

三、【实验内容】

  • 给定关键字序列32,75,29,63,48,94,25,46,18,70,调用快速排序函数进行排序并输出。
  • 读入一个元素,比如32(成功找到)、27(不能成功查找到),用折半查找的方法判断该元素是否在已排序的数组内,输出是否找到,最好能统计比较的次数并输出。

[title]代码[/title]

#include <iostream>
using namespace std;
//快速排序
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x)
                j--;
            if(i < j)
                s[i++] = s[j];
            while(i < j && s[i] < x)
                i++;
            if(i < j)
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1);
        quick_sort(s, i + 1, r);
    }
}
//折半查找
void binarySearch(int arr[], int n, int target){
    int l = 0, r = n - 1, i = 0;
    //在[l,r]区间查找
    while( l <= r){
        i++;
        int mid = l + (r-l)/2;
        if(target == arr[mid]){
            cout << "目标元素在arr[" << mid << "]的位置," << "查找了" << i << "次";
            break;
        }
        if (target < arr[mid])
            r = mid -1;
        if (target > arr[mid])
            l = mid + 1;
    }
    if ( l > r)
        cout << "找不到啊!";
}

int main() {
    int s[] = {32,75,29,63,48,94,25,46,18,70}, l = 0, r = 9, target;
    quick_sort(s,l, r);
    for(int i=0;i<=r;i++)
        cout << s[i] << " ";
    cout << endl << "请输入查找的数字:";
    cin >> target;
    binarySearch(s, r+1, target);
    return 0;
}

ps:快排看一个博主的真是茅塞顿开(大佬就是大佬),附上链接——链接

:huaji13:

当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »
因本文不是用Markdown格式的编辑器书写的,转换的页面可能不符合MIP标准。