简介
在本实验中,我们将学习如何使用 C++ 中的动态数组实现插入排序(Insertion Sort)算法。该算法是一种简单的排序算法,通过将列表分为已排序和未排序两部分,然后将未排序列表中的每个元素插入到已排序列表的正确位置来完成排序。
在本实验中,我们将学习如何使用 C++ 中的动态数组实现插入排序(Insertion Sort)算法。该算法是一种简单的排序算法,通过将列表分为已排序和未排序两部分,然后将未排序列表中的每个元素插入到已排序列表的正确位置来完成排序。
首先,我们需要创建一个由用户指定大小的整数动态数组,并用 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)算法。我们创建了一个由用户指定大小的动态数组,并用随机整数填充它,实现了插入排序算法,最后向用户显示了排序后的数组。我们还学习了如何释放动态数组使用的内存。