本文作者：程序员飞云

本站地址：https://www.flycode.icu

数组练习

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[i] > 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) / 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. 找出整型数组中第二大的元素的值

// 不可排序，最大元素可能出现多次

int secondMax(const int* arr,int len) {
  if (len < 2) {
    cout << "长度小于2" << endl;
    return -1;
  }
  int res[2] ;
  // 第一个存最大值，第二个存第二个最大值
  res[0] = arr[0] > arr[1] ? arr[0] : arr[1];
  res[1] = arr[0] > arr[1] ? arr[1] : arr[0];

  for (int i = 0; i < len; i++) {
    // 新的最大值出现了
    if (res[0] < arr[i]) {
      // 第二个元素存入第一个元素的值
      res[1] = res[0];
      // 第一个元素存入当前的值
      res[0] = arr[i];
    }
    else if (res[0] > arr[i] && res[1] < arr[i]) {
      // 当前的这个值小于最大值，大于倒数第二个大的值
      res[1] = arr[i];
    }
  }
  return res[1];
}

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. 数组元素拷贝到另一个数组

int* copyArr(int* arr,  int len,int* newArr,int nLen) {
  nLen = len;
  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;

数组专区