快排和二分查找

一、【实验目的】

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

二、【实验要求】

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

三、【实验内容】

• 给定关键字序列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: