在归并排序中,对小数组进行插入排序 c++代码
时间: 2023-06-02 22:05:41 浏览: 28
很好,这是一个关于算法的问题,我可以回答。以下是对小数组进行插入排序的 C 代码:
```c
void insert_sort(int arr[], int start, int end) {
int i, j;
for (i = start + 1; i <= end; i++) {
int curr = arr[i];
j = i - 1;
while (j >= start && arr[j] > curr) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = curr;
}
}
void merge_sort(int arr[], int start, int end) {
if (end - start < 16) {
insert_sort(arr, start, end);
return;
}
int mid = (start + end) / 2;
merge_sort(arr, start, mid);
merge_sort(arr, mid + 1, end);
int temp[end - start + 1];
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= end) {
temp[k++] = arr[j++];
}
memcpy(arr + start, temp, sizeof(int) * (end - start + 1));
}
```
以上代码是将 Merge Sort 和 Insertion Sort 结合起来使用,当待排序的数组长度小于 16 时,使用插入排序算法来排序。这一策略可以在一些情况下提升算法的效率。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)