【基础算法】冒泡排序+二分查找法

浏览数：19 / 时间：2015年06月08日

　　1、思考题

　　（1）有12颗球，1颗是9克，其余的都是10克，怎样在天平上称三次找出9克的那颗质量小的球？

　　答：第一次：把12颗球分成两半，一半6颗，在天平上称，取质量小的一边；

　　　　第二次：把6颗球分成两半，一半三颗，也取质量小的一边；

　　　　第三次：取三颗球中任一两颗去称，如果质量相等，那么没有称的那一颗就是质量最小的一颗（9克），如果两颗质量不想等，取质量小的一颗也可以取到。

　　（2）有1024个人，有一个人血液有病毒，而999个人没有病毒，化验一个人的血液需要10分钟，怎么用最短的时间找出有血液病毒的那个人？

　　答：普通的方法，如果每个人都检查的话，需要话的时间最多需要10000分钟，是需要几天。

我们这样，1024个人分为两组，每人抽一次血混合，查看有病毒的一组再分成两半测，直到测出为止，这种方法只需要 2^x=1024，x=10 ，就只需要10次，100分钟即可

　　（3）有1到100的数，随机寻找1到100的数，怎么在最短的时间找到？

　　答：把1到一百分成两半，把中间的数和随机数比较，如果随机数大于中间数，选择大于的一半数再分成两半查找，再和随机数比较，不停的分成两半取中间比较值，直到找到为止；如果小于，反之；

　　2、二分法查找

　　上面的思考题就是运用了二分法查找的原理。

　　二分法伪代码：　

             输入 f(x) 的定义
             输入 a 和 b 为初始区间

             重复如下:
             m := (a + b) / 2
             如果 f(m) * f(a) < 0 则
             b := m
             否则
             a := m
            直至满意为止

　　3、冒泡排序

　　二分法查找必须针对有序数组，如果不是有序的，我们就要对数组进行排序。冒泡排序算法：

void  bubble_sort(int arr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (arr[j]>arr[j + 1])
            {
                //交换两个数
                arr[j] = arr[j] + arr[j + 1];
                arr[j + 1] = arr[j] - arr[j + 1];
                arr[j] = arr[j] - arr[j + 1];
            }
        }
    }
}

　　4、二分法查找

//二分法排序 while循环实现
int dichotomy1(int arr[], int length, int num)
{
    int head = 0;
    int foot = length - 1;
    int middle = (head + foot) / 2;
    while (head <= foot)
    {
        if (arr[middle] = num)
        {
            return middle;
            break;
        }
        else if (arr[middle] < num)
        {
            head = middle-1;
            middle = (head + foot) / 2;
        }
        else if (arr[middle] > num)
        {
            foot = middle+1;
            middle = (head + foot) / 2;
        }
    }
    return -1;
}
//二分查找 for循环实现
int dichotomy2(int arr[], int length, int num)
{
    for (int head = 0, foot = length - 1, middle = (length-1)/2; head <= foot;middle=(head+foot)/2)
    {
        if (arr[middle] == num)
        {
            return middle;
        }
        else if (arr[middle]>num )
        {
            foot = middle - 1;
        }
        else if (arr[middle]<num)
        {
            head = middle + 1;
            
        }
    }
    return -1;
}

　　5、完整实例

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 100
//二分法排序 while循环实现
int dichotomy1(int arr[], int length, int num)
{
    int head = 0;
    int foot = length - 1;
    int middle = (head + foot) / 2;
    while (head <= foot)
    {
        if (arr[middle] = num)
        {
            return middle;
            break;
        }
        else if (arr[middle] < num)
        {
            head = middle-1;
            middle = (head + foot) / 2;
        }
        else if (arr[middle] > num)
        {
            foot = middle+1;
            middle = (head + foot) / 2;
        }
    }
    return -1;
}
//二分查找 for循环实现
int dichotomy2(int arr[], int length, int num)
{
    for (int head = 0, foot = length - 1, middle = (length-1)/2; head <= foot;middle=(head+foot)/2)
    {
        if (arr[middle] == num)
        {
            return middle;
        }
        else if (arr[middle]>num )
        {
            foot = middle - 1;
        }
        else if (arr[middle]<num)
        {
            head = middle + 1;
            
        }
    }
    return -1;
}
void  bubble_sort(int arr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (arr[j]>arr[j + 1])
            {
                //交换两个数
                arr[j] = arr[j] + arr[j + 1];
                arr[j + 1] = arr[j] - arr[j + 1];
                arr[j] = arr[j] - arr[j + 1];
            }
        }
    }
}
void main()
{
    time_t t;
    srand((unsigned int)time(&t));
    int a[N];
    for (int i = 0; i < N; i++)
    {
        a[i] = rand() % 100;//生成100以内的随机数
        printf("%-2d\t", a[i]);
    }
    bubble_sort(a,N);    
    printf("排序后\n");
    for (int i = 0; i < N; i++)
    {
        printf("%-2d\t", a[i]);
    }
    printf("请输入要查找的数\n");
    int num;
    scanf_s("%d", &num);
    int found = dichotomy2(a,N,num);
    if (found != -1)
    {
        printf("found!a[%d]=%d",found,num);
    }
    else
    {
        printf("not found!");
    }
    system("pause");

}