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

C++C++Beginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

介绍

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


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("`C++`")) -.-> cpp/BasicsGroup(["`Basics`"]) cpp(("`C++`")) -.-> cpp/ControlFlowGroup(["`Control Flow`"]) cpp(("`C++`")) -.-> cpp/AdvancedConceptsGroup(["`Advanced Concepts`"]) cpp(("`C++`")) -.-> cpp/IOandFileHandlingGroup(["`I/O and File Handling`"]) cpp(("`C++`")) -.-> cpp/SyntaxandStyleGroup(["`Syntax and Style`"]) cpp/BasicsGroup -.-> cpp/operators("`Operators`") cpp/BasicsGroup -.-> cpp/arrays("`Arrays`") cpp/ControlFlowGroup -.-> cpp/for_loop("`For Loop`") cpp/AdvancedConceptsGroup -.-> cpp/pointers("`Pointers`") cpp/IOandFileHandlingGroup -.-> cpp/output("`Output`") cpp/IOandFileHandlingGroup -.-> cpp/user_input("`User Input`") cpp/IOandFileHandlingGroup -.-> cpp/files("`Files`") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("`Code Formatting`") subgraph Lab Skills cpp/operators -.-> lab-96170{{"`C++ 中的动态数组选择排序`"}} cpp/arrays -.-> lab-96170{{"`C++ 中的动态数组选择排序`"}} cpp/for_loop -.-> lab-96170{{"`C++ 中的动态数组选择排序`"}} cpp/pointers -.-> lab-96170{{"`C++ 中的动态数组选择排序`"}} cpp/output -.-> lab-96170{{"`C++ 中的动态数组选择排序`"}} cpp/user_input -.-> lab-96170{{"`C++ 中的动态数组选择排序`"}} cpp/files -.-> lab-96170{{"`C++ 中的动态数组选择排序`"}} cpp/code_formatting -.-> lab-96170{{"`C++ 中的动态数组选择排序`"}} end

创建一个新的 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++ 中的未排序动态数组进行排序。为此,你需要输入数组、实现选择排序算法、执行排序、输出排序后的数组,然后在终端中编译并运行代码。通过这些技能,你将能够使用选择排序对任意大小的数组进行排序。

您可能感兴趣的其他 C++ 教程