数组专区

数组练习

变量与循环片段放在 main 中，函数定义放在 main 外；函数参数中的长度必须非负且不超过实际容量。含 cout 的例子需包含 <iostream> 并使用 std::cout/std::endl。C++17 示例可用 cl /std:c++17 /utf-8 /EHsc main.cpp 编译。

1.选择排序（不稳定）

当前的元素和后续的元素比较，如果后续的元素小，就交换，然后继续寻找最小的值，第一个元素遍历完成后，继续第二个元素开始遍历，找最小元素

  int arr[] = { 3,2,5,3,1,0 };
  int size = sizeof(arr) / sizeof(arr[0]);

  for (int i = 0; i < size; i++) {
    for (int j = i + 1; j < size; j++) {
      if (arr[i] > arr[j]) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }

第一段属于直接交换排序。下面是每轮选出最小下标、最后只交换一次的选择排序：

  int arr[] = { 3,2,5,3,1,0 };
  int size = sizeof(arr) / sizeof(arr[0]);

  for (int i = 0; i < size; i++) {
    int minIndex = i;
    for (int j = i + 1; j < size; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    if (minIndex != i) {
      int temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
    }
  }

2. 冒泡排序

相邻的两个元素比较，如果当前元素小，就不交换，如果当前元素大，就两两交换

int arr[] = { 3,2,5,3,1,0 };
int size = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < size; i++) {
  for (int j = 0; j < size - i - 1; j++) {
    if (arr[j] > arr[j + 1]) {
      int temp = arr[j];
      arr[j] = arr[j + 1];
      arr[j + 1] = temp;
    }
  }
}

3. 顺序查找元素

从前往后寻找是否存在对应的目标元素，存在就返回下标

int indexof(const int* arr, int len,int target) {
  for (int i = 0; i < len; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

4. 二分查找元素

一般依赖于数组有序

int binarySearch(const int* arr, int len, int target) {
  int left = 0;
  int right = len - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] > target) {
      right = mid-1;
    }
    else if (arr[mid] < target) {
      left = mid + 1;
    }
    else {
      return mid;
    }
  }
  return -1;
}

5. 找数组中最大的数字，返回下标

int maxNum(const int* arr, int len) {
  if (len <= 0) {
    cout << "数组为空" << endl;
    return -1;
  }
  int maxIndex = 0;
  for (int i = 1; i < len; i++) {
    if (arr[maxIndex] < arr[i]) {
      maxIndex = i;
    }
  }
  return maxIndex;
}

6. 判断数组是否是升序数组

bool isSorted(const int* arr, int len) {
  bool flag = true;
  for (int i = 0; i < len-1; i++) {
    if (arr[i] > arr[i + 1]) {
      flag = false;
      break;
    }
  }
  return flag;
}

递归判断，从最后一个元素和倒数第二个元素比较，判断是否升序

bool isSorted2(const int* arr, int len) {
  if (len <= 1) {
    return true;
  }
  return isSorted2(arr, len - 1) && arr[len - 2] <= arr[len - 1];
}

7. 找出整型数组中第二大的元素的值

找第二个不同的最大值，例如 [5,5,3] 返回 3，[5,5] 没有结果。下面需要 C++17；std::nullopt 明确表示不存在，不用 -1 与合法负数混淆。传入长度必须非负，且不能超过实际数组长度。

#include <optional>
std::optional<int> secondMax(const int* arr, int len) {
    if (!arr || len < 2) return std::nullopt;
    int largest = arr[0];
    std::optional<int> second;
    for (int i = 1; i < len; ++i) {
        if (arr[i] > largest) {
            second = largest;
            largest = arr[i];
        } else if (arr[i] < largest && (!second || arr[i] > *second)) {
            second = arr[i];
        }
    }
    return second;
}

8. 数组元素倒序排列

void reverseArr( int *arr, int len) {
  int left = 0;
  int right = len - 1;
  while (left < right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++;
    right--;
  }
}

9. 数组元素拷贝到另一个数组

目标容量不能小于源长度，nLen 是传入的容量，不是通过赋值就能扩容。下面需包含 <stdexcept>。

int* copyArr(const int* arr, int len, int* newArr, int nLen) {
    if (len < 0 || nLen < len || (len > 0 && (!arr || !newArr))) {
        throw std::invalid_argument("目标容量不足或参数无效");
    }
  for (int i = 0; i < len; i++) {
    newArr[i] = arr[i];
  }
  return newArr;
}

10. 比较两个数组中的元素是否相同

bool arrayEquals(int* arr, int len, int* newArr, int nLen) {
  if (len != nLen) {
    return false;
  }

  for (int i = 0; i < len; i++) {
    if (newArr[i] != arr[i]) {
      return false;
    }
  }
  return true;
}

浅拷贝和深拷贝

浅拷贝：地址拷贝，拷贝的是数组的首元素地址

深拷贝：定义一个新的数组，长度和原来的相同，然后将元素全部拷贝到新的数组里面去。

int arr[] = { 1,2,3 };
cout << "原地址" << &arr << endl;
// 浅拷贝
int* arr_copy_1  = arr;
cout << "浅拷贝地址：" << arr_copy_1 << endl;


// 深拷贝
const int size = sizeof(arr) / sizeof(arr[0]);
int  arr_copy_2[size];
for (int i = 0; i < size; i++) {
  arr_copy_2[i] = arr[i];
}
cout << "深拷贝地址：" << &arr_copy_2 << endl;