1.阅读下面程序，写出其运行结果

#include <stdio.h>
#include <stdlib.h>

int BinarySearch(int *array, int key, int low, int high)  
{
    int mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (key == array[mid])
        {
            return mid;
        }
        else if (key < array[mid])
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return 0;
}

int main()  
{
    int n, i, key, position;
    int *array;
    printf("请输入有序数组的大小：");
    scanf("%d", &n);
    array = (int*) malloc(sizeof(int) * n);
    printf("请按升序输入数据：\n");
    for (i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }
    printf("请输入想要查找的数：");
    scanf("%d", &key);
    if (position = BinarySearch(array, key, 0, n - 1)) 
    {
        printf("%d的位置为：%d\n", key, position);
    }
    else
    {
        printf("%d不存在\n", key);    
    }
}

2. 阅读下面程序，写出其运行结果

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 直接插入排序
 */
void InsertSort(int *array)  
{
    int i, j;
    for (i = 2; i <= n; i++)
    {
        if (array[i] < array[i - 1])
        {
            array[0] = array[i];
            array[i] = array[i - 1];
            for (j = i - 2; array[0] < array[j]; j--)
            {
                array[j + 1] = array[j];
            }
            array[j + 1] = array[0];
        }
    }
}

int main()  
{
    int i;
    int *array;
    printf("请输入数组的大小：");
    scanf("%d", &n);
    array = (int*) malloc(sizeof(int) * (n + 1));
    printf("请输入数据（用空格分隔）：");
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &array[i]);
    }
    InsertSort(array);
    printf("排序后为：");
    for (i = 1; i <= n; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

3. 阅读下面程序，写出其运行结果

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 冒泡排序
 */
void BubbleSort(int *array)  
{
    int i, j, temp;
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < n - 1 - i; j++)
        {
            if (array[j] > array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

int main()  
{
    int i;
    int *array;
    printf("请输入数组的大小：");
    scanf("%d", &n);
    array = (int*) malloc(sizeof(int) * n);
    printf("请输入数据（用空格分隔）：");
    for (i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }
    BubbleSort(array);
    printf("排序后为：");
    for (i = 0; i < n; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

4. 阅读下面程序，写出其运行结果

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 分割使枢轴记录的左边元素比右边元素小
 */
int Partition(int *array, int low, int high)  
{
    int pivotkey = array[low];
    array[0] = array[low];
    while (low < high)
    {
        while (low < high && array[high] >= pivotkey)
        {
            high--;
        }
        array[low] = array[high];
        while (low < high && array[low] <= pivotkey)
        {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = array[0];
    return low;
}

/*
 * 快速排序递归实现
 */
void QuickSort(int *array, int low, int high)  
{
    if (low < high)
    {
        int pivotloc = Partition(array, low, high);
        QuickSort(array, low, pivotloc - 1);
        QuickSort(array, pivotloc + 1, high);
    }
}

int main()  
{
    int i;
    int *array;
    printf("请输入数组的大小：");
    scanf("%d", &n);
    array = (int*) malloc(sizeof(int) * (n + 1));
    printf("请输入数据（用空格分隔）：");
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &array[i]);
    }
    QuickSort(array, 1, n);
    printf("排序后为：");
    for (i = 1; i <= n; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

5. 阅读下面程序，写出其运行结果

#include <stdio.h>
#include <stdlib.h>

int n;

/*
 * 选择排序
 */
void SelectSort(int *array)  
{
    int i, j, k, temp;
    for (i = 0; i < n; i++)
    {
        k = i;
        for (j = i + 1; j < n; j++)
        {
            if (array[j] < array[k])
            {
                k = j;
            }
        }
        if (k != i)
        {
            temp = array[i];
            array[i] = array[k];
            array[k] = temp;
        }
    }
}

int main()  
{
    int i;
    int *array;
    printf("请输入数组的大小：");
    scanf("%d", &n);
    array = (int*) malloc(sizeof(int) * n);
    printf("请输入数据（用空格分隔）：");
    for (i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }
    SelectSort(array);
    printf("排序后为：");
    for (i = 0; i < n; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}