C++ 数组排序方法总结 |21xrx.com

C++ 数组排序方法总结

2023-07-04 17:55:09 深夜i -- --

- C++ - 数组 - 排序方法 - 总结

C++ 数组是指一块连续的内存空间，存储相同类型的数据。数组中的元素可以是基本数据类型，也可以是自定义数据类型。在实际开发中，经常需要对数组进行排序。下面我们总结几种常见的排序方法。

1. 冒泡排序

冒泡排序是一种简单的排序算法，它通过不断交换相邻的元素，将较大的元素向数组的一端移动。该算法的时间复杂度为 O(n^2)。

示例代码：


void bubbleSort(int arr[], int len) {
  for (int i = 0; i < len - 1; i++) {
    for (int j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}

2. 快速排序

快速排序是一种常用的排序算法，它通过分治的思想，将数组分成两部分，一部分比另一部分小，然后再对每部分进行排序。该算法的时间复杂度为 O(nlogn)。

示例代码：


int partition(int arr[], int left, int right) { // 分区函数
  int pivot = arr[right];
  int i = left - 1;
  for (int j = left; j < right; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1], arr[right]);
  return i + 1;
}
void quickSort(int arr[], int left, int right) { // 排序函数
  if (left < right) {
    int p = partition(arr, left, right);
    quickSort(arr, left, p - 1);
    quickSort(arr, p + 1, right);
  }
}

3. 归并排序

归并排序是一种非常稳定的排序算法，它将数组分成两个部分，对每个部分进行排序，然后将两个排序好的子数组合并成一个有序数组。该算法的时间复杂度为 O(nlogn)。

示例代码：


void merge(int arr[], int left, int mid, int right) { // 归并函数
  int i = left; // 左子数组的起始位置
  int j = mid + 1; // 右子数组的起始位置
  int k = 0; // 新数组的起始位置
  int temp[right - left + 1];
  while (i <= mid && j <= right) { // 比较并合并
    if (arr[i] < arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }
  while (i <= mid) {
    temp[k++] = arr[i++];
  }
  while (j <= right) {
    temp[k++] = arr[j++];
  }
  for (int t = 0; t < k; t++) { // 将新数组复制回原数组
    arr[left + t] = temp[t];
  }
}
void mergeSort(int arr[], int left, int right) { // 排序函数
  if (left < right) {
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}

以上就是三种常见的数组排序方法。需要注意的是，不同的算法适用于不同的场景，根据具体的需求选择合适的排序算法可以提高程序的效率。

上一篇: idea打包java可执行jar包

下一篇: Node.js代码调试指南

评论区

()

相似文章