数据结构-5
时间复杂度、算法
程序设计 = 数据结构 + 算法
算法就是对数据进行操作的流程与步骤。
算法基本要求：
正确性
语法书写合法，合法输入能够得到正确结果；对非法输入按规范处理，各类极端测试用例也可正常运行。
可读性
代码便于阅读、交流与理解，遵循高内聚、低耦合的设计原则。
健壮性
接收非法数据时可正常处理，不会出现程序异常、崩溃等问题。
高效率
对应时间复杂度，尽量减少算法执行耗时。
低存储
对应空间复杂度，算法运行过程中占用的内存空间尽可能小。
时间复杂度：
时间复杂度用来度量算法的执行耗时，描述数据规模n和运行时间的增长关系，统一使用大 O 表示法O(...)。
数据量n越大，复杂度增长越慢的算法，执行效率越高。
时间复杂度计算规则：
- 用常数 1 替换运行时间里所有加法常数
- 只保留表达式中的最高阶项
- 若最高阶项带有不为 1 的系数，直接去除系数
常见时间复杂度及代码示例：
O (1) 常数阶：
voidFun(inta,intb){inttmp=a;a=b;b=tmp;}O (n) 线性阶：
for(inti=0;i<n;i+=2){inttmp=a;a=b;b=tmp;}O (logn) 对数阶：
// 初始值为1，每次 *=2，执行次数为log₂(n)for(inti=1;i<n;i*=2){...}O (nlogn) 线性对数阶：
外层循环复杂度为 (O(n))，内层循环复杂度为 (O(\log n))，整体复杂度为两者相乘。
// 外层循环：O(n)，执行n次for(inti=0;i<n;i++){// 内层循环：O(logn)，每次j *=2，执行log₂(n)次for(intj=1;j<n;j*=2){...}}O (n²) 平方阶：
for(i=0;i<n;i++){for(j=i;j<n;j++){inttmp=a;a=b;b=tmp;}}排序与查找算法
排序稳定性定义：
待排序序列中存在相同元素，排序完成后，相同元素的相对位置没有发生改变，则该排序算法为稳定排序。
冒泡排序：
排序思想：相邻元素两两对比，逆序则交换位置。每一轮排序都会将当前未排序区间的最大值移至末尾。
时间复杂度：(O(n^2))
稳定性：稳定
for(inti=0;i<len-1;i++){for(intj=0;j<len-1-i;j++){if(a[j]>a[j+1])swap(a[j],a[j+1]);}}选择排序：
排序思想：遍历待排序区间，找出区间内最小值，与区间首位元素交换。每一轮确定一个最小值的最终位置。
时间复杂度：(O(n^2))
稳定性：不稳定（元素为跳跃式交换）
for(inti=0;i<len-1;i++){for(intj=i+1;j<len;j++){if(a[i]>a[j])swap(a[i],a[j]);}}插入排序：
排序思想：将元素逐个插入到前方已排序的有序序列中，保证插入后整体序列依旧有序。
时间复杂度：(O(n^2))
稳定性：稳定
for(i=1;i<len;i++){j=i;tmp=a[i];while(j>0&&tmp<a[j-1]){a[j]=a[j-1];j--;}a[j]=tmp;}希尔排序：
排序思想：将原序列拆分为多个子序列，对子序列分别做插入排序；不断缩小分组间隔，最终完成整体排序。
时间复杂度：(O(n\log n) \sim O(n^2))
稳定性：不稳定
intinsert_sort(int*a,intsize){inti=0;inttmp=0;intlen=10;for(i=1;i<len;i++){intj=i;tmp=a[j];while(j>0&&tmp<a[j-1]){if(tmp<a[j-1]){a[j]=a[j-1];j--;}}a[j]=tmp;}return0;}voidshell_sort(int*a,intsize){inti=0;intinc=size/2;inttmp=0;for(i=inc;i>0;i/=inc){insert_sort(a,10);}return;}快速排序：
排序思想：选取一个基准值，双指针从两端向中间遍历，小于基准值的元素放左侧，大于基准值的元素放右侧。一趟排序后基准值归位，再递归处理左右两个子区间。
时间复杂度：(O(n\log n))
稳定性：不稳定
intquick_sort(int*a,intbegin,intend){if(begin>=end){return0;}inti=begin;intj=end;intkey=a[i];while(i<j){while(i<j&&a[j]>=key){j--;}a[i]=a[j];while(i<j&&a[i]<=key){i++;}a[j]=a[i];}a[i]=key;quick_sort(a,begin,i-1);quick_sort(a,i+1,end);return0;}二分查找（折半查找）：
前置条件：待查找序列必须有序
// 二分查找intbinary_search(int*a,intlen,intaim_num){intbegin=0;intend=len-1;intfindcnt=0;while(begin<=end){findcnt++;intmid=(begin+end)/2;if(aim_num==a[mid]){printf("find num is %d\n",a[mid]);printf("cnt is %d\n",findcnt);return0;}if(aim_num>a[mid]){begin=mid+1;}if(aim_num<a[mid]){end=mid-1;}}printf("num not be find\n ");return-1;}