插入排序程序C++for循环
时间: 2024-05-17 13:10:55 浏览: 12
插入排序是一种简单直观的排序算法,在实现上通常采用in-place排序(即只需要用到O(1)的额外空间的排序),稳定排序算法。以下是一个使用C++ for 循环实现插入排序的示例代码:
```
void insertSort(int arr[], int n) {
int i, j, key;
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;
}
}
```
这段代码的基本思路是:从第二个元素开始,依次将该元素与前面已排序的元素进行比较,找到该元素在已排序数组中的正确位置,并将其插入到相应位置。具体实现是通过一个内层循环,不断地将比当前元素大的元素后移一位,直到找到正确位置,再将该元素插入到该位置。
相关问题
插入排序c++语言程序
插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在C++中,插入排序可以这样实现:
```cpp
#include <iostream>
// 插入排序函数
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// 将arr[j]大于key的元素向右移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// 插入元素
arr[j + 1] = key;
}
}
int main() {
int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10};
int n = sizeof(arr) / sizeof(arr);
std::cout << "Original array: ";
for (int i = 0; i < n; ++i) {
std::cout << arr[i] << " ";
}
insertionSort(arr, n);
std::cout << "\nSorted array: ";
for (int i = 0; i < n; ++i) {
std::cout << arr[i] << " ";
}
return 0;
}
```
在这个程序中,`insertionSort`函数接收一个整数数组和它的大小作为参数,然后通过循环和比较过程对数组进行排序。`main`函数则展示了如何调用这个排序函数,并输出排序前后的数组。
直接插入排序算法c++
直接插入排序算法是一种简单直观的排序算法,它的基本思想是将一个记录插入到已经排好序的有序序列中,从而得到一个新的、记录数增加1的有序序列。下面是一个使用C++实现的直接插入排序算法的示例代码:
```cpp
#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;
// 将比 key 大的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
这段代码实现了直接插入排序算法。首先,我们定义了一个名为`insertionSort`的函数,该函数接受一个整型数组和数组的大小作为参数。在函数内部,我们使用了两个循环来实现插入排序的逻辑。外层循环从第二个元素开始遍历数组,内层循环用于将比当前元素大的元素向后移动,为当前元素找到合适的插入位置。最后,我们在`main`函数中定义了一个整型数组,并调用`insertionSort`函数对数组进行排序。最后,我们输出排序后的数组。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)