一、算法
1、概念
问题的求解方法
2、算法的特性和设计要求
算法的特性：
确定性 有穷性 输入输出 可行性
设计要求：
正确性 高效性 低存储 健壮性 可读性
3、时间复杂度O(n)
用于评估程序执行所需的时间
O(n)记法： 只保留最高阶部分
例题：
4、快速排序
思想：
每次取待排序中的一个元素作为基准，将序列分为比基准大和比基准小两个部分
再分对这两个部分别进行快速排序，直到每个部分都只有一个元素时，结束快速排序
#include <stdio.h>
//一次快排需要返回最后基准的位置
int one_sort(int *p,int low,int high)
{
int base = *(p+low);
while(high>low)
{
//high一侧的数据比基准更大
while(*(p+high)>=base&&high>low)
{high--;}
*(p+low) = *(p+high);
while(*(p+low)<=base&&high>low)
{low++;}
*(p+high) = *(p+low);
}
*(p+low)=base; //将基准放在中间位置
return low;
}
void sort(int *p,int low,int high)
{
int ret;
if(high>low) //说明序列中不止一个元素
{
ret = one_sort(p,low,high);
sort(p,low,ret-1);
sort(p,ret+1,high);
}
}
int main(int argc, const char *argv[])
{
int arr[]={50,36,66,76,36,12,25,95};
sort(arr,0,sizeof(arr)/sizeof(int)-1);
for(int i=0;i<sizeof(arr)/sizeof(int);i++)
{
printf("%d\n",arr[i]);
}
return 0;
}5、直接插入排序
思想：
假定序列中的元素有序（只有一个元素时，序列一定时有序的），将其他的元素插入到已经排好的序列中并排序。
#include <stdio.h>
void insert_sort(int *p,int len)
{
int i,j,temp;
//外层循环获取要插入的每一个元素
for(i=1;i<len;i++)
{
//把每次要插入的数据保存
temp = p[i];
//内层循环找到元素应该插入的位置
//因为是顺序结构，插入的同时需要保证其他数据不变
//需要将插入位置后面的元素后移
//后移的就是比我插入元素更大的数
for(j=i;j>0&&p[j-1]>temp;j--)
{
p[j] = p[j-1];
}
//退出循环说明找到了要插入的位置
p[j] = temp;
}
}
int main(int argc, const char *argv[])
{
int arr[]={50,36,66,76,36,12,25,95};
int len = sizeof(arr)/sizeof(arr[0]);
insert_sort(arr,len);
for(int i=0;i<len;i++)
{
printf("%d\n",arr[i]);
}
return 0;
}二、查找算法
根据给定关键字，在序列中查找该关键字的操作
1、二分查找（条件：数列有序）
思想：
每次都使用序列中的中间值和给定的关键字比较，
中间值比关键字更大就去比中间值更小的一侧查找，
中间值比关键字更小就去比中间值更大的一侧查找。
#include <stdio.h>
int half_search(int *p,int start,int end,int key)
{
int mid;
//查找算法，即使只有一个数也要判断
while(end>=start)
{
//找到中间值
mid = (start+end)/2; //中间值的下标
if(p[mid]>key)
{
end = mid-1; //更新序列的终止位置
}
else if(p[mid]<key)
{
start = mid+1; //更新序列的起始位置
}else if(p[mid]==key)
{
return mid;
}
}
}
int main(int argc, const char *argv[])
{
int arr[]={50,36,66,76,36,12,25,95};
int len = sizeof(arr)/sizeof(arr[0]);
printf("%d\n",half_search(arr,0,len-1,76));
return 0;
}