直接插入排序c语言怎么做
时间: 2023-11-27 16:46:53 浏览: 57
以下是直接插入排序的C语言实现代码:
```c
void InsertSort(int* a, int n) {
assert(a);
for (int i = 0; i < n - 1; ++i) {
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (tmp < a[end]) {
a[end + 1] = a[end];
--end;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
```
直接插入排序的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。具体实现时,将待排序的第一个元素看作是一个有序的子序列,然后从第二个元素开始,逐个将其插入到有序子序列中,直到整个序列有序为止。
相关问题
c语言要求编写程序实现直接插入排序的功能插入排序从第二个数开始,拿出第二个数向前进行插入排序,一直到最后一个数向前做插入排序,要求输出每趟插入排序的结果。
以下是一个简单的C语言程序,实现直接插入排序的功能,每趟插入排序的结果都会被输出。
```c
#include <stdio.h>
void insertion_sort(int arr[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
temp = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
printf("第%d趟排序后的结果:", i);
for (int k = 0; k < n; k++) {
printf("%d ", arr[k]);
}
printf("\n");
}
}
int main() {
int arr[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数据为:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n\n");
insertion_sort(arr, n);
printf("\n排序后的结果:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
输出结果:
```
原始数据为:3 1 4 1 5 9 2 6 5 3 5
第1趟排序后的结果:1 3 4 1 5 9 2 6 5 3 5
第2趟排序后的结果:1 1 3 4 5 9 2 6 5 3 5
第3趟排序后的结果:1 1 3 4 5 9 2 6 5 3 5
第4趟排序后的结果:1 1 3 4 5 9 2 6 5 3 5
第5趟排序后的结果:1 1 3 4 5 5 9 2 6 3 5
第6趟排序后的结果:1 1 3 4 5 5 9 2 6 3 5
第7趟排序后的结果:1 1 2 3 4 5 5 9 6 3 5
第8趟排序后的结果:1 1 2 3 4 5 5 6 9 3 5
第9趟排序后的结果:1 1 2 3 4 5 5 6 9 3 5
第10趟排序后的结果:1 1 2 3 3 4 5 5 6 9 5
第11趟排序后的结果:1 1 2 3 3 4 5 5 5 6 9
排序后的结果:1 1 2 3 3 4 5 5 5 6 9
```
怎么对链表进行排序 在c语言环境下
在C语言环境下对链表进行排序,可以使用不同的算法,例如插入排序、归并排序或者快速排序。下面是一个使用插入排序算法对链表进行排序的基本示例:
首先,定义链表节点结构体:
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
```
然后,实现插入排序算法对链表进行排序:
```c
void sortLinkedList(Node** head) {
if (*head == NULL) {
return; // 链表为空时,直接返回
}
Node* sorted = NULL; // 用于存放已排序部分的链表头节点
// 遍历原链表,逐个节点地将节点插入到已排序链表中
while (*head != NULL) {
Node* current = *head; // 当前要排序的节点
*head = (*head)->next; // 将原链表的头指针移动到下一个节点
// 找到插入的位置,并插入到已排序的链表中
if (sorted == NULL || sorted->data >= current->data) {
current->next = sorted;
sorted = current;
} else {
Node* sortedCurrent = sorted;
while (sortedCurrent->next != NULL && sortedCurrent->next->data < current->data) {
sortedCurrent = sortedCurrent->next;
}
current->next = sortedCurrent->next;
sortedCurrent->next = current;
}
}
*head = sorted; // 更新链表头指针为已排序链表的头指针
}
```
这里是如何使用该排序函数的示例:
```c
int main() {
Node* head = NULL;
// 假设这里已经创建了一个链表并初始化了一些数据
sortLinkedList(&head); // 对链表进行排序
// 排序后,可以遍历链表打印结果,或者做其他操作
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
return 0;
}
```