数据演示插入排序过程
在插入排序算法中，我们需要将未排序部分的元素逐个插入到已排序部分的适当位置。具体来说，对于第 i 个未排序元素，我们需要将其与已排序部分的元素从右到左逐个比较，找到其在已排序部分中的正确位置。
我将使用以下数据来演示插入排序算法的排序过程：
10 7 1 3 8 9
首先，我们将第一个元素 10 视为已排序数组，将剩余的元素视为未排序数组。接下来，我们将第二个元素 7 与已排序数组中的元素进行比较：
10 7 1 3 8 9
因为 7 小于 10，所以我们将 7 插入到已排序数组的前面：
7 10 1 3 8 9
接下来，我们将第三个元素 1 插入到已排序数组中的正确位置。
我们需要将 1 与已排序数组中的每个元素逐个比较，找到它应该插入的位置。首先，我们将 1 与 10 进行比较，因为 1 小于 10，所以我们继续将 1 与 7 进行比较。因为 1 小于 7，所以我们将 1 插入到 7 的前面：
1 7 10 3 8 9
接下来，我们将第四个元素 3 插入到已排序数组中的正确位置。我们需要将 3 与已排序数组中的每个元素逐个比较，找到它应该插入的位置。首先，我们将 3 与 10 进行比较，因为 3 小于 10，所以我们继续将 3 与 7 进行比较。因为 3 小于 7，所以我们将 3 插入到 7 的前面：
1 3 7 10 8 9
接下来，我们将第五个元素 8 插入到已排序数组中的正确位置。我们需要将 8 与已排序数组中的每个元素逐个比较，找到它应该插入的位置。首先，我们将 8 与 10 进行比较，因为 8 小于 10，所以我们继续将 8 与 7 进行比较。因为 8 大于 7，所以我们将 8 插入到 7 的后面：
1 3 7 8 10 9
最后，我们将第六个元素 9 插入到已排序数组中的正确位置。我们需要将 9 与已排序数组中的每个元素逐个比较，找到它应该插入的位置。首先，我们将 9 与 10 进行比较，因为 9 小于 10，所以我们继续将 9 与 8 进行比较。因为 9 大于 8，所以我们将 9 插入到 8 的后面：
1 3 7 8 9 10
因此，最终的排序结果为：
1 3 7 8 9 10
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
for (; j >= 0 && arr[j] > key; j--)
arr[j + 1] = arr[j];
arr[j + 1] = key;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
insertionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}输出：
Original array: 12 11 13 5 6 Sorted array: 5 6 11 12 13
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
int i, key, j;
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;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
insertionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}在上面的示例中，insertionSort() 函数是用来实现插入排序算法的。该函数接受一个整数数组和该数组的大小作为参数，并在原地对数组进行排序。printArray() 函数用于打印数组。
插入排序算法的基本思想是将数组分为已排序和未排序两部分，每次将未排序部分中的一个元素插入到已排序部分的正确位置。在上面的示例中，我们使用了一个 while 循环来找到插入元素的正确位置，然后将数组中的元素后移以腾出插入元素的位置。最后，将插入元素插入到正确的位置。
以下是一个简单的示例，展示了如何使用 while 循环来实现元素后移的操作：
int i, j;
int n = 5;
int arr[n] = {5, 3, 8, 2, 7};
// 从第二个元素开始遍历未排序的元素
for (i = 1; i < n; i++) {
int temp = arr[i];
j = i - 1;
// 将比当前元素大的元素向后移动一位
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
// 将当前元素插入到正确的位置
arr[j + 1] = temp;
}在上面的代码中，我们使用 for 循环来遍历未排序的元素，并使用 while 循环将比当前元素大的元素向后移动一位。在 while 循环中，我们首先检查 j 是否大于等于 0，并且已排序数组中的当前元素是否大于 temp（即当前未排序元素的值）。如果是，则将 arr[j] 向右移动一位，并将 j 减 1。如果不是，则退出 while 循环。
在 while 循环完成后，我们将当前未排序元素 temp 插入到正确的位置（即 j+1 的位置）。这个位置是在 while 循环中找到的，它是第一个比 temp 小的已排序元素的位置加 1。
