c语言知识整理4
排序
分类
-
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
-
- 稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，归属于不稳定排序。
- 就地排序：若排序算法所需的辅助空间并不依赖于问题的规模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趋于正无穷。
网友评论