C++ 中的动态数组选择排序

介绍

在本实验中，你将学习如何使用选择排序算法对 C++ 中的未排序动态数组进行排序。

Skills Graph

创建一个新的 C++ 文件

首先，在 ~/project 目录下创建一个名为 main.cpp 的 C++ 文件。

touch ~/project/main.cpp

实现选择排序算法

选择排序算法的工作原理是：首先选择数组中的最小元素并将其放置在数组的开头，然后从剩余数组中选择下一个最小元素并将其放置在索引 1 的位置，依此类推，直到数组完全排序。以下是如何在 C++ 中实现选择排序算法：

#include <iostream>
using namespace std;

// 交换两个元素位置的函数
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// 执行选择排序算法的函数
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {

      // 若要按降序排序，将此行中的 > 改为 <。
      // 在每次循环中选择最小元素。
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // 将最小值放置在正确的位置
    swap(&array[min_idx], &array[step]);
  }
}

在这段代码中，我们定义了一个 swap() 函数来交换数组中两个元素的位置，以及一个 selectionSort() 函数来对数组执行选择排序算法。

输入数组

在这一步中，你将输入需要排序的动态数组。你可以通过提示用户逐个输入数组元素来实现：

// 驱动代码
int main() {
  int size;
  cout<<"输入数组的大小：";
  cin>>size; // 输入数组的大小
  int* data = new int[size]; // 动态声明数组

  // 逐个输入数组元素
  for(int i = 0; i < size; i++) {
    cout<<"输入元素 "<<i+1<<" : ";
    cin>>data[i];
  }

执行选择排序

现在我们已经有了未排序的数组，可以使用之前定义的 selectionSort() 函数对其执行选择排序算法。以下是具体实现：

  // 执行选择排序
  selectionSort(data, size);

输出排序后的数组

最后，我们将使用一个名为 printArray() 的函数中的循环将排序后的数组输出到控制台。以下是具体实现：

  // 输出排序后的数组
  cout << "\n排序后的数组：";
  for (int i = 0; i < size; i++)
    cout << data[i] << " ";

  // 释放动态数组使用的内存
  delete[] data;
  return 0;
}

编译并运行代码

要编译并运行代码，请打开终端并导航到存储 main.cpp 文件的文件夹。然后执行以下命令：

g++ main.cpp -o main
./main

排序后的数组将会显示在控制台中。

总结

在本实验中，你学习了如何使用选择排序算法对 C++ 中的未排序动态数组进行排序。为此，你需要输入数组、实现选择排序算法、执行排序、输出排序后的数组，然后在终端中编译并运行代码。通过这些技能，你将能够使用选择排序对任意大小的数组进行排序。