1.基础概念程序设计数据结构算法算法解决特定问题的步骤。算法的设计1.正确性语法正确合法的输入能得到合理的结果。对非法的输入给出满足要求的规格说明对精心选择甚至刁难的测试都能正常运行结果正确2.可读性便于交流阅读理解高内聚 低耦合3.健壮性输入非法数据能进行相应的处理而不是产生异常4.高效率(时间复杂度)5.低存储空间复杂度》空间复杂度算法执行过程中额外开辟的空间随数据量n的变化关系。O(1)O(n)》算法时间复杂度执行这个算法所花时间的度量将数据量增长和时间增长用函数表示出来这个函数就叫做时间复杂度。一般用大O表示法On-----时间复杂度是关于数据n的一个函数随着n的增加时间复杂度增长较慢的算法时间复杂度低》时间复杂度的计算规则1.用常数1取代运行时间中的所有加法常数2.在修改后的运行函数中只保留最高阶项。3.如果最高阶存在且系数不是1则去除这个项相乘的常数。常用排序和查找算法1.选择排序*2.冒泡排序*3.插入排序*4.希尔排序5.快速排序*查找算法1.二分查找*前提条件序列必须有序时间复杂度Ologn2.插入排序思想将待排的数据插入到一个已有序的序列中确保每次插入之后该序列仍然有序。时间复杂度O(n^2)空间复杂度O(1)稳定性稳定的3.希尔排序思想将待排序列根据增量划分成若干个子序列分别对这些子序列进行插入排序。时间复杂度O(nlongn)~O(n^2)空间复杂度O1稳定性不稳定4.快速排序思想选取基准值从两端向中间比较比基准值大的放在序列的右边比基准小的放在序列的左边 经过一趟排序优先排好基准值。时间复杂度Onlogn空间复杂度Ologn稳定性不稳定调用以上 结果