以往博客的复习补充——part1

之前没更新是因为期末考试要复习，没空写博客。1月3号才考完，现在有空，打算从头看一遍，既是复习以前知识点，又是对原来的博客进行补充。刚好寒假，有大把时间。

一，希尔排序（Shell Sort）

算是插入排序的改进。因为插入算法相比三傻排序的另外两个，在序列有序时能够节省时间复杂；而且插入排序会在数据量比较小的时候效率比较高。所以通过增量将数组进行分组，开始增量较大，每组数据量较小，很快就能排有序。然后逐渐缩小增量，在分组内进行插入排序。直至增量为1.

还有就是增量是多少，就会分为几个组。因为一个组内两个元素的间隔为增量，中间就会夹着增量个元素，意味着还要分多少组。

希尔排序也叫作缩小增量排序。在排序过程中开始分组多但组内元素少，后来分组少元素多，但是越来越有序的。

具体过程看下面教程或者b站视频《数据结构合集——希尔排序》蓝不过海呀。

六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序-CSDN博客

我写下代码：

第一次写的，只能说是漏洞百出，不忍直视。

#include<stdio.h>int main()
{int arr[] = { 3,2,4,9,6,1,5,7,8 };int len = sizeof(arr) / sizeof(int);for (int i = 0; i < len; i++){printf("%d ", arr[i]);}printf("\n");int gap = len / 2;int turn = 2;while (turn){//当前增量下，会分为几组，也就会进行几轮插入排序。for (int i = 0; i < (len / gap); i++){int end = i;//end是有序队列末尾。int temp = arr[end + gap];//temp临时变量代表将要插入的元素。//接下来就是组内进行插入排序。while (end >= 0){if (arr[end] > temp){arr[end + gap] = arr[end];//大于插入元素的往后移，它的位置空出来了。end -= gap;}else break;}arr[end + gap] = temp;}//接下来更新增量，进行下一轮排序。gap /= 2;if (gap == 1) turn--;//第一次gap等于1时循环不会结束。}printf("end");for (int i = 0; i < len; i++){printf("%d ", arr[i]);}return 0;
}

这是AI分析出的问题：
 

问题 1：分组逻辑有误

在 for (int i = 0; i < (len / gap); i++) 这一部分，你的分组逻辑错误。希尔排序的核心思想是在当前增量 gap 下，对所有以 gap 为间隔的元素分组，然后对每组进行插入排序。这里你按 (len / gap) 的方式分组，但实际上应该从每个分组的起始点出发进行分组，即从 0 到 gap - 1 的每个起点出发。

---

问题 2：组内插入排序逻辑有误

int end = i;  // end 是有序队列的末尾
int temp = arr[end + gap];

这里 end 设置为 i 是不正确的，因为在希尔排序中，组内的有序序列需要从当前分组起点逐步扩展，而不是简单地以分组的索引作为 end。

正确的逻辑是从当前分组的起始点出发，按增量 gap 逐步移动进行插入排序。

---

问题 3：增量更新逻辑有误

你的增量更新逻辑是：

gap /= 2;
if (gap == 1) turn--;

这里你设置了一个变量 turn，试图在 gap == 1 时多循环一次。但这是不必要的，希尔排序的结束条件应当是 gap == 0，即在最后一次增量为 1 的插入排序完成后结束。

这是我自己改的代码

#include<stdio.h>int main()
{int arr[] = { 3,2,4,9,6,1,5,7,8 };int len = sizeof(arr) / sizeof(int);for (int i = 0; i < len; i++){printf("%d ", arr[i]);}printf("\n");int gap = len / 2;while (gap){//当前增量下，会分为几组，也就会进行几轮插入排序。for (int i = 0; i < gap; i++){int end = i;//end是有序队列末尾。从开始序号为i这组进行插入排序。while (end + gap < len){int temp = arr[end + gap];//temp临时变量代表将要插入的元素。//接下来就是组内进行插入排序。while (end >= 0){if (arr[end] > temp){arr[end + gap] = arr[end];//大于插入元素的往后移，它的位置空出来了。end -= gap;}else break;}arr[end + gap] = temp;end += gap;}}//接下来更新增量，进行下一轮排序。gap /= 2;}for (int i = 0; i < len; i++){printf("%d ", arr[i]);}return 0;
}

这是AI的答案

#include <stdio.h>int main()
{int arr[] = { 3, 2, 4, 9, 6, 1, 5, 7, 8 };int len = sizeof(arr) / sizeof(int);// 打印初始数组for (int i = 0; i < len; i++){printf("%d ", arr[i]);}printf("\n");// 希尔排序int gap = len / 2;  // 初始增量为数组长度的一半while (gap > 0){// 从每组的起点出发for (int i = gap; i < len; i++){int temp = arr[i];  // 当前待插入的元素int j = i;// 插入排序：对当前组进行排序while (j >= gap && arr[j - gap] > temp){arr[j] = arr[j - gap];  // 元素后移j -= gap;}arr[j] = temp;  // 插入到正确位置}gap /= 2;  // 缩小增量}// 打印排序后的数组for (int i = 0; i < len; i++){printf("%d ", arr[i]);}return 0;
}

ai这个好理解，将每组起点过后的元素进行插入排序，因为增量的存在，所以插入排序只会和自己所在组的进行比较。

另位博主写的代码

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap>1){//每次对gap折半操作gap = gap / 2;//单趟排序for (int i = 0; i < n - gap; ++i){int end = i;int tem = arr[end + gap];while (end >= 0){if (tem < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tem;}}
}

二，链表相加

以前写的

Node* add_twolist(Node* head1, Node* head2)
{Node* ans, * current, * cur1 = head1, * cur2 = head2;ans = current = NULL;int carry = 0;for (int sum, val;cur1 != NULL || cur2 != NULL;cur1 = (cur1 == NULL) ? NULL : cur1->next,cur2 = (cur2 == NULL) ? NULL : cur2->next){sum = (cur1 == NULL ? 0 : cur1->value)+ (cur2 == NULL ? 0 : cur2->value)+ carry;val = sum % 10;carry = sum / 10;if (ans == NULL)//create the new head node {ans = new Node(val);current = ans;}else{current->next = new Node(val);current = current->next;}}if (carry == 1)current->next = new Node(1);return ans;
}

这是复习时写的

Node* add_list(Node* h1, Node* h2)
{Node* head, * current;int value, carry;value = (h1->value + h2->value) % 10;carry = (h1->value + h2->value) / 10;head = current = new Node(value);h1 = h1->next;h2 = h2->next;while (h1 && h2){value = (h1->value + h2->value + carry) % 10;carry = (h1->value + h2->value + carry) / 10;Node* p = new Node(value);current->next = p;current = current->next;h1 = h1->next;h2 = h2->next;}while (h1){value = (h1->value + carry) % 10;carry = (h1->value + carry) / 10;Node* p = new Node(value);current->next = p;current = current->next;h1 = h1->next;}while (h2){value = (h2->value + carry) % 10;carry = (h2->value + carry) / 10;Node* p = new Node(value);current->next = p;current = current->next;h2 = h2->next;}if (carry){Node* p = new Node(carry);current->next = p;current = current->next;}return head;
}

三，分割链表

第一次

Node* seperate_list(Node* head, int target)
{Node* h1, * h2, * cur1, * cur2;h1 = cur1 = NULL;h2 = cur2 = NULL;while (head){if (head->value <= target){if (!h1)h1= head;else{cur1->next = head;cur1 = cur1->next;}}else{if (!h2)h2 = cur2 = head;else{cur2->next = head;cur2 = cur2->next;}}head = head->next;}cur1->next = h2;return h1;
}

能看出哪里有问题吗？

首先是两条链表赋值时，只让h1 = head，此时cur1还是NULL；

cur2的next可能没有指向空，导致打印链表时出现死循环。

例如数组int arr[] = { 3,2,6,5,4,7,1 };

还有第三个错误就是没有新造链表，直接使用原链表，原链表的节点之间的联系还没有解开，关系混乱。

改后

Node* seperate_list(Node* head, int target)
{Node* h1, * h2, * cur1, * cur2;h1 = cur1 = NULL;h2 = cur2 = NULL;while (head){if (head->value < target){if (!h1)h1 = cur1 = new Node(head->value);else{cur1->next = new Node(head->value);cur1 = cur1->next;}}else if(head->value > target){if (!h2)h2 = cur2 = new Node(head->value);else{cur2->next = new Node(head->value);cur2 = cur2->next;}}head = head->next;}cur1->next = new Node(target);cur1 = cur1->next;cur1->next = h2;if (!cur2) cur2->next = NULL;return h1;
}