使用C++编写排序算法 |21xrx.com

使用C++编写排序算法

2023-07-08 12:51:19 深夜i -- --

C++ 排序算法数组数据结构

C++是一门被广泛应用于计算机科学和软件工程领域的编程语言。在许多实际场景中，需要对数据进行排序处理，而C++提供了多种排序算法来满足这种需求。下面介绍一些常用的排序算法，以及它们在C++中的实现。

1. 插入排序

插入排序是最简单的排序算法之一。它的基本思想是将一个元素插入到已经排好序的数组中，使得插入后的数组仍然有序。这个过程可以反复进行，直到整个数组都有序为止。

C++中实现插入排序的代码如下：

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

2. 选择排序

选择排序也比较简单。它的基本思想是在未排序的部分中选择最小的元素，将其放到已排序部分的末尾。这个过程也可反复进行，直到整个数组都有序为止。

C++中实现选择排序的代码如下：

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

3. 快速排序

快速排序是一种高效的排序算法。它的基本思想是通过一次划分将待排序数组分成两个子数组，其中一个子数组的所有元素均小于另一个子数组的所有元素。然后再对这两个子数组分别进行递归排序。

C++中实现快速排序的代码如下：

 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++中的实现。在实际应用中，不同的排序算法可能会根据实际需求进行组合使用，以充分利用它们的优势和避免它们的缺点。

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

下一篇: C++中如何输入回车键？

评论区

()

相似文章