【数据结构学习7】算法基本概念及【排序算法】和【查找算法】动图解释（C语言实现）
文章目录算法一、算法的基础知识二、排序算法2.1 选择排序2.2 冒泡排序2.3 插入排序2.4 希尔排序2.5 快速排序三、查找算法3.1 二分查找折半查找算法一、算法的基础知识程序设计 数据结构 算法算法解决特定问题的步骤。算法设计遵循的五个原则1.正确性语法正确合法的输入能得到合理的结果。2.可读性便于交流阅读理解 高内聚 低耦合。3.健壮性输入非法数据能进行相应的处理而不是产生异常对非法的输入给出满足要求的规格说明对精心选择甚至刁难的测试都能正常运行结果正确。4.高效率(时间复杂度)5.低存储(空间复杂度)空间复杂度算法执行过程中额外开辟的空间随数据量n的变化关系。时间复杂度执行这个算法所花时间的度量。将数据量增长和时间增长用函数表示出来这个函数就叫做时间复杂度。一般用大O表示法On----- 时间复杂度是关于数据n的一个函数随着n的增加时间复杂度增长较慢的算法时间复杂度低时间复杂度的计算规则用常数1 取代运行时间中的所有加法常数在修改后的运行函数中只保留最高阶项。如果最高阶存在且系数不是1则去除这个项相乘的常数。下面是一些例子时间复杂度O(1)Fun(inta,intb)O(1){inttmpa;O(1)ab;btmp;}时间复杂度O(n)for(i0;in;i2){inttmpa;//循环次数3\(\boldsymbol{n/2}\)ab;btmp;}时间复杂度O(logn)for(i1;in;i*2)//1*2*2*2*2*2... n{// 2^x n}时间复杂度O(nlogn)for(i0;in;i){for(i0;in;i*2){xxx;}}时间复杂度O(n^2)for(i0;in;i)// i取 012 …… n‑1{for(ji;jn;j)// 循环次数依次n, n‑1, n‑2 …… 1{inttmpa;ab;btmp;}}所以时间复杂度由小到大排序为O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn)二、排序算法2.1 选择排序思想将待排位置的数据和后面的数据以此进行比较按照升序降序要求将较小值较大值存储在待排位置。时间复杂度O(n2)空间复杂度O(1)稳定性不稳定#includestdio.hintmain(void){intcount0;inttemp0;scanf(%d,count);inta[count];for(inti0;icount;i){scanf(%d,a[i]);}intlensizeof(a)/sizeof(a[0]);for(inti0;ilen-1;i){for(intji1;jlen;j){tempa[i];if(a[i]a[j]){a[i]a[j];a[j]temp;}}}for(inti0;ilen;i){printf(%d ,a[i]);}printf(\n);return0;}2.2 冒泡排序思想将相邻两两数据进行比较按照升序降序要求将较大值较小值交换到两两中的后者位置经过一次循环先找到最大值然后依次往下。时间复杂度O(n2)空间复杂度O(1)稳定性稳定#includestdio.hintmain(void){intcount0;inttemp0;scanf(%d,count);inta[count];for(inti0;icount;i){scanf(%d,a[i]);}intlensizeof(a)/sizeof(a[0]);for(inti0;ilen-1;i){for(intj0;jlen-1-i;j){tempa[j];if(a[j]a[j1]){a[j]a[j1];a[j1]temp;}}}for(inti0;ilen;i){printf(%d ,a[i]);}printf(\n);return0;}2.3 插入排序思想将待排的数据插入到一个已有序的序列中确保每次插入之后该序列仍然有序。时间复杂度O(n2)空间复杂度O(1)稳定性稳定的voidsort_charu(int*pa,intlen){intj0;inttmp0;for(inti1;ilen;i){ji;tmppa[i];while(j0tmppa[j-1]){pa[j]pa[j-1];--j;}pa[j]tmp;}}2.4 希尔排序思想将待排序序列根据增量划分成若干个子序列分别对这些子序列进行插入排序。时间复杂度O(nlogn)~O(n2)空间复杂度O(1)稳定性不稳定voidshell_sort(int*pa,intlen){intinclen/2;inti0,j0;inttmp0;while(inc0){for(iinc;ilen;i){ji;tmppa[i];while(jinctmppa[j-1]){pa[j]pa[j-inc];jj-inc;}pa[j]tmp;}inc/2;}}2.5 快速排序思想选取基准值从两端向中间比较比基准值大的放在序列的右边比基准小的放在序列的左边经过一趟排序优先排好基准值。时间复杂度O(nlogn)空间复杂度O(logn)稳定性不稳定voidquick_sort(int*pa,intbegin,intend){if(beginend){return;}intibegin,jend;intkeypa[i];while(ij){while(ijkeypa[j]){--j;}pa[i]pa[j];while(ijkeypa[i]){i;}pa[j]pa[i];}pa[i]key;quick_sort(pa,i1,end);quick_sort(pa,begin,i-1);}注动图解释来源十大经典排序算法三、查找算法3.1 二分查找折半查找前提条件序列必须为有序序列。思想在升序序列降序中将要查找的值与序列中间位置的值进行比较若比中间值大则在后半前半序列中继续二分查找如果比中间值小则从前半后半个序列中继续二分查找。intbin_find(int*pa,intlen,intdata){intleft0;intrigthlen-1;while(leftrigth){intmidleft(rigth-left)/2;if(pa[mid]data){returnpa[mid];}elseif(datapa[mid]){rigthmid-1;}elseif(datapa[mid]){leftmid1;}}return-9999;}