插入排序 C语言代码
时间: 2023-10-29 07:36:38 浏览: 47
好的,以下是插入排序的C语言代码:
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] = key;
}
}
请问还有其他问题吗?
相关问题
折半插入排序C语言代码复杂度最低
折半插入排序(也称为二分插入排序)是一种改进的插入排序算法,它适用于部分有序的数据。在最坏情况下,它的时间复杂度仍然是O(n^2),但在最好情况下(输入数组已经是有序的),它的效率会提高,达到线性时间复杂度,即O(n)。
以下是C语言中折半插入排序的简化实现:
```c
#include <stdio.h>
void binaryInsertionSort(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--;
}
arr[j + 1] = key;
}
}
// 主函数演示
int main() {
int arr[] = {9, 7, 5, 11, 12, 2, 14, 3};
int n = sizeof(arr) / sizeof(arr);
printf("原始数组: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
binaryInsertionSort(arr, n);
printf("\n排序后数组: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
```
数据结构二路插入排序c语言代码
以下是二路插入排序的C语言代码示例:
```c
// 二路插入排序
void TwoWayInsertSort(int r[], int n) {
int i, j, low, high, mid;
int temp[n+1];
temp[0] = r[0]; // 哨兵
low = 0;
high = 0;
for (i = 1; i <= n; i++) {
if (r[i] < temp[low]) { // 插入到前半部分
low = (low - 1 + n) % n;
temp[low] = r[i];
} else if (r[i] >= temp[high]) { // 插入到后半部分
high = (high + 1) % n;
temp[high] = r[i];
} else { // 插入到中间部分
mid = (low + 1) % n;
while (r[i] >= temp[mid]) {
low = mid;
mid = (mid + 1) % n;
}
high = (high + 1) % n;
for (j = high; j != mid; j = (j - 1 + n) % n) {
temp[j] = temp[(j - 1 + n) % n];
}
temp[mid] = r[i];
}
}
for (i = 1; i <= n; i++) {
r[i] = temp[(low + i) % n];
}
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)