一、数组

（一）一维数组

1、定义方式：类型说明符 数组名【常量表达式】；

2、一维数组元素的引用表现形式：数组名【下标】，a[i]指数组里具体的值，i为数组下标；数组最前面的为a[0]；

3、注意事项：

（1）类型说明符唯独不能是空类型（void）；

（2）数组名应遵循标识符命名规则；

（3）常量表达式为整型常量表达式；

（4）“【】”被理解为类型说明符，仅是说明其为数组；

（二）数组三大特性

连续性——数组空间是一片连续的内存空间

有序性——数组的元素挨个依次存放

单一性——数组的元素是同一类型

注意事项：（1）数组中所有元素下标一定从0开始，最后一个数组下标为数组元素个数-1，超过会引发数组越界访问；

（2）数组不可被整体访问，引用，赋值；

（3）数组的数组名是数组的首元素地址。

扩：初始化一个数组：int a[10]={};  其中“{}”为初始化列表器，有初始化列表器[]里的个数可省略；部分初始化后面自动清零。

（三）例题

1、遍历输出数组a[]。

2、求数组里的最大值与次大值。

二、排序算法

（一）逆序排序

数组逆序输出

（二）选择排序

选择排序：在合适的位置上放上合适的数；

算法复杂度：O（n^2），空间复杂度：O（1）（注：算法复杂度又称时间复杂度是检测算法优劣，空间复杂度是代码实现过程中需提供的额外空间）

理解：a[0]与先与a[1]进行比较，如果a[0]比a[1]的大，则a[0]与a[1]里面的数值交换，如果不大，则不变，然后a[0]再与a[2]进行比较，重复与a[1]的比较操作，一直到与a[7]做完比较，此时a[0]内的数是这组数的最小值，放最前面，之后再用a[1]与a[2]进行比较，重复之前的比较过程，又可以找出这组数的第二个最小值放到a[1]中，然后a[3]再与之后位置的数进行比较，重复之前操作，一直到a[6]这个数与a[7]比较重复之前的比较操作，得到升序的数组并输出。

（三）冒泡排序

冒泡排序：相邻两个元素两两比较，小的放前，大的放后（默认升序排序）（两数比较交换把最大值推到末尾处）

算法复杂度：O（n^2）

理解：第一次比较，a[0]与a[1]比，当a[0]大于a[1]时，a[0]与a[1]里的数值交换，反之不变，接着a[1]与a[2]比，如果a[1]大于a[2]，a[1]与a[2]里的数值交换，反之不变，接着a[2]与a[3]比，如果a[2]大于a[3]时，a[2]与a[3]里的数值交换，反之不变，接着a[3]与a[4]比，如果a[3]大于a[4]时，a[3]与a[4]里的数值交换，反之不变，一直这样到a[7]与a[8]比，如果a[7]大于a[8]时，a[7]与a[8]里的数值交换，此时a[8]里的数值是这个数组中最大的数值；

第二次比较，a[0]与a[1]比，如果a[0]大于a[1]时，a[0]与a[1]里的数值交换，反之不变，接着a[1]与a[2]比，如果a[1]大于a[2]，a[1]与a[2]里的数值交换，反之不变，一直比较到a[6]与a[7]相比，如果a[6]大于a[7]，a[6]与a[7]里的数值交换，反之不变，此时a[7]中是这组数组中第二大的数；

接着第三，第四一直到第len（长度）-1次比较此时a[1]与a[0]作比较，然后得出全部数的排序并输出。

（四）插入排序

插入排序：在有序序列中，找到合适的位置插入；

算法复杂度：O（n^2），原地插入排序降低空间复杂度，空间复杂度为O（1）

非原地插入法理解：

先将一个a数组的一个值拿出来，比如a[0]，放入到b数组中，此时b数组是空的空间，a[0]可以直接放到b[0]中，再将a[1]的值拿出来，此时要放入b数组中，先与b[0]中的值进行比较，如果a[1]的值小于b[0]的值，则b[0]中的值要给a[1]中的值挪位置，此时b[0]中是a[1]中的值，原先b[0]中的值被挪到了b[1]中，如果不小于，就直接将a[1]的值直接放入到b[1]中；

此时再将a[2]中的值拿出来先与b[1]中的值作比较，如果此时a[2]的值小于b[1]的值，则b[1]中的值要给a[2]中的值挪位置，原先b[1]中的a[0]的值被挪到了b[2]中，然后将现在b[1]的值再与b[0]中的值作比较，如果小于，则像之前那样挪位置，如果不小于，直接放入到b[2]；

之后再将a[3]中的值拿出重复之前的比较，挪位置，一直这样到a[9]，然后打印出新的数组b将得到升序排列的数组，拷贝到a数组后输出。

原地插入排序，降低空间复杂度（不需要数组b）

三、查找算法（二分查找）

1、二分查找（折半查找）：大前提是数据得是有序的；

2、思想：找到中间位置的数（下标），拿这个数和要找的数比较；

理解：定义一个数组int a[] = {1,2,3,4,5,6,7,8,0},输入一个数n，查找这个数是否在数组中

首先应该求出数组的长度，这个数组最开始的初始位置下标begin就是0，最后的位置end是len-1，找出它中间位置的数mid就是（len-1）/2，接着判断中间位置数的值是否比n大，

如果比n大，则n应该在中间位置数的左边，此时缩小范围，最后的位置mid应该变为中间数的左边的第一个数，此时end变为mid-1；

如果比n小，则m应该在中间位置数的右边，此时缩小范围，最开始的位置begin应该变为中间数的右边的第一个数，此时begin变为mid+1；

然后再在判定后这个范围内再取中间值，重复上面的过程，直到找到等于n的值。