插入排序C++ 份文件编写代码 优化
时间: 2023-08-10 12:58:31 浏览: 65
当然,我可以帮您编写插入排序的C++代码,并进行优化。以下是一个示例代码:
```cpp
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
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() {
std::vector<int> arr = {5, 2, 9, 1, 3};
insertionSort(arr);
std::cout << "Sorted array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
```
这是一个简单的插入排序实现,它使用了一个for循环遍历数组,并使用一个while循环将当前元素插入到已排序的子数组中的正确位置。最后,它打印出排序后的数组。
如果您希望对插入排序进行优化,可以考虑以下几点:
1. 使用二分查找来寻找插入位置:在while循环中,可以使用二分查找来快速找到要插入的位置,而不是逐个比较元素。这样可以提高插入排序的效率。
2. 对于较小的子数组,可以考虑使用插入排序的变体,例如希尔排序。希尔排序通过使用较大的间隔来交换元素,然后逐渐减小间隔,最终达到插入排序的效果。这样可以减少比较和交换的次数,提高排序的速度。
这些是一些常见的优化技巧,可以根据具体的需求和数据集进行选择和实现。希望对您有所帮助!