数据结构 6（算法）
一、算法
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;
}