在C++中简单说明插入排序的算法思想
时间: 2024-03-12 21:48:08 浏览: 18
在C++中实现插入排序的算法思想和上面提到的一样,具体实现步骤如下:
1. 从第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,从已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5,直到排序完成
C++代码实现如下:
```cpp
void insertionSort(int arr[], int n)
{
for(int i = 1; i < n; i++)
{
int key = arr[i];
int j = i - 1;
while(j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
```
其中,arr表示待排序的数组,n表示数组的长度。外层循环从第二个元素开始遍历,内层循环不断将当前元素与已排序的元素比较,找到插入的位置,最后将该元素插入到相应的位置上。
需要注意的是,在C++中,数组下标从0开始,因此在实现插入排序时,需要将外层循环的起始值设为1,而不是0。
相关问题
c++写份插入排序算法代码
当然可以!以下是一个使用C++编写的插入排序算法代码示例:
```cpp
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {5, 2, 8, 12, 1, 6};
int n = sizeof(arr) / sizeof(arr);
insertionSort(arr, n);
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
这段代码实现了插入排序算法。插入排序的基本思想是将数组分为已排序和未排序两部分,每次从未排序部分取出一个元素,插入到已排序部分的正确位置。通过不断重复这个过程,最终完成整个数组的排序。
直接插入排序算法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`函数对数组进行排序。最后,我们输出排序后的数组。