c语言知识整理4

排序

分类

• 快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

• 1. 稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，归属于不稳定排序。
  2. 就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1），则称为就地排序。

三种基本排序方法

冒泡

比较相邻的两个数，如果前者比后者大，则进行交换。每一轮排序结束，选出一个未排序中最大的数放到数组后面。

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

选择

依次选出数组最小的数放到数组的前面。

int main()
{
        int a[10] = { 2,4,7,1,6,9,8,3,0,5 };
        int temp = 0;
        for (int i = 0; i < 10 - 1; i++)
        {
               for (int j = i + 1; j < 10 ; j++)
               {
                       if (a[i] > a[j])
                       {
                              temp = a[i];
                              a[i] = a[j];
                              a[j] = temp;
                       }
               }
        }
        for (int i = 0; i < 10; i++)
               printf("%d  ", a[i]);
        printf("\n");
        return 0;
}

插入

当前面的元素比后面大时，先把后面的元素存入临时变量，前面元素的值放到后面元素位置，再到最后把其值插入到合适的数组位置。

int main(int argc, char *argv[])
{
        int a[10] = { 2,4,7,1,6,9,8,3,0,5 };
        for (int i = 1; i < 10; i++)
        {
               int temp = a[i];
               int j = 0;
               for (j = i - 1; j >= 0; j--)
               {
                       if (a[j] > temp)
                       {
                              a[j + 1] = a[j];
                       }
                       else
                       {
                              break;
                       }
               }
               a[j + 1] = temp;
        }
        for (int i = 0; i < 10; i++) {
               printf("%d  ", a[i]);
        }
        printf("\n");
        return 0;
}

随机数生成

#include<stdlib.h>
#include<time.h>
int myRandom(int max){
srand((unsigned int)time (NULL));
return rand()%(max + 1);
}

项目实战

杀人游戏

终端输入参与的人数：7, 大家围成一圈,请输入死亡编号：3, 凡是报道3的人都死亡,后面的人继续数数, 输出最后一个活着的人的编号

#include "pch.h"
#include <iostream>
#define die -1

int main()
{
    int total = 0;
    int num[20];
    int killNum = 0;
    int dieNum = 0;
    int count = 0;
//初始设定
    printf("请输入参加游戏人数：");
    scanf_s("%d", &total);
    printf("请输入死亡编号：");
    scanf_s("%d", &killNum);
    for (int i = 0; i < total; i++) {
        num[i] = i + 1;
    }
//游戏规则执行
    for (int i = 0; i < total; i++) {
        if (num[i] != die) {
            count++;
        }
        if (count == killNum) {
            num[i] = die;
            dieNum++;
            count = 0;
            if (dieNum == total - 1) {
                break;
            }
            
        }
        if (i == total - 1) {
            i = -1;
        }
    }
    for (int i = 0; i < total; i++) {
        if (num[i] != die) {
            printf("最终活下来的是：%d号", i + 1);
        }
    }
    /*for (int i = 0; i < total; i++) {
        printf("%d ", num[i]);
    }*/

    return 0;
}

猜数字

随机产生4个不重复的 0-9 之间的整数,从小到大排序,输入猜测的数字,A表示数字正确 位置正确的个数, B表示数字正确 位置不正确

#include "pch.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
int main() {
    int num[4];
    int ans[4];
    int a = 0;
    int b = 0;
//产生不重复的随机数
    srand(time(NULL));
    for (int i = 0; i < 4; i++) {
        num[i] = rand() % 9 + 1;
        for (int j = 0; j < i; j++) {
            if (num[i] == num[j]) {
                i--;
            }
        }
    }
//对随机数排序
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < i; j++) {
            if (num[i] < num[j]) {
                int temp = 0;
                temp = num[j];
                num[j] = num[i];
                num[i] = temp;
            }
        }
    }
//正确答案显示
    /*printf("正确答案：");
    for (int i = 0; i < 4; i++) {
        printf("%d", num[i]);
    }
    printf("\n");*/
//游戏执行操作
    while (1) {
        printf("请输入你的答案：");
        int n = 0;
        scanf_s("%d", &n);
//分解
        ans[0] = n / 1000;
        ans[1] = n / 100 % 10;
        ans[2] = n / 10 % 10;
        ans[3] = n % 10;
//判断
        for (int i = 0; i <= 3; i++) {
            for (int j = 0; j <= 3; j++) {
                if (num[i] == ans[j]) {
                    if (i == j) {
                        a++;
                    }
                    else {
                        b++;
                    }
                }
            }
        }
        if (a == 4) {
            printf("You are right");
            break;
        }
        else {
            printf("%dA%dB\n", a, b);
            a = 0;
            b = 0;
        }
    }
    return 0;
}

体会

又是烧（tuo）脑（fa）的一天，昨天制作了杀人游戏当时在数组怎么连成环的地方想了很久，没想到还能这么简单。对于边产生随机数边排序的做法还是有点绕（=，=）可能本辣鸡只适合分开做，，开始补脑的第二天。在此郑重批评6711，在我写这篇文章的时候她成功关了三次我的网页，未遂n次n趋于正无穷。