【0001】排序法与查找方式

时间：2020-07-19 11:54:20 阅读：62 评论：0 收藏：0 [点我收藏+]

0001、选择排序法

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 #define N 20
 5 
 6 
 7 void main()
 8 {
 9     time_t ts;
10     srand((unsigned int)time(&ts));
11 
12     int a[N] = { 0 };
13     
14     for (int i = 0; i < N; i++)
15     {
16         printf("%4d", a[i] = rand() % 300);
17     }
18 
19     int intmax = 0;                选择法找极值（极大值和极小值）
20     for (int i = 0; i < N; i++)
21     {
22         if (intmax < a[i])
23             intmax = a[i];
24     }
25     printf("\nintmax=%d \n", intmax);    // intmax=261 
26 
27     
28     system("pause");
29 }

选择法查找极值

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 #define N 20
 5 
 6 
 7 void main001()
 8 {
 9     time_t ts;
10     srand((unsigned int)time(&ts));
11 
12     int a[N] = { 0 };
13     
14     for (int i = 0; i < N; i++)
15     {
16         printf("%4d", a[i] = rand() % 300);
17     }
18 
19 
20     for (int i = 0; i < N - 1; i++)
21     {
22         int imax = i;
23         for (int j = i + 1; j < N; j++)
24         {
25             if (a[imax] < a[j])
26                 imax = j;
27         }
28         if (imax != i)
29         {
30             int temp = a[imax];
31             a[imax] = a[i];
32             a[i] = temp;
33         }
34     }
35     
36 
37     putchar(‘\n‘);
38     for (int i = 0; i < N; i++)
39         printf("%4d", a[i]);
40 
41     putchar(‘\n‘);
42 
43     system("pause");
44 }
45 
46 /*
47        9  49 261 110  64 160  83 215  58 163  29 101 131  88  56 255 104 186  44 165
48      261 255 215 186 165 163 160 131 110 104 101  88  83  64  58  56  49  44  29   9
49 */

选择排序法

0002、冒泡排序法

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define N 10
 4 
 5 void main()
 6 {
 7     int a[N] = { 3,5,18,9,23,5,2,1,0,2 };
 8 
 9     for (int i = 0; i < N - 1; i++)                // 沉底极大值
10     {
11         if (a[i] > a[i + 1])
12         {
13             int temp = a[i];
14             a[i] = a[i + 1];
15             a[i + 1] = temp;
16         }
17 
18         for (int i = 0; i < N; i++)
19             printf("%3d", a[i]);
20 
21         putchar(‘\n‘);
22     }
23 
24     /*
25           3  5 18  9 23  5  2  1  0  2
26           3  5 18  9 23  5  2  1  0  2
27           3  5  9 18 23  5  2  1  0  2
28           3  5  9 18 23  5  2  1  0  2
29           3  5  9 18  5 23  2  1  0  2
30           3  5  9 18  5  2 23  1  0  2
31           3  5  9 18  5  2  1 23  0  2
32           3  5  9 18  5  2  1  0 23  2
33           3  5  9 18  5  2  1  0  2 23
34     */
35 
36     system("pause");
37 }

冒泡法寻找极值

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define N 10
 4 
 5 
 6 void main()
 7 {
 8     int a[N] = { 3,5,18,9,23,5,2,1,0,2 };
 9 
10     for (int i = 0; i < N - 1; i++)                
11     {
12         for (int j = 0; j < N - 1 - i; j++)            // 每沉底一次，就向上冒泡一次
13         {
14             if (a[j] > a[j + 1])
15             {
16                 int temp = a[j];
17                 a[j] = a[j + 1];
18                 a[j + 1] = temp;
19             }
20         }
21 
22         for (int i = 0; i < N; i++)
23             printf("%3d", a[i]);
24 
25         putchar(‘\n‘);
26     }
27 
28     /*
29         3  5  9 18  5  2  1  0  2 23
30         3  5  9  5  2  1  0  2 18 23
31         3  5  5  2  1  0  2  9 18 23
32         3  5  2  1  0  2  5  9 18 23
33         3  2  1  0  2  5  5  9 18 23
34         2  1  0  2  3  5  5  9 18 23
35         1  0  2  2  3  5  5  9 18 23
36         0  1  2  2  3  5  5  9 18 23
37         0  1  2  2  3  5  5  9 18 23
38     */
39 
40     system("pause");
41 }

冒泡排序法

0003、二分查找和拉格朗日定理

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
#define N 1024


void search(int a[N], int num)                    // 二分查找
{
    int head = 0, tail = N - 1, middle;
    int flag = -1, count=0;

    if (num<a[head])
    {
        printf("要查找的值%d小于数组中的最小值%d，共查找了1次 \n", num, a[head]);
    }
    else if (num>a[tail])
    {
        printf("要查找的值%d大于数组中的最大值%d，共查找了1次 \n", num, a[tail]);
    }
    else
    {
        while (head <= tail)
        {
            middle = (head + tail) / 2;
            printf("head=%d, middle=%d, tail=%d, count=%d \n", head, middle, tail, ++count);
            if (a[middle] == num)
            {
                flag = 1;
                printf("找到了，是a[%d]=%d, 一共查找了%d次 \n", middle, num, count);
                break;
            }
            else if (a[middle] > num)
                tail = middle - 1;
            else
                head = middle + 1;
        }

        if (flag == -1)
            printf("一共查找了%d次，未找到数据%d \n", count, num);
    }
}


void main()
{
    int a[N], b[N];

    srand((unsigned int)(time(NULL)));
    for (int i = 0; i < N; i++)
    {
        a[i] = i;
        b[i] = a[i] + rand() % 300;
        Sleep(rand() % 10);
    }

    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < N - 1 - i; j++)
        {
            if (b[j] > b[j + 1])
            {
                int temp = b[j];
                b[j] = b[j + 1];
                b[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < N; i++)
        printf("%d ", b[i]);

    int num;
    scanf("%d", &num);

    search(a, num);
    search(b, num);


    system("pause");
}

二分查找

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
#define N 1024


void search(int a[N], int num)                    // 二分查找
{
    int head = 0, tail = N - 1, middle;
    int flag = -1, count=0;

    if (num<a[head])
    {
        printf("要查找的值%d小于数组中的最小值%d，共查找了1次 \n", num, a[head]);
    }
    else if (num>a[tail])
    {
        printf("要查找的值%d大于数组中的最大值%d，共查找了1次 \n", num, a[tail]);
    }
    else
    {
        while (head <= tail)
        {
            middle = (head + tail) / 2;
            printf("head=%d, middle=%d, tail=%d, count=%d \n", head, middle, tail, ++count);
            if (a[middle] == num)
            {
                flag = 1;
                printf("找到了，是a[%d]=%d, 一共查找了%d次 \n", middle, num, count);
                break;
            }
            else if (a[middle] > num)
                tail = middle - 1;
            else
                head = middle + 1;
        }

        if (flag == -1)
            printf("一共查找了%d次，未找到数据%d \n", count, num);
    }
}

void searchByLagrange(int a[N], int num)
{
    int head = 0, tail = N - 1, middle;
    int flag = -1, count = 0;

    if (num<a[head])
    {
        printf("要查找的值%d小于数组中的最小值%d，共查找了1次 \n", num, a[head]);
    }
    else if (num>a[tail])
    {
        printf("要查找的值%d大于数组中的最大值%d，共查找了1次 \n", num, a[tail]);
    }
    else
    {
        while (head <= tail)
        {
            
            /*
                middle = (head + tail) / 2;        // 二分查找
                middle = head + (tail - head) / 2;
            */
            middle = head + (tail - head)*1.0*(num - a[head]) / (a[tail] - a[head]);
            /*
                拉格朗日差值定理
                ((num - a[head]) / (a[tail] - a[head]))  比例不等于0.5
            */

            printf("head=%d, middle=%d, tail=%d, count=%d \n", head, middle, tail, ++count);
            if (a[middle] == num)
            {
                flag = 1;
                printf("找到了，是a[%d]=%d, 一共查找了%d次 \n", middle, num, count);
                break;
            }
            else if (a[middle] > num)
                tail = middle - 1;
            else
                head = middle + 1;
        }

        if (flag == -1)
            printf("一共查找了%d次，未找到数据%d \n", count, num);
    }
}

void main()
{
    int a[N], b[N];

    srand((unsigned int)(time(NULL)));
    for (int i = 0; i < N; i++)
    {
        a[i] = i;
        b[i] = a[i] + rand() % 300;
        Sleep(rand() % 10);
    }

    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < N - 1 - i; j++)
        {
            if (b[j] > b[j + 1])
            {
                int temp = b[j];
                b[j] = b[j + 1];
                b[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < N; i++)
        printf("%d ", b[i]);

    int num;
    scanf("%d", &num);

    search(a, num);
    search(b, num);

    searchByLagrange(a, num);
    searchByLagrange(b, num);

    system("pause");
}

二分查找的进化_拉格朗日定理

0004、插入排序法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20


void main()
{
    srand((unsigned int)(time(NULL)));

    int a[N + 1] = { 0 };
    for (int i = 0; i < N; i++)
        a[i] = rand() / 100;

    a[N] = 77;

    for (int i = 0; i < N + 1; i++)
        printf("%5d", a[i]);
    putchar(‘\n‘);

    for (int i = 0; i < N; i++)            // 冒泡排序(前N个元素)
    {
        for (int j = 0; j < N - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < N + 1; i++)
        printf("%5d", a[i]);
    putchar(‘\n‘);

    int temp = a[N];
    int j = N;
    while (j > 0 && a[j - 1]>temp)
    {
        a[j] = a[j - 1];                     // 数组元素向后平移
        j--;
    }

    a[j] = temp;                    // 将temp插入到适合的位置

    for (int i = 0; i < N + 1; i++)
        printf("%5d", a[i]);
    putchar(‘\n‘);

    system("pause");
}

单个数据的插入

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20


void main()
{
    srand((unsigned int)(time(NULL)));

    int a[N + 1] = { 0 };
    for (int i = 0; i < N; i++)
        a[i] = rand() / 100;

    a[N] = 77;

    for (int i = 0; i < N + 1; i++)
        printf("%5d", a[i]);
    putchar(‘\n‘);


    for (int i = 1; i < N + 1; i++)        // 整体插入排序
    {
        int j = i;
        int temp = a[j];
        while (j > 0 && a[j - 1]>temp)
        {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = temp;                // 将temp插入到适合的位置
    }

    for (int i = 0; i < N + 1; i++)
        printf("%5d", a[i]);
    putchar(‘\n‘);

    system("pause");
}

随机数组的整体插入排序

【0001】排序法与查找方式

原文：https://www.cnblogs.com/ant-colonies/p/13333918.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)