数据结构直接插入排序代码c++
时间: 2023-12-11 09:32:39 浏览: 44
以下是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;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] =;
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
```
相关问题
c++数据结构直接插入排序
直接插入排序是一种简单的排序算法,它通过构建有序序列逐步地插入待排序元素。它的基本思想是将待排序的元素按照大小依次插入已经有序的序列中,直到所有元素都插入完毕形成有序序列。
具体实现步骤如下:
1. 首先,将第一个元素视为已经排好序的序列。
2. 然后,从第二个元素开始,依次将其插入到已排好序的序列中。
3. 对于第 i 个元素,将其与已排好序的序列中的元素从后往前进行比较,找到合适的位置插入。
4. 重复步骤 3,直到所有元素都插入完毕。
下面是一个使用 C 语言实现直接插入排序的例子:
```c
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// 将 arr[j] 大于 key 的元素后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("排序后的数组:");
printArray(arr, n);
return 0;
}
```
以上代码中,我们使用 `insertionSort` 函数实现直接插入排序,并使用 `printArray` 函数打印排序后的数组。在 `main` 函数中,我们定义了一个待排序的数组 `arr`,并通过调用 `insertionSort` 函数对其进行排序。
输出结果为:
```
排序后的数组:5 6 11 12 13
```
这就是直接插入排序的基本实现方法。希望对你有所帮助!如果还有其他问题,请随时提问。
数据结构折半插入排序c++
以下是C++实现的折半插入排序代码:
```c++
void binaryInsertSort(int arr[], int len) {
for (int i = 1; i < len; i++) {
int temp = arr[i];
int left = 0, right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > temp) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
}
}
```
折半插入排序的基本思想是:将一个元素插入到已经排好序的数组中,仍然保持有序。与直接插入排序不同的是,折半插入排序使用二分查找来寻找插入位置,从而减少了比较次数,提高了排序效率。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.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)