八、算法程序设计 数据结构 算法算法解决特定问题的步骤。1.算法的设计1)正确性语法正确合法的输入能得到合理的结果。对非法的输入给出满足要求的规格说明对精心选择甚至刁难的测试都能正常运行结果正确2)可读性便于交流阅读理解 高内聚 低耦合3)健壮性输入非法数据能进行相应的处理而不是产生异常4)高效率时间复杂度5)低存储空间复杂度6)算法空间复杂度算法执行过程中额外开辟的空间随数据量n的变化关系。O(1)O(n)7)算法时间复杂度执行这个算法所花时间的度量将数据量增长和时间增长用函数表示出来这个函数就叫做时间复杂度。一般用大O表示法On-----时间复杂度是关于数据n的一个函数随着n的增加时间复杂度增长较慢的算法时间复杂度低时间复杂度的计算规则(1)用常数1 取代运行时间中的所有加法常数(2)在修改后的运行函数中只保留最高阶项。(3)如果最高阶存在且系数不是1则去除这个项相乘的常数。Fun(int a,int b) O(1){1 Int tmp a; O1 n O1A b;B tmp;}for(i0;in; i2) O(n) n O(n){3n/2 Int tmp a;A b;B tmp; O(n}for (i 1; i n; i * 2) 1*2*2*2*2*2... n{2 ^x no(logn)}for(i0;in;i) o(nlogn){for (i 0; i n; i*2){xxx;}}for(i0;in; i) 0 1 2 ..... n-1{for(ji;jn;j) n n-1 n-2 1{Int tmp a; (n1)n/2 n^2A b;B tmp;}}O(1)O(logn)O(n)O(nlogn)O(n^2)O(n^3)O(2^n)O(n!)O(n^n)2.常用排序和查找算法1)常用排序(1)选择排序*(2)冒泡排序*(3)插入排序*(4)希尔排序(5)快速排序*2)查找算法(1)二分查找*前提条件序列必须有序时间复杂度Ologn插入排序思想将待排的数据插入到一个已有序的序列中确保每次插入之后该序列仍然有序。时间复杂度O(n^2)空间复杂度O(1)稳定性稳定的(2)希尔排序思想将待排序列根据增量划分成若干个子序列分别对这些子序列进行插入排序。时间复杂度O(nlongn)~O(n^2)空间复杂度O1稳定性不稳定void shell_sort(int *a, int len){int inc 0;int i 0, j 0, tmp 0;for (inc len/2; inc 0; inc / 2){for (i inc; i len; i){tmp a[i];j i;while (j inc tmp a[j-inc]){a[j] a[j-inc];j - inc;}a[j] tmp;}}}(3)快速排序思想选取基准值从两端向中间比较比基准值大的放在序列的右边比基准小的放在序列的左边经过一趟排序优先排好基准值。时间复杂度Onlogn空间复杂度Ologn稳定性不稳定void quick_sort(int *a, int begin, int end){if (begin end){return ;}int i begin;int j end;int key a[i];while (i j){while (i j key a[j]){--j;}a[i] a[j];while (i j key a[i]){i;}a[j] a[i];}a[i] key;quick_sort(a, i1, end);quick_sort(a, begin, i-1);}