21xrx.com
2025-04-10 14:06:03 Thursday
文章检索 我的文章 写文章
C++数组排序方法详解
2023-07-10 19:25:55 深夜i     9     0
C++ 数组 排序 方法 详解

C++是一门流行的编程语言，尤其在开发各种应用程序时非常常用。在C++编程中，数组排序是一个基本的编程问题。因此，在本文中，我们将详细介绍C++的数组排序方法。

C++提供了多种数组排序算法，其中最常用的是冒泡排序、选择排序、插入排序、归并排序和快速排序。

1. 冒泡排序

冒泡排序通过比较相邻的元素，如果前一个元素比后一个元素大，则交换这两个元素。通过不断地交换相邻元素的位置，将最大的元素移动到数组的末尾。这个过程需要重复 n-1 次，直到排序完成。

以下是使用C++实现的冒泡排序算法：

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. 选择排序

选择排序从数组中选择最小的元素，然后与数组的第一个元素交换位置。接着，从剩余元素中选出最小的元素，与第二个元素交换位置。重复这个过程，直到排序完成。

以下是使用C++实现的选择排序算法：

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

3. 插入排序

插入排序将未排序的元素插入已排序的序列中，对于每个未排序的元素，从已排序的序列的末尾向前比较，直到找到插入位置。

以下是使用C++实现的插入排序算法：

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

4. 归并排序

归并排序将数组分成两个部分，对每个部分进行排序，然后将它们合并起来。该算法使用分治思想，通过将问题分成小问题来解决较大的问题。因此，归并排序的时间复杂度为 O(n log n)。

以下是使用C++实现的归并排序算法：

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);
  }
}

5. 快速排序

快速排序通过将数组分成较小的部分来排序，然后对它们进行快速排序。快速排序是一种分治算法，通过选取一个基准元素来划分数组，将比基准元素小的元素放在左边，比基准元素大的元素放在右边，然后递归地对左右两部分进行排序。

以下是使用C++实现的快速排序算法：

int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low - 1;
  for (int j = low; j <= high - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1], arr[high]);
  return i + 1;
}
void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

总结

以上是使用C++实现的基本排序算法，包括冒泡排序、选择排序、插入排序、归并排序和快速排序。每种算法的时间复杂度和空间复杂度都有所不同。在选择算法时，需要考虑到数据量的大小以及需要排序数据的类型。

  
  

评论区

请求出错了