写在开头

一维数组

本讲主要内容:

  • 概念引入
  • 数组的定义
  • 数组的初始化
  • 数组的访问
  • 循环访问数组
  • 数组排序
    • 冒泡排序
    • 选择排序
    • 直接插入排序

概念引入

我们来看一下这个例子:

存储全班同学的成绩,并算出总成绩与平均分。(全班50人)

如果没有数组,那么需要初始化50个变量:

int score1 = 0;
int score2 = 0;
int score3 = 0;
...
...
...

int sum = score1 + score2 + ... + score50;
int avg = sum / 50;

不难看出,我们不可能去初始化50个变量,那么有没有更好的解决办法呢?

当然有,数组!

数组的定义

基本概念:

  • 在定义数组时,计算机会分配一块连续的空间
  • 定义方式为:类型 数组名[数组长度];
  • 命名规则与变量命名规则相同(首字母小写、驼峰法)
  • 数组长度定义后,就不能改变
  • Clang编译环境下,长度可以是变量。但是数组取的值,是定义数组时,变量的值。

具体写法为:

int scores[50]; // 含义:定义一个长度为50的数组scores

数组的初始化

在变量定义时给值,叫做初始化。

将全部值都初始化为0

int scores[50] = {};

// 或

int scores[50] = {0};

初始化部分或全部的值

初始化全部的数据。需要注意的是:

  • 现在的数组长度为3,所以最多只能给3个值
  • 数组类型为int,所以数组中只能放int类型的值
int scores[3] = {94, 91, 80};

下面的例子中,数组长度为50。如果只初始化2个值,那么剩下的48个值,均为0。

int scores[50] = {94, 90};

已确定个数的初始化方式

当数组长度已经确定时,可以省略数组长度,直接初始化。

int score[] = {34, 78, 64};

数组的读写

访问某个值

访问时需要注意以下几点:

  • 数组通过下标访问
  • 下标从0开始(意味着长度为40的数组,下标范围是0~39)
  • 注意不要越界(超出访问范围)
int scores[50] = {30, 58, 93, 80, 32, 45};

int firstScore = scores[0]; // 访问第0个数
int thirdScore = scores[2]; // 访问第3个数

赋值

int scores[50] = {0}; // 定义并初始化数组

scores[0] = 10; // 第0个值为10
scores[3] = 90; // 第3个值为90

循环访问数组

有了数组,不仅方便了同类变量的定义,最重要的是,数组的下标是连续的,我们可以通过循环的方式,来访问数组。

来看下面这个例子:

定义一个长度为6的成绩数组,并初始化。求出总分与平均分。

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int scores[6] = {1, 3, 4, 6, 2, 4};
    int sum = 0;

    for (int i = 0; i < 6; i ++) {

        sum += scores[i];
    }

    printf("总分 = %d, 平均分 = %lf", sum, sum / 6.0);

    return 0;
}

练习:

录入6个成绩,求出总分与平均分。

数组的排序

排序一直是数组操作中,最经典的话题。各种算法,各种实现方式,最后还有各种面试,防不胜防的会问到。这一讲介绍到的数组排序方式都比较基础:

  • 冒泡排序
  • 选择排序
  • 直接插入排序

冒泡排序

步骤:每次将最大的数冒出来。(每一轮都会将最大值排到最前或最后)

思路:比较两个相邻两个数,如果i > i + 1,则交换位置。每轮排序完成后,减少起点(或重点),避免重复比较有序部分。

// 冒泡排序
void bubbleSort() {

    int array[5] = {1, 2, 3, 5, 4};
    int sum = 0; // 记录执行次数

    for (int i = 0; i < 5; i ++) {

        int flag = 0; // 标记是否提前完成排序

        for (int j = 0; j < 5 - i - 1; j ++) {

            if (array[j] > array[j + 1]) {

                flag = 1; // 如果该轮排序进行了值的交换,说明排序还未完成

                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
            sum ++; // 排序字数++
        }
        if (flag == 0) {

            break;
        }
    }

    printf("排序共执行%d次\n", sum);

    // 遍历输出
    for (int i = 0; i < 5; i ++) {

        printf("%d ", array[i]);
    }
}

选择排序

步骤:遍历数组,每一轮找到最大的值,与最前(最后)交换。

实现:

void selectionSort() {

    int array[7] = {4, 6, 3, 1, 7, 5, 2};

    // 每一轮循环,找出第i大的数,放到第i位
    for (int i = 0; i < 7; i ++) {

        // 默认最小值的下标为i
        int minIndex = i;

        // 循环找最小值,j从i开始,避免重复查找
        for (int j = i + 1; j < 7; j ++) {

            if (array[j] < array[minIndex]) {

                minIndex = j;
            }
        }
        // 将找到的最小值,与第i位互换
        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
    // 遍历输出
    for (int i = 0; i < 7; i ++) {

        printf("%d ", array[i]);
    }
}

插入排序

步骤:找到一个数的正确位置,插入数组。

思路:

void insertionSort() {

    int array[8] = {6, 5, 3, 1, 8, 7, 2, 4};

    // 每一轮循环,可保证第i个数之前是有序的
    for (int i = 1; i < 8; i ++) {

        int j = i;
        int temp = array[i];

        // 第二层循环:移位操作
        for (; j > 0 && temp < array[j - 1]; j --) {

            array[j] = array[j - 1];
        }
        array[j] = temp;
    }
    // 遍历输出
    for (int i = 0; i < 8; i ++) {

        printf("%d ", array[i]);
    }
}