C++排序技巧 |21xrx.com

C++排序技巧

2023-07-07 02:26:46 深夜i 11 0

排序算法 STL库快排归并排序堆排序

C++是一门非常强大的编程语言，它可以用来解决各种问题，其中排序算法是其中一个重要的应用。排序是算法中一个最基本的问题，因为它是解决许多其他问题的基础。在这里，我们将讨论一些C++排序技巧。

1. 使用STL库中的sort函数

STL库是C++标准库的一个重要组成部分，其中有一个sort函数可以帮助我们排序。sort函数的使用非常简单，只需要使用一个函数即可完成排序。例如，如果我们希望将一个数组进行升序排列，可以使用以下代码：

int arr[5] = 1;
sort(arr, arr + 5);

这段代码中，sort函数会将arr数组中的元素按升序排列，因为我们没有给sort函数传递参数，所以它默认将元素按从小到大的顺序排列。

2. 使用快速排序算法

快速排序是一种常用的排序算法，它的时间复杂度为O(nlogn)，非常高效。快速排序的基本思路是选择一个基准元素，将数组分为两个部分，小于基准元素的放到左边，大于基准元素的放到右边，然后分别对左、右两个部分进行快速排序，最终将排好序的两个部分合并起来即可。

下面是一个C++实现快速排序的示例代码：

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

这个函数接受三个参数：要排序的数组、数组的左边界、数组的右边界。在函数中，我们首先判断左右边界是否相等，如果相等，就直接返回。然后，我们选择数组的第一个元素作为基准元素，并将数组分为两部分。接着，使用两个指针i和j分别从左往右和从右往左扫描数组，并将小于基准元素的置于左边，大于基准元素的置于右边。最后，递归地对左、右两部分分别进行快速排序。

3. 使用归并排序算法

归并排序也是一种常用的排序算法，它的时间复杂度为O(nlogn)。归并排序的基本思路是将待排序数组分成两个子序列，分别对每个子序列进行排序，然后将排好序的两个子序列合并成一个排序好的序列。

下面是一个C++实现归并排序的示例代码：

void merge(int arr[], int left, int mid, int right, int tmp[]) {
  int i = left, j = mid + 1, k = left;
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
      tmp[k++] = arr[i++];
    } else {
      tmp[k++] = arr[j++];
    }
  }
  while (i <= mid) {
    tmp[k++] = arr[i++];
  }
  while (j <= right) {
    tmp[k++] = arr[j++];
  }
  for (int i = left; i <= right; i++) {
    arr[i] = tmp[i];
  }
}
void mergeSort(int arr[], int left, int right, int tmp[]) {
  if (left >= right)
    return;
  
  int mid = (left + right) / 2;
  mergeSort(arr, left, mid, tmp);
  mergeSort(arr, mid + 1, right, tmp);
  merge(arr, left, mid, right, tmp);
}
void mergeSort(int arr[], int len) {
  int tmp[len];
  mergeSort(arr, 0, len - 1, tmp);
}

这段代码中，我们定义了一个merge函数和一个mergeSort函数，它们分别用来进行归并排序的合并和递归。在merge函数中，我们首先定义三个指针i、j和k，分别指向左、右两个子序列和临时数组的当前位置。然后，比较左右子序列的元素大小，并将较小的元素放入临时数组中。最后，将临时数组中的元素复制回原数组中。

在mergeSort函数中，我们首先判断左右边界是否相等，如果相等，就直接返回。然后，我们计算出当前数组的中间位置mid，并递归地对左、右两个子序列分别进行归并排序。最后，使用merge函数将排序好的两个子序列合并成一个序列。

总结

本文介绍了三种C++排序技巧：使用STL库中的sort函数、使用快速排序算法和使用归并排序算法。由于算法的运行效率和时间复杂度不同，我们需要根据具体应用场景来选择不同的排序技巧。同时，我们也需要注意排序算法的实现细节，例如边界条件的处理和临时数组的分配等。希望本文对你学习C++排序算法有所帮助。

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

下一篇: C++实现分形盒

评论区

相似文章