一、输入输出
（1）scanf
scanf 是C语言中的一个标准库函数，用于从标准输入（通常是键盘）读取数据。scanf 函数定义在 <stdio.h> 头文件中。
#include <stdio.h>
int main(void) {
//读取整数
int num;
printf("Enter an integer: ");
scanf("%d", &num); // 读取一个整数
printf("You entered: %d\n", num);
//读取浮点数
float num2;
printf("Enter a floating-point number: ");
scanf("%f", &num2); // 读取一个浮点数
printf("You entered: %f\n", num2);
//读取字符
char ch;
printf("Enter a character: ");
scanf(" %c", &ch); // 读取一个字符，前面的空格用于忽略空白字符
printf("You entered: %c\n", ch);
// 读取字符串
char str[50];
printf("Enter a string: ");
scanf("%s", str); // 读取一个字符串，直到遇到空白字符
printf("You entered: %s\n", str);
// 读取多个数据
int num3;
float fnum;
char ch;
printf("Enter an integer, a floating-point number, and a character: ");
scanf("%d %f %c", &num3, &fnum, &ch); // 读取多个数据
printf("You entered: %d, %f, %c\n", num3, fnum, ch);
char str2[50];
printf("Enter a multi-word string: ");
scanf("%[^\n]", str2); // 读取多单词字符串，直到遇到换行符
printf("You entered: %s\n", str2);
return 0;
}
（2）getchar
功能：该函数从标准输入读取一个字符，并返回该字符的ASCII码值。
#include <stdio.h>
int main(void) {
char ch = getchar(); // 定义char 变量 ch，接收 getchar() 函数返回值做为初值。
printf("ch的数值：%d\n", ch);
printf("ch的字符：%c\n", ch);
return 0;
}
（3）printf
- printf 函数的第一个参数是一个格式字符串，用于指定如何输出后续的参数。例如%d 是一个格式说明符，用于输出整数。
#include <stdio.h> // 引⼊头⽂件 stdio.h , 因为下⾯使⽤了printf() 必须添加此头⽂件。
#define PI 3.14
int main(void) {
int a = 10;
printf("%d\n", a); // %d：格式匹配符，匹配整数。
printf("a = %d\n", a); // a = 在“”中，代表普通字符串， 原样输出。
printf("%d\n", 100);
printf("%f\n", PI); // %f：格式匹配符，匹配小数。
printf("PI = %f\n", PI); // PI = 在“”中，代表普通字符串， 原样输出。
printf("%f\n", 3.45678); // %f：格式匹配符，匹配小数。
int b = 20;
printf("%d + %d = %d\n", a, b, a+b); // +、= 在 “”中，代表普通字符串， 原样输出。
printf("%d + %d = %d\n", 3, 7, 3+7);
return 0; //C程序要求，main 函数要有返回值。借助 return 实现返回。
}
补充：占位符说明
（4）putchar
-
putchar 是C语言中的一个标准库函数，用于向标准输出（通常是终端）输出一个字符。
-
输出字符串：虽然 putchar 一次只能输出一个字符，但可以结合循环来输出整个字符串。
#include <stdio.h>
int main(void) {
char str[] = "Hello, World!";
int i;
for (i = 0; str[i] != '\0'; i++) {
putchar(str[i]); // 输出字符串中的每个字符
}
putchar('\n'); // 输出换行符
return 0;
}
二、变量
1、 变量 3 要素
- 变量名：用来在程序中使用。
- 变量类型：开辟内存空间大小。
- 变量值：存储的实际数据。
2、变量名命名的主要规则：
字母数字和下划线 变量名只能包含字母（A-Z, a-z）、数字（0-9）和下划线（_）。变量名不能以数字开头。
不得使用关键字 变量名不能与C语言的关键字（如 int, char, for, if 等）相同。
3、变量的作用域
变量的作用域决定了变量在哪里可以被访问。主要作用域有：
- 局部变量：在函数内部声明的变量，只在该函数内有效。
- 全局变量：在所有函数之外声明的变量，在整个文件或多个文件中都可访问。
- 形式参数：函数定义中参数列表内的变量，仅在该函数调用期间有效。
- 静态局部变量：使用 static关键字声明的局部变量，其生命周期贯穿整个程序运行期，但是作用域仍限制在声明它的函数内。
#include <stdio.h>
// 全局变量
int globalVar = 100;
void func() {
// 局部变量
int localVar = 200;
printf("Inside function: globalVar = %d, localVar = %d\n", globalVar, localVar);
}
int main() {
func();
printf("In main: globalVar = %d\n", globalVar);
// 下面这行会报错，因为 localVar 是 func 函数内的局部变量
// printf("localVar = %d\n", localVar);
return 0;
}
三、常量
- C语言中，常量是那些在程序执行过程中其值不能被修改的量。
C语言中常量的主要用法：
- 使用 #define 预处理器指令
#define 是一个预处理器指令，用于定义宏常量。宏常量在编译前会被预处理器替换为指定的值。
#include <stdio.h>
#define PI 3.14159
#define MAX 100
int main(void) {
printf("Value of PI: %f\n", PI);
printf("Maximum value: %d\n", MAX);
return 0;
}
- 使用 const 关键字
const 关键字用于声明常量变量。这种常量在内存中分配空间，并且可以在编译时或运行时初始化。
#include <stdio.h>
int main(void) {
const int MAX = 100;
const float PI = 3.14159;
const char GRADE = 'A';
printf("Maximum value: %d\n", MAX);
printf("Value of PI: %f\n", PI);
printf("Grade: %c\n", GRADE);
// 下面这行代码会导致编译错误，因为 MAX 是常量
// MAX = 200;
return 0;
}
- 枚举常量
枚举（enum）是一种特殊的整型常量集合，用于定义一组具名的整数值。
说明：枚举类型 Day 包含七个枚举常量：MON, TUE, WED, THU, FRI, SAT,
SUN。默认情况下，这些枚举常量会被赋予从 0 开始的连续整数值。
#include <stdio.h>
enum Day { MON, TUE, WED, THU, FRI, SAT, SUN };
int main(void) {
enum Day today = WED;
printf("Today is day number: %d\n", today);//Today is day number: 2
return 0;
}
练习：
#include <stdio.h>
#define PI 3.1415926 // 定义常量
int main(void) {
// 圆的面积 ：s = PI * r * r
// 圆的周长 ：L = 2 * PI * r
int r = 3; // 变量的定义。
float s = PI * r * r; // 表达式。作为变量值。
float l = 2 * PI * r;
//printf("圆的面积：%f\n", s);// 28.274334 默认显示 6 位小数。
//printf("圆的周长：%f\n", l);// 18.849556
//printf("圆的面积：%.2f\n", s);// 28.27
//printf("圆的周长：%.2f\n", l);// 18.85指定保留小数点后两位，对第3位四舍五入
float m = 3.4567891;
printf("m=%.2f\n", m);
printf("m=%6.2f\n", m);
//共显示6位数，包含小数点，保留小数点后两位，对第3位四舍五入，不足6位用空格补齐。
printf("m=%06.2f\n", m);
//共显示6位数，包含小数点，保留小数点后两位，对第3位四舍五入，不足6位用0补齐。
return 0;
}
四、sizeof
1、有符号整型
#include <stdio.h>
#include <limits.h>
int main(void) {
printf("int大小 = %u\n", sizeof(int));
printf("int最小值：%d, 最大值：%d\n", INT_MIN, INT_MAX);
printf("short大小 = %u\n", sizeof(short));
printf("short最小值：%hd, 最大值：%hd\n", SHRT_MIN, SHRT_MAX);
printf("long大小 = %u\n", sizeof(long));
printf("long最小值：%ld, 最大值：%ld\n", LONG_MIN, LONG_MAX);
printf("long long大小 = %u\n", sizeof(long long));
printf("long long最小值：%lld, 最大值：%lld\n", LLONG_MIN, LLONG_MAX);
}
2、无符号整型
【扩展】：C语言中引入无符号整型有几个重要的原因，这些原因涉及性能、表示范围、内存利用率以及特定应用场景的需求。以扩大表示范围为例子，无符号整型可以表示更大的正数范围。
五、char
在C语言中，char 类型用于表示字符。char 类型是一个基本的数据类型，通常占用1个字节的内存。以下是关于 char 类型的详细总结：
-
基本属性
-
定义和初始化
#include <stdio.h>
#include <limits.h>
int main(void) {
char ch1 = 'A'; // 单引号表示单个字符
char ch2 = 65; // 使用ASCII码值初始化
printf("%c",ch2); //结果：A
return 0;
}
-
字符常量
-
字符串
-
输入和输出
#include <stdio.h>
int main(void) {
char ch;
printf("Enter a character: ");
scanf("%c", &ch); // 读取一个字符
printf("You entered: %c\n", ch); // 打印字符
return 0;
}
-
ASCII 码
-
字符操作
- 比较字符：可以使用关系运算符比较字符。
- 字符运算：可以对字符进行算术运算，实际上是对其ASCII码值进行运算。
#include <stdio.h>
int main(void) {
char ch1 = 'A';
char ch2 = 'B';
if (ch1 < ch2) {
printf("'%c' comes before '%c'\n", ch1, ch2);//'A' comes before 'B'
}
char ch3 = ch1 + 1; // 'A' + 1 -> 'B'
printf("ch1 + 1 = %c\n", ch3);//ch1 + 1 = B
return 0;
}
- 字符串处理函数
- C标准库提供了许多用于字符串处理的函数，例如 strlen、strcpy、strcat、strcmp 等。
#include <stdio.h>
#include <string.h>
int main(void) {
char str1[20] = "Hello";
char str2[20] = "World";
strcpy(str1, str2); // 复制 str2 到 str1
strcat(str1, "!"); // 连接字符串
printf("str1: %s\n", str1);
int len = strlen(str1); // 获取字符串长度
printf("Length of str1: %d\n", len);
return 0;
}
- 无符号字符
- 如果需要确保 char 类型的值是非负的，可以使用 unsigned char。
#include <stdio.h>
int main(void) {
unsigned char ch = 255; // 无符号字符
printf("Value of ch: %u\n", ch);
return 0;
}
【 练习1 】：将大写字母，转换成 小写字母
#include <stdio.h>
int main(void) {
char ch = 'R'; // char 变量定义
printf("R 转换的小写为：%c\n", ch+32); //ch+32 表达式，对应格式匹配符 %c
char ch2 = 'h'; // char 变量定义
printf("h 转换的大写为：%c\n", ch2-32); //ch2-32 表达式，对应格式匹配符 %c
char ch3 = '5';
// 借助字符5， 利用 ASCII特性，打印出 字符9
printf(" 打印字符9 = %c\n", ch3+4);
return 0;
}
【 练习 2】：在一个printf函数中， 打印输出 hello 换行 world 换行 。
#include <stdio.h>
/*
方法1
int main(void) {
printf("hello\nworld\n");
return 0;
}
*/
//方法2
int main(void) {
char ch = '\n'; //定义ch变量，初值为'\n'
printf("hello%cworld%c", ch, ch); // 等价于 printf("hello\nworld\n");
return 0;
}
六、bool
- 在C语言中，布尔类型（bool）并不是内置类型，而是通过包含 <stdbool.h> 头文件来引入的。bool 类型用于表示真（true）和假（false）两种逻辑值。
1.输出布尔值
可以使用 %d 格式说明符来输出布尔值。true 输出为 1，false 输出为 0。
#include <stdio.h>
#include <stdbool.h>
int main(void) {
bool isTrue = true;
bool isFalse = false;
printf("isTrue: %d\n", isTrue); // 输出 1
printf("isFalse: %d\n", isFalse); // 输出 0
return 0;
}
2.布尔值的整数表示
在C语言中，true 实际上表示整数 1，false 表示整数 0。因此，任何非零值都可以被视为 true，零值被视为 false。
#include <stdio.h>
#include <stdbool.h>
int main(void) {
bool a = 1; // true
bool b = 0; // false
bool c = 10; // true
printf("a: %d\n", a); // 输出 1
printf("b: %d\n", b); // 输出 0
printf("c: %d\n", c); // 输出 1
return 0;
}
3.布尔运算
布尔运算符（如 &&、||、!）可以用于布尔表达式的组合和否定。
#include <stdio.h>
#include <stdbool.h>
int main(void) {
bool a = true;
bool b = false;
bool andResult = a && b; // false
bool orResult = a || b; // true
bool notResult = !a; // false
printf("a && b: %d\n", andResult);
printf("a || b: %d\n", orResult);
printf("!a: %d\n", notResult);
return 0;
}
七、运算符
（1）算数运算符
（2）自增自减运算符
#include <stdio.h>
// ++ / -- 运算符
int main(void) {
// 前缀
int a = 10;
printf("%d\n", ++a); // ++a 等价于 a = a+1；
// 后缀
int b = 10;
printf("%d\n", b++); // b++ 等价于 b = b+1；
// 不管前缀、后缀、含有变量 ++/-- 表达式执行完后，变量均发生了自增、自减。
printf("b = %d\n", b);
return 0;
}
（3）赋值运算符
（4）比较运算符
（5）逻辑运算符
- 0 为假， 非0 为真。（非0: 1、 27、-9）
- 逻辑非(!)
- 规律：非真为假，非假为真。
#include<stdio.h>
// 逻辑运算符
int main(void) {
// 逻辑非
int a = 34; // 34 是非0， 默认 a 为真。
int b = 0;
printf("a = %d\n", !a); // a为真，非a 为假！！---> 0
printf("b = %d\n", !b); // b=0, b为假，非b, 为真。 ---> 1
return 0;
}
- 逻辑与(&&)
- 规律：同真为真，其余为假。
#include<stdio.h>
// 逻辑运算符
int main(void) {
int a = 34; // 34 是非0， 默认 a 为真。
int b = 0;
printf("%d\n", a && !b); // a为真，!b为真， 真&&真 -- 真。 --->1
}
- 逻辑或(||)
- 规律：有真为真，同假为假。
#include<stdio.h>
// 逻辑运算符
int main(void) {
int a = 34; // 34 是非0， 默认 a 为真。
int b = 0;
printf("------%d\n", a || !b); // a为真，!b为真，真||真 -- 真。---> 1
printf("------%d\n", a || b); // a为真，b为假，真||假 --真。---> 1
printf("------%d\n", !a || b); // !a为假，b为假，假||假 --假。---> 0
}
（6）逗号运算符
（7）三目运算符
#include<stdio.h>
// 三目运算
int main(void) {
int a = 40;
int b = 4;
//int m = a > b ? 69 : 10;
//printf("m = %d\n", m); // m = 69；
//int m = a < b ? 69 : 10;
//printf("m = %d\n", m); // m = 10；
// 三目运算支持嵌套
int m = a < b ? 69 : (a<b?3:5); // 先算表达式3，取5，整个三目运算，取表达式3-- >5
printf("m = %d\n", m); // m = 5；
int m2 = a < b ? 69 : a < b ? 3 : 5;
printf("m2 = %d\n", m2); // m = 5；
return 0;
}
【说明】：如果不使用（），三目运算默认的结合性，自右向左。
（8）运算符的优先级
八、if 条件判断
（1）if…else 分支
#include <stdio.h>
int main(void) {
int a;
printf("请输入一个数：");
int ret = scanf("%d", &a);
if (a > 0) {
printf("a > 0\n");
} else {
printf("a <= 0\n");
}
return 0;
}
（2）多个分支逻辑
#include <stdio.h>
int main(void) {
int score;
printf("请输入学生成绩：");
scanf("%d", &score);
if (score >= 90) { // 优秀
printf("优秀\n");
} else if (score >=70 && score < 90) { // 70 < score < 90 错误写法。
printf("良好\n");
} else if (score >= 60 && score < 70) {
printf("及格\n");
} else {
printf("差劲\n");
}
}
九、switch 语句
#include <stdio.h>
int main(void) {
int score;
printf("请输入学生成绩：");
scanf("%d", &score);
// 将 学生成绩，通过运算，得出可以放入 switch case 分支的 表达式。
switch (score/10) {
case 10:
printf("优秀\n");
break; // 表示当前分支结束。
case 9:
printf("优秀\n");
break;
case 8:
printf("良好\n");
break;
case 7:
printf("良好\n");
break;
case 6:
printf("及格\n");
break;
default: // 所有case都不满足的其他情况。
printf("不及格");
break;
}
return 0;
}
备注：case穿透
十、while 循环
#include<stdio.h>
int main(void) {
//7的倍数： num % 7 == 0
//个位含7： num % 10 == 7
//十位含7： num / 10 == 7
int num = 1;
while (num <= 100) {
if (num % 7 == 0 || num % 10 == 7 || num / 10 == 7) {
printf("敲桌子！\n");
} else {
printf("%d\n", num);
}
num++;
}
return 0;
}
十一、do while 循环
练习：
#include<stdio.h>
int main(void) {
//-个位数：int a = num % 10；
//-十位数：int b = num / 10 % 10;
//-百位数：int c = num / 100;
int num = 100; // 数数从 100 开始。
int a, b, c; // 定义存储个位、十位、百位数 的变量。
do {
a = num % 10; // 求个位数。
b = num / 10 % 10;
c = num / 100;
// 判断 这个数字是否是“水仙花数”
if (a * a * a + b * b * b + c * c * c == num){
printf("水仙花数：%d\n", num);
}
num++; // 不断向后数数。
} while (num <= 999);
return 0;
}
十二、for 循环
- 使用 for 循环 求 1~100 的 和
#include <stdio.h>
int main(void) {
int sum = 0; // 初始化累加和为0
// 使用 for 循环从1到100求和
for (int i = 1; i <= 100; i++) {
sum += i; // 累加当前的值
}
// 输出结果
printf("The sum of numbers from 1 to 100 is: %d\n", sum);
return 0;
}
- 特殊语法：
-
十三、嵌套 for 循环
#include <stdio.h>
int main(void) {
for (int i = 0; i < 2; i++) { // 外层循环
for (int j = 0; j < 3; j++) { // 内层循环
printf("Hello World!\n");
}
}
return 0;
}
分析代码：拆解以上循环嵌套的执行过程
第一次外层循环：
i = 0; //i的初始值为0
i < 2 //条件成立，进入内层循环
第一次进入内层循环：
【内层循环第一次：】
j = 0; //j的初始值为0
j < 3 //条件成立
printf("Hello World!\n");//此时输出一次 Hello World!
j++; //j的值变为1
【内层循环第二次：】
j = 1;
j < 3 //条件成立
printf("Hello World!\n");//此时输出一次 Hello World!
j++; //j的值变为2
【内层循环第三次：】
j = 2;
j < 3 //条件成立
printf("Hello World!\n"); //此时输出一次 Hello World!
j++; //j的值变为3
【内层循环第四次：】
j = 3;
j < 3 //条件不成立，内层循环结束
i++; //i的值变为1
第二次外层循环：
i = 1;
i < 2 //条件成立，进入内层循环
第二次进入内层循环：
【内层循环第一次：】
j = 0; //j的初始值为0
j < 3 //条件成立
printf("Hello World!\n"); //此时输出一次 Hello World!
j++; //j的值变为1
【内层循环第二次：】
j = 1;
j < 3 //条件成立
printf("Hello World!\n"); //此时输出一次 Hello World!
j++; //j的值变为2
【内层循环第三次：】
j = 2;
j < 3 //条件成立
printf("Hello World!\n"); //此时输出一次 Hello World!
j++; //j的值变为3
【内层循环第四次：】
j = 3;
j < 3 //条件不成立，内层循环结束
i++; //i的值变为2
第三次外层循环：
i = 2;
i < 2 //条件不成立，外层循环结束，整个循环都终止了
练习：打印乘法口诀表
#include <stdio.h>
int main(void) {
// 外层循环控制行数
for (int i = 1; i <= 9; i++) {
// 内层循环控制列数
for (int j = 1; j <= i; j++) {
// 打印乘法口诀表的一个项
printf("%d*%d=%d ", j, i, i * j);
}
// 每一行结束后换行
printf("\n");
}
return 0;
}
十四、语句跳转
- 在流程控制语句中还有一类“跳转语句”，主要用来中断当前的执行过程。
（1）break
- 当代码中遇到break时，会直接中断距离最近的循环，跳转到外部继续执行。
#include <stdio.h>
int main(void) {
int i = 1;
while (1) { // 使用1表示无限循环
printf(" 这是第%d次输出\n", i);
i++;
if (i > 5) {
break; // 当 i 大于 5 时退出循环
}
}
return 0;
}
结果：
（2）continue
- continue语句表示“继续”执行循环，也就是中断循环中的本次迭代，并开始执行下一次迭代。
//需求：输出1到10之间所有的整数，5不输出
#include <stdio.h>
int main(void) {
for (int i = 1; i <= 10; i++) {
if (i == 5) {
continue; // 当 i 等于 5 时跳过本次循环
} else {
printf("这是第%d次输出\n", i);
}
}
return 0;
}
结果：
十五、数组
- 基本特性
- 数组初始化
- 练习：数组元素逆序
#include <stdio.h>
// 数组元素逆序
int main(void) {
int arr[] = {1, 6, 8, 0, 4, 3, 9, 2}; // 变为：{2, 9, 3, 4, 0, 8, 6, 1}
// 获取数组的元素个数
int n = sizeof(arr) / sizeof(arr[0]);
int i = 0; // 从前向后
int j = n-1; // 从后向前
int tmp = 0; // 定义临时变量。
// 交换数组元素之前，打印数组的所有元素。
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
putchar('\n');
// 循环交换数组元素。
while (i < j) {
tmp = arr[i]; // 三杯水变量交换法
arr[i] = arr[j];
arr[j] = tmp;
i++; // 不断后移
j--; // 不断前移
}
// 交换数组元素之后，打印数组的所有元素。
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
putchar('\n');
return 0;
}
1.查找算法
（1）顺序查找
思路：
- 遍历列表。
- 找到跟目标值相等的元素，就返回他的下标。
- 遍历结束后，如果没有搜索到目标值，就返回-1。
参考代码：
#include <stdio.h>
int main(void) {
int a[5] = {4, 5, 2, 3, 1};
int target = 1;
int len = sizeof(a) / sizeof(a[0]);
bool b = false;
for (int i = 0; i < len; i++) {
if (target == a[i]) {
printf("%d\n", i);
b = true;
}
}
if (!b) {
printf("-1\n");
}
return 0;
}
时间复杂度：O(n)
（2）二分查找
【注意】：二分查找的前提是数字是排序好的。
思路：
- 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。
- 如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索。
动画演示：
#include <stdio.h>
int main(void) {
int a[5] = {4, 5, 8, 9, 15};
int target = 5;
int len = sizeof(a) / sizeof(a[0]);
int left = 0;
int right = len - 1;
bool b = false;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] < target) {
left = mid + 1;
} else if (a[mid] > target) {
right = mid - 1;
} else {
printf("%d\n", mid);
b = true;
break;
}
}
if (!b) {
printf("找不到该数字\n");
}
return 0;
}
时间复杂度：O(logn）
3. 排序算法
菜鸡三人组：
- 冒泡排序
- 选择排序
- 插入排序
牛逼三人组：
- 快速排序
- 堆排序（难）
- 归并排序（较难）
（1）冒泡排序
思路：
- 1.比较所有相邻的元素，如果第一个比第二个大，则交换他们。
- 2.一轮下来，可以保证最后一个数是最大的。
- 3.以此类推，执行n-1轮，就可以完成排序。
- 动画演示：
代码参考：
#include <stdio.h>
int main(void) {
int a[] = {6, 5, 4, 1, 3, 2};
int len = sizeof(a) / sizeof(a[0]);
// 冒泡排序
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1; 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 < len; i++) {
printf("%d ", a[i]);
}
printf("\n"); // 输出换行符
return 0;
}
- 思考：以上代码能否进行优化呢？内层循环需要每次都遍历0~len-1次吗？？
- 回答：不需要，因为随着外层循环次数的增加，数组末尾的排序会依次确定好位置，例如，第一轮会确定6的位置，第二轮会确定5的位置。所以，内层循环不需要每次都遍历0~len-1次，只需要遍历len-1-i 次就够了。
优化后的代码：
#include <iostream>
using namespace std;
int main() {
int a[] = {6,5,4,1,3,2};
int len = sizeof(a) / sizeof(a[0]);
for(int i = 0; i < len-1; i++) {
for(int j = 0; j < len-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 < len; i++) {
cout << a[i] << " ";
}
}
冒泡排序时间复杂度：O(n2)
（2）选择排序
思路：
- 1.找到数组中的最小值，把他更换到列表中的第一位。（具体做法：先假设第一数为最小值，记录它的索引值，将第一数和第二个数作比较，如果第一个数大于第二个数，将最小索引值记录为第二个数，依次循环比较，一轮比较下来，最小值所在的索引位置就会被找到，并且把他更换到最开头的位置。
- 2.接着找到第二小的值，把他更换到数组中的第二位。
- 3.以此类推，执行n-1轮，就可以完成排序。
- 动画演示：
参考代码：
#include <stdio.h>
int main(void) {
int a[] = {6, 5, 4, 1, 3, 2};
int len = sizeof(a) / sizeof(a[0]);
// 冒泡排序
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 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 < len; i++) {
printf("%d ", a[i]);
}
printf("\n"); // 输出换行符
return 0;
}
选择排序时间复杂度：O(n2)
（3）插入排序
插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。
基本思路：
- 在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。
具体步骤：
- 从第二个元素开始，依次将元素插入已经排序好的部分。
- 遍历已排序好的部分，找到合适的插入位置。
- 将待排序的元素插入合适的位置。
- 将大于待排序元素的元素向后移动一个位置。
- 依次类推，完成插入排序。
例子：
插入排序的总体过程，类似我们打牌，摸牌后进行依次插入的过程：
举例：假如已经进行到31这个数了，31前面的数我们已经插入排序完毕了；那么对于31这个数，我们需要先将其与93比较，31<93，交换位置；接着比较31<77，交换位置；接着比较31<54，交换位置；接着比较31>26，不需要交换位置了，此时内层循环可以结束了。
动画演示：
代码参考：
#include <stdio.h>
int main(void) {
int a[] = {5, 3, 4, 7, 2};
int len = sizeof(a) / sizeof(a[0]);
for (int i = 1; i < len; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && key < a[j]) {
a[j + 1] = a[j];
j -= 1;
}
a[j + 1] = key;
// 输出当前排序状态
for (int z = 0; z < len; z++) {
printf("%d ", a[z]);
}
printf("\n"); // 输出换行符
}
return 0;
}
插入排序的外层循环为for循环 + 内层循环为while循环，所以时间复杂度为 O(n2)
（4）快速排序
- 第一轮排序的代码：
#include <iostream>
#include <vector>
using namespace std;
// 遍历数组
void printVector(const vector<int>& vec) {
for (int num : vec) {
cout << num << " ";
}
cout << endl;
}
// 归位函数
void partition(vector<int>& vec, int left, int right) {
int tmp = vec[left];
while (left < right) {
while (left < right && vec[right] >= tmp) { // 从右边找出比tmp小的数
--right; // 往左移动一步
}
vec[left] = vec[right]; // 把右边的值给到左边的空缺位置
printVector(vec);
while (left < right && vec[left] <= tmp) {
++left;
}
vec[right] = vec[left];
printVector(vec);
}
vec[left] = tmp; // 将tmp进行归位
}
int main() {
vector<int> vec = {5, 7, 4, 6, 3, 1, 2, 9, 8};
printVector(vec);
partition(vec, 0, vec.size() - 1);
printVector(vec);
}
结果：
问题解析:
问: 为何是先从右往左进行查找?
答: 因为左边空出了位置, 从右往左找出比tmp小的数字, 可以放到left指针所在的位; 如果一开始从左往右查找, 右边并没有空余位置。
代码解析1:
while (left < right && vec[right] >= tmp)
问: 以上这行代码为何添加条件判断 left < right
答: 因为如果不添加, right可能会跑到left的左边, 比如5 6 7,right指针最终会移动到5所在位置的左边，vec[right]就取不到元素了
# 代码解析2:
while (left < right && vec[right] >= tmp)
问: 以上这行代码为何是 vec[right] >= tmp, 不能是vec[right] > tmp:
答: 因为如果是vec[right] > tmp, 假如列表为5 6 5 7, right指针移动到5所在位置就会停止了, 此时
列表的顺序为: 5 6 5 7, left指针也会一直停留在左边5的位置, 循环无法跳出来.
- 添加递归函数，实现左右两边也进行快速排序，最终版代码：
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& vec, int left, int right) {
int tmp = vec[left];
while (left < right) {
while (left < right && vec[right] >= tmp) { // 从右边找出比tmp小的数
--right; // 往左移动一步
}
vec[left] = vec[right]; // 把右边的值给到左边的空缺位置
while (left < right && vec[left] <= tmp) {
++left;
}
vec[right] = vec[left];
}
vec[left] = tmp; // 将tmp进行归位
return left;
}
void quick_sort(vector<int>& vec, int left, int right) {
if (left < right) { // 至少存在两个元素
int mid = partition(vec, left, right);
quick_sort(vec, left, mid - 1);
quick_sort(vec, mid + 1, right);
}
}
int main() {
vector<int> vec = {5, 7, 4, 6, 3, 1, 2, 9, 8};
quick_sort(vec, 0, vec.size() - 1);
for (int num : vec) {
cout << num << " ";
}
cout << endl;
}
结果：
快速排序时间复杂度：O（nlogn）
（5）归并排序
-
理解一次归并
-
一次归并动画演示：点我观看
-
一次归并的代码：
#include <iostream>
#include <vector>
void mergeOne(std::vector<int>& arr, int low, int mid, int high) {
int i = low;
int j = mid + 1;
std::vector<int> temp; // 临时存储排序后的元素
// 合并两个有序子数组
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp.push_back(arr[i]);
i++;
} else {
temp.push_back(arr[j]);
j++;
}
}
// 如果左边还有元素，全部加入临时数组
while (i <= mid) {
temp.push_back(arr[i]);
i++;
}
// 如果右边还有元素，全部加入临时数组
while (j <= high) {
temp.push_back(arr[j]);
j++;
}
// 将临时数组中的元素拷贝回原数组
for (int k = low; k <= high; ++k) {
arr[k] = temp[k - low];
}
}
int main() {
std::vector<int> li = {2, 5, 7, 8, 9, 1, 3, 4, 6};
mergeOne(li, 0, 4, 8);
// 输出排序后的数组
for (int num : li) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
-
归并排序整体思路：【递归解决：先分解，再合并】
-
归并排序图解：
- 归并排序最终代码：
#include <iostream>
#include <vector>
void mergeOne(std::vector<int>& arr, int low, int mid, int high) {
int i = low;
int j = mid + 1;
std::vector<int> temp; // 临时存储排序后的元素
// 合并两个有序子数组
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp.push_back(arr[i]);
i++;
} else {
temp.push_back(arr[j]);
j++;
}
}
// 如果左边还有元素，全部加入临时数组
while (i <= mid) {
temp.push_back(arr[i]);
i++;
}
// 如果右边还有元素，全部加入临时数组
while (j <= high) {
temp.push_back(arr[j]);
j++;
}
// 将临时数组中的元素拷贝回原数组
for (int k = low; k <= high; ++k) {
arr[k] = temp[k - low];
}
}
void mergeSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
mergeOne(arr, low, mid, high);
}
}
int main() {
std::vector<int> li = {5, 2, 8, 7, 9, 3, 4, 6, 1};
mergeSort(li, 0, li.size() - 1);
// 输出排序后的数组
for (int num : li) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
归并排序时间复杂度：O（nlogn）
![[JavaWeb]微头条项目](https://i-blog.csdnimg.cn/direct/0c31d247d38e4f1783db876d54c63591.png)
