C++交换排序的实现 |21xrx.com

C++交换排序的实现

2023-06-23 22:48:10 深夜i 12 0

C++ 交换排序实现

C++语言中，交换排序是一种常见的排序算法，可以对一个数组或者一个容器的元素进行排序。交换排序通常有两种实现方法，即冒泡排序和快速排序。

一、冒泡排序

冒泡排序是最简单的交换排序算法之一，它的思想是将相邻的元素进行比较，然后根据比较结果交换它们的位置，从而达到排序的目的。这个过程像冒泡一样，较大的元素会慢慢"浮"到最后。

在C++中，实现冒泡排序可以使用两层循环。外层循环遍历所有元素，内层循环则进行相邻元素比较和交换操作。代码如下：

void bubble_sort(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]);
      }
    }
  }
}

二、快速排序

快速排序是一种高效的交换排序算法，它的基本思想是选定一个"基准"元素，将数组分成两个部分，一部分都比基准元素小，另一部分都比基准元素大，然后对这两部分递归进行排序。具体实现可以使用"分治法"。

在C++中，实现快速排序通常可以使用递归函数来实现。代码如下：

int partition(int arr[], int left, int right)
{
  int pivot = arr[left]; //选取左边第一个元素作为基准元素
  int i = left + 1;
  int j = right;
  while (true)
  {
    while (i <= j && arr[i] <= pivot) i++;
    while (i <= j && arr[j] >= pivot) j--;
    if (i > j) break;
    swap(arr[i], arr[j]);
  }
  swap(arr[left], arr[j]);
  return j;
}
void quick_sort(int arr[], int left, int right)
{
  if (left >= right) return;
  int pivot_index = partition(arr, left, right);
  quick_sort(arr, left, pivot_index - 1);
  quick_sort(arr, pivot_index + 1, right);
}

以上是C++中交换排序的实现方式，程序员可以根据自己的需求选择适合的算法实现方式。

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

下一篇: C++ 可变参数函数

评论区

相似文章