C++数组排序技巧分享 |21xrx.com

C++数组排序技巧分享

2023-07-10 02:27:22 深夜i 12 0

C++ 数组排序技巧分享

在C++编程中，数组是必不可少的数据结构之一。当涉及到排序这样的操作时，了解排序技巧可以让您编写更高效的代码和更好的算法。本文将分享C++数组排序的一些技巧。

1. 冒泡排序

冒泡排序是最基本的排序算法之一。它通过对相邻元素的交换来排序数组中的元素。冒泡排序的时间复杂度为O(n^2)。

示例：

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

2. 快速排序

快速排序是一种常用的排序算法。它通过划分输入数组为较小和较大的元素来排序。快速排序的时间复杂度为O(nlogn)。

示例：

void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int pivot = arr[(left + right) / 2];
  while (i <= j) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i <= j) {
      swap(arr[i], arr[j]);
      i++;
      j--;
    }
  }
  if (left < j) quickSort(arr, left, j);
  if (i < right) quickSort(arr, i, right);
}

3. 插入排序

插入排序是一种简单的排序算法。它通过遍历输入数组，将每个元素插入到已排序的子数组中来排序。插入排序的时间复杂度为O(n^2)。

示例：

void insertionSort(int arr[], int n) {
  int j, temp;
  for (int i = 1; i < n; i++) {
    j = i - 1;
    temp = arr[i];
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
}

4. 归并排序

归并排序是一种分治算法，它将输入数组分成两个子数组，对每个子数组进行递归排序，最后将两个子数组合并到一起。归并排序的时间复杂度为O(nlogn)。

示例：

void merge(int arr[], int l, int m, int r) {
  int i, j, k;
  int n1 = m - l + 1;
  int n2 = r - m;
  int L[n1], R[n2];
  for (i = 0; i < n1; i++) L[i] = arr[l + i];
  for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
  i = 0;
  j = 0;
  k = l;
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    }
    else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}
void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }
}

总结

C++数组排序是编程中很重要的一部分，不同的算法适用于不同的场景。在实际开发中，您可以调整和改进这些算法，以满足特定的需求和问题。我们希望这篇文章可以帮助您更好地理解C++数组排序的技巧和应用。

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

下一篇: 《C++程序设计第三版答案谭浩强第一章》

评论区

相似文章