使用动态数组实现插入排序

C++C++Beginner
立即练习

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

简介

在本实验中,我们将学习如何使用 C++ 中的动态数组实现插入排序(Insertion Sort)算法。该算法是一种简单的排序算法,通过将列表分为已排序和未排序两部分,然后将未排序列表中的每个元素插入到已排序列表的正确位置来完成排序。


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/BasicsGroup -.-> cpp/operators("`Operators`") cpp/BasicsGroup -.-> cpp/arrays("`Arrays`") cpp/ControlFlowGroup -.-> cpp/for_loop("`For Loop`") cpp/ControlFlowGroup -.-> cpp/while_loop("`While Loop`") cpp/AdvancedConceptsGroup -.-> cpp/pointers("`Pointers`") cpp/IOandFileHandlingGroup -.-> cpp/output("`Output`") cpp/IOandFileHandlingGroup -.-> cpp/user_input("`User Input`") cpp/IOandFileHandlingGroup -.-> cpp/files("`Files`") subgraph Lab Skills cpp/operators -.-> lab-96119{{"`使用动态数组实现插入排序`"}} cpp/arrays -.-> lab-96119{{"`使用动态数组实现插入排序`"}} cpp/for_loop -.-> lab-96119{{"`使用动态数组实现插入排序`"}} cpp/while_loop -.-> lab-96119{{"`使用动态数组实现插入排序`"}} cpp/pointers -.-> lab-96119{{"`使用动态数组实现插入排序`"}} cpp/output -.-> lab-96119{{"`使用动态数组实现插入排序`"}} cpp/user_input -.-> lab-96119{{"`使用动态数组实现插入排序`"}} cpp/files -.-> lab-96119{{"`使用动态数组实现插入排序`"}} end

创建动态数组

首先,我们需要创建一个由用户指定大小的整数动态数组,并用 1 到 100 之间的随机整数填充它。

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int *arr;
    int size, i;

    cout << "Enter the size of the array: ";
    cin >> size;

    // 创建动态数组
    arr = new int[size];

    // 用 1 到 100 之间的随机整数填充数组
    for(i=0; i<size; i++) {
        arr[i] = rand() % 100 + 1;
    }

显示未排序的数组

接下来,我们将向用户显示未排序数组的内容。

    // 显示未排序的数组
    cout << "Unsorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

实现插入排序算法

现在,我们将实现插入排序(Insertion Sort)算法,该算法会将数组按升序排列。

    // 插入排序
    int j, temp;
    for(i=1; i<size; i++) {
        temp = arr[i];
        j = i - 1;
        while(j>=0 && arr[j]>temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }

显示排序后的数组

我们将向用户显示排序后的数组内容。

    // 显示排序后的数组
    cout << "Sorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

释放内存

最后,我们将释放动态数组使用的内存。

    // 释放内存
    delete [] arr;

    return 0;
}

编译并运行程序

将文件保存为 sort.cpp,并放置在 ~/project 目录下。

在终端中编译并运行程序:

$ cd ~/project
$ g++ sort.cpp -o sort
$ ./sort

总结

在本实验中,我们学习了如何使用 C++ 中的动态数组实现插入排序(Insertion Sort)算法。我们创建了一个由用户指定大小的动态数组,并用随机整数填充它,实现了插入排序算法,最后向用户显示了排序后的数组。我们还学习了如何释放动态数组使用的内存。

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