数组

一、一维数组的定义和引用

1、一位数组的定义

        定义：类型说明符   数组名[整型常量表达式]；

                eg：

int s[10000];

        c99中允许用变量来定义常量表达式；

int n = 100;
int s[n];

 2、一维数组元素的引用

        数组元素表示形式：

                                        数组名[下标]

        定义数组时的“[   ]”是一个类型说明符，说明是一个数组；

        a[i]中的“[    ]”是一个下标运算符；

数组在内存中存储元素时，具有连续性、有序性（下标小，则地址在前）、单一性（每个元素占有的字节数相同）；

       越界访问：在定义之外的下标数，则称之为越界访问；

         eg：【int a[10];    a[10] = 100;   a[-1] = 100；】；

        a[10] = 100;   a[-1] = 100就为越界访问；

注意事项：

        ①数组不能被整体访问；eg：【int a[10];a = 100;】;

        ②数组的数组名为数组的首元素地址；

        ③不能越界访问；

数组初始化：

        【int a[10] = {1,2,3,4,5,6,7,8}】

        其中 【{1,2,3,4,5,6,7,8}】称之为初始化列表；

注意事项：

        ①初始化的值大于定义的个数，会越界访问；

        ②初始化的值小于被定义的个数，则后面的值都是0；

 

五种重要的应用：

1、倒序输出

eg：将下面的数组倒序输出；

程序：

运行结果：

 

 二、选择排序

1、必须存在比较功能的前提下，在进行排序；

其中比较次数为（n-1）+(n-2) + （n-3）+……+2+1 = （n*（n-1））/2

则算数复杂度为：O（n^2）;

时间复杂度：

空间复杂度：

eg：将下面的数组排序（从小到大）默认是从小到大

三、冒泡排序法

定义：相邻的两个元素两两比较，小的放前面，大的放后面；

eg：将下面的数组排序（从小到大）

 四、插入法排序

eg:将下面的数组排序（从小到大）

程序：

五、二分查找法（折半查找法）

eg：将下面的数组排序（从小到大），并输入一个数，查找该数在不在此数组中；

二分查找发的前提是提前排序完成

练习：从终端输入一个n将数组int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9} 完成如下变化,并打印,操作方式如下:

         n:2 8 9 1 2 3 4 5 6 7

        n:3 7 8 9 1 2 3 4 5 6

程序：

 

运行结果：