菜鸡的代码大佬勿喷

注:不一定是最优解嗷,懒得改了/捂脸

A. 简单排序(冒泡)

运行时间限制: 1000运行内存限制: 65536
作者: scsyuanbaoku是否specialjudge: False

题目描述

输入第一行为一个整数n(0<n<=1000),代表待排序元素的个数。第二行是n个整数,每个整数都不会超过int型的存储范围,为待排序元素。
输出只有一行,为输入的n个待排序元素按从小到大排序后的结果。(建议采用起泡排序算法)

输入样例

8
49 38 65 97 76 13 27 4

输出样例

4 13 27 38 49 65 76 97

示例代码

#include<stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int a[n];
    int i, j;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n - i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

B. 实验7_12_设计函数(插入)

运行时间限制: 1000运行内存限制: 65536
作者: scshuanghai是否specialjudge: False

题目描述

void InsertSort(int a[],int n); 使用插入排序算法,将数组a的前n个元素按照升序的方式排序。
插入排序算法描述如下:
初始序列:49 38 65 97 76 13 27 49
将元素(38) 插入合适位置: [38 49] 65 97 76 13 27 49
将元素(65) 插入合适位置: [38 49 65] 97 76 13 27 49
将元素(97) 插入合适位置: [38 49 65 97] 76 13 27 49
将元素(76) 插入合适位置: [38 49 65 76 97] 13 27 49
将元素(13) 插入合适位置: [13 38 49 65 76 97] 27 49
将元素(27) 插入合适位置: [13 27 38 49 65 76 97] 49
将元素(49) 插入合适位置: [13 27 38 49 49 65 76 97]
输入与输出要求:首先输入一个整数n(1<=n<=1000),代表待排序元素的个数。然后输入n个整数,每个整数不会超过int型的存储范围。输出为n-1行,依次为1到n-1趟排序后数组内各个元素。每行输出的顺序为a[0]至a[n-1],数与数之间用空格分开,注意第n个数后没有空格而是换行符。

输入样例

8
49 38 65 97 76 13 27 49

输出样例

38 49 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 76 97 13 27 49
13 38 49 65 76 97 27 49
13 27 38 49 65 76 97 49
13 27 38 49 49 65 76 97

示例代码

#include<stdio.h>

void InsertSort(int*, int);
void printArray(int*, int);

int main()
{
    int n;
    scanf("%d", &n);
    int a[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    InsertSort(a, n);
    return 0;
}

void InsertSort(int a[],int n)
{
    int i, j, tmp;
    for (i = 1; i < n; i++)
    {
        tmp = a[i];
        j = i - 1;
        while (tmp < a[j])
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = tmp;
        printArray(a, n);
    }
}

void printArray(int a[],int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return;
}

C. 实验7_15_设计函数(选择)

运行时间限制: 1000运行内存限制: 65536
作者: scshuanghai是否specialjudge: False

题目描述

void SelectSort(int a[],int n); 使用选择排序算法对数组a的前n个元素按照升序的方式排序。
选择排序算法描述如下:
从a[0]~a[n-1]这段元素中找最小元素a[min],a[0]和a[min]交换;接着,从a[1]~a[n -1]这段元素中找最小元素a[min],a[1]和a[min]交换;依次类推,直到从a[n-2]~a[n -1]这段元素中找最小元素a[min],a[n-2]和a[min]交换。
输入与输出要求:首先输入一个整数n(1<n<=1000),代表待排序元素的个数。然后是n个整数,每个整数不会超过int型的存储范围
输出为n-1行,依次为1到n-1趟排序后数组内各个元素。每行输出的顺序为a[0]至a[n-1],数与数之间用空格分开,注意第n个数后没有空格而是换行符。
建议设计两个辅助函数:

函数功能:找数组中的最小值元素,并返回其下标
参数说明:数组名,查找起始位置下标,查找终止位置下标
int findMin(int data[], int startLoc, int endLoc) ;

函数功能:依次输出数组中各个元素,数与数之间用空格分开,最后一个数后没有空格而是换行符
参数说明:数组名,数组内元素个数
void outputData(int data[],int elementCount) ;

输入样例

8
49 38 65 97 76 13 27 4

输出样例

4 38 65 97 76 13 27 49
4 13 65 97 76 38 27 49
4 13 27 97 76 38 65 49
4 13 27 38 76 97 65 49
4 13 27 38 49 97 65 76
4 13 27 38 49 65 97 76
4 13 27 38 49 65 76 97

示例代码

#include<stdio.h>

void InsertSort(int*, int);
int findMin(int*, int, int);
void outputData(int*, int);


int main()
{
    int n;
    scanf("%d", &n);
    int a[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    InsertSort(a, n);
    return 0;
}

void InsertSort(int a[],int n)
{
    int i;
    for (i = 0; i < n - 1; i++)
    {
        int tmp = a[i];
        int min = findMin(a, i, n);
        a[i] = a[min];
        a[min] = tmp;
        outputData(a, n);
    }
}

int findMin(int data[], int startLoc, int endLoc)
{
    int i, xiabiao = startLoc;
    int min = data[startLoc];
    for (i = startLoc; i < endLoc; i++)
    {
        if (data[i] < min)
        {
            min = data[i];
            xiabiao = i;
        }
    }
    return xiabiao;
}

void outputData(int data[],int elementCount)
{
    int i = 0;
    for (i = 0; i < elementCount; i++)
    {
        printf("%d ", data[i]);
    }
    printf("\n");
}

D. 实验7_17_设计函数

运行时间限制: 1000运行内存限制: 65536
作者: scshuanghai是否specialjudge: False

题目描述

int BinarySearch(int a[],int n,int key);利用二分查找算法,在升序排列的数组a的前n个元素中查找值为key的数组元素的下标。如果数组a中存在整数key,则返回下标;否则返回-1。假设数组a中的元素互不相同。
输入与输出要求:首先输入两个整数n,m,分别代表数组a中元素的个数与需要查找的整数的个数,n(0<n<=2000000)与m(0<m<=100000)。然后分别输入n个整数和m个整数,分别代表存放在数组中的数以及要查找的数。输出m个整数,分别为要查找的数在数组a中的下标,如果数组a中不存在某个数,则输出-1。数与数之间用空格分开,注意第n个数后没有空格而是换行符。

注意:
1、由于n比较大,建议使用全局变量存储这n个整数;
2、由于数据量较大,建议输入时使用scanf()函数。

输入样例

15
20
-293 -213 -23 0 1 5 11 23 56 67 87 273 999 2132 10000
-23 -99999 0 999 953 67 56 44 33 87 -293 23 11 273 -213 2132 10000 87654 1 5

输出样例

2 -1 3 12 -1 9 8 -1 -1 10 0 7 6 11 1 13 14 -1 4 5

示例代码

#include<stdio.h>
#include<math.h>

int BinarySearch(int*, int, int);

int main()
{
    int n,m;
    scanf("%d %d", &n, &m);
    int nn[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &nn[i]);
    }
    while (m--)
    {
        int key;
        scanf("%d", &key);
        printf("%d ", BinarySearch(nn, n, key));
    }
    return 0;
}

int BinarySearch(int a[],int n,int key)
{
    int b = 0, c = n;
    int i;
    for (i = (b + c) / 2; a[i] != key && b <= c;)
    {
        if (a[i] > key)
        {
            c = (b + c) / 2 - 1;
            i = (b + c) / 2;
        }
        else if (a[i] < key)
        {
            b = (b + c) / 2 + 1;
            i = (b + c) / 2;
        }
    }
    if (b > c)
    {
        i = -1;
    }
    return i;
}

分类: OJ代码