算法
作用: 提高代码运行效率
评判算法是否优良
时间复杂度
预测代码执行所需的时间与关键系数的关系
代码执行时间越短越好
空间复杂度
代码执行所需占用的空间,越小越好
常用算法
两数交换
方式1:
int a=10;
int b=1;
int c = a;a = b;b = c;
方式2:
int a=10;
int b=1;
a=a+b;
b=a-b;
a=a-b;
方式3:
int a=10;
int b=1;
a=a^b;
b=a^b;
a=a^b;
查找最值
步骤:
1,假定容器中的某个值为最大值或最小值
2,遍历该容器
3,使用遍历获取的值与假设的最大值或最小值比较
4,如果变量的值大于最大值或遍历的值小于最小值,那么将遍历获取的值赋值给假设的变
量5,当遍历完成后假设的最值就是真的最值
如:int nums[]={21,56,23,44,76,89,12,0,35,65,78};int max=nums[0];for(int i=0;i<sizeof(nums)/sizeof(nums[0]);i++){if(max<nums[i]){max=nums[i];}}printf(("max = %d\n",max);
查找最值下标
步骤:
1,假定容器中的某个下标对应的值为最大值/最小值
2,遍历该容器3,使用遍历获取的值与假设的最大值 / 最小值下标对应的值进行比较4,如果假设的最值下标对应的值小于遍历获取的值 ( 最大值下标 ) 或大于遍历获取的值(最小值下标 )5,将最值下标修改6,当遍历完成后 , 假设的最值下标就是真的最值下标
如:int nums[] = {21,56,23,44,76,89,12,0,35,65,78};int minIndex=0;for(int i = 0; i < sizeof(nums)/sizeof(nums[0]); i++){if(nums[minIndex] > nums[i]){minIndex = i;}}printf("minIndex = %d\n",minIndex);
冒排排序
思想:相邻比较
如:
int nums[] = {21,56,23,44,76,89,12,0,35,65,78};
int len=sizeof(nums)/sizeof(nums[0]);
for(int j=0;j<len;j++)
{
for(int i=0;i<len-1;i++)
{
if(nums[i]<nums[i+1])
{
int x = nums[i];nums[i] = nums[i+1];nums[i+1] = x;}
}
}
选择排序
思想:逐个比较
如:int nums[] = {21,56,23,44,76,89,12,0,35,65,78};int len = sizeof(nums) / sizeof(nums[0]);for(int j = 0; j < len; j++){for(int i = j; i < len; i++){if(nums[j]>num[i]){int x = nums[j];nums[j] = nums[i];nums[i] = x;}}}
顺序查找
思想:逐个查找
如:
#include <stdio.h>
int main() {
int arr[] = { 12, 25, 37, 41, 53, 62, 78, 84, 91 };
int n = sizeof(arr) / sizeof(arr[0]);
int key = 53;
int i;for (i = 0; i < n; i++) {
if (arr[i] == key) {
break;
}
}if (i < n) {
printf("元素 %d 在数组中的下标是 %d\n", key, i);
} else {
printf("未找到元素 %d\n", key);
}return 0;
}
二分查找
思想:折半法
注意:数组必须是从小到大或从大到小是有序的
如:
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 50;int left = 0;
int right = n - 1;
int mid;
int found = 0;while (left <= right &&!found) {
mid = left + (right - left) / 2;if (arr[mid] == key) {
found = 1;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}if (found) {
printf("元素 %d 在数组中的下标是 %d\n", key, mid);
} else {
printf("未找到元素 %d\n", key);
}return 0;
}
