25.6.5学习总结

归并排序（Merge Sort）

1. 概述

归并排序是一种基于分治思想的排序算法。它通过递归的方式，将待排序的数组不断分割成两半，直到每个子数组只剩一个元素（自然排序）；然后，将这些子数组逐步合并成有序的数组。

2. 主要思想

• 分解（Divide）：将数组分成左右两个子数组。

• 解决（Conquer）：递归对左右子数组排序。

• 合并（Combine）：合并两个已排序的子数组，得到一个大的有序数组。

3.递归实现的归并排序 

#include <stdio.h>
#include <stdlib.h>// 合并两个有序子数组
void merge(int* arr, int l, int m, int r) {int i = l, j = m + 1, k = 0;int size = r - l + 1;int* temp = (int*)malloc(sizeof(int) * size);while (i <= m && j <= r) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 复制剩余元素while (i <= m) {temp[k++] = arr[i++];}while (j <= r) {temp[k++] = arr[j++];}// Copy back到原数组for (int p = 0; p < size; p++) {arr[l + p] = temp[p];}free(temp);
}// 归并排序递归实现
void mergeSort(int* arr, int l, int r) {if (l >= r) return;int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);
}int main() {int arr[] = {8, 4, 5, 7, 1, 3, 2, 6};int size = sizeof(arr) / sizeof(arr[0]);mergeSort(arr, 0, size - 1);for (int i=0; i<size; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

 4.非递归（迭代）实现的归并排序

#include <stdio.h>
#include <stdlib.h>void merge(int* arr, int l, int m, int r) {int i = l, j = m + 1, k = 0;int size = r - l + 1;int* temp = (int*)malloc(sizeof(int) * size);while (i <= m && j <= r) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}while (i <= m) temp[k++] = arr[i++];while (j <= r) temp[k++] = arr[j++];for (int p = 0; p < size; p++) {arr[l + p] = temp[p];}free(temp);
}void mergeSortIterative(int* arr, int n) {for (int curr_size = 1; curr_size < n; curr_size *= 2) {for (int left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {int mid = left_start + curr_size - 1;int right_end = (left_start + 2 * curr_size - 1) < n -1 ? (left_start + 2 * curr_size -1) : (n -1);if (mid < right_end) {merge(arr, left_start, mid, right_end);}}}
}int main() {int arr[] = {8, 4, 5, 7, 1, 3, 2, 6};int size = sizeof(arr) / sizeof(arr[0]);mergeSortIterative(arr, size);for (int i=0; i<size; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

希尔排序（Shell Sort）

1. 概述

希尔排序是一种基于插入排序的改进版本，由Donald Shell于1959年提出。它利用“比较和交换”的思想，对数据进行“分组排序”，逐步缩小分组间的间隔（步长）最终实现整体排序。

2. 核心思想

• 初始时，将整个数组按一定间隔（步长）划分成若干子数组，对每个子数组进行插入排序。

• 随着算法进行，逐渐减小间隔，经过多轮排序，最终间隔缩减为1，完成整体排序。

• 当步长为1时，实际上执行一次插入排序，确保整个数组有序。

3. 步骤

1. 选择一个初始的间隔（通常为数组长度的一半）。

2. 对所有间隔为gap的子数组执行插入排序。

3. 缩小gap。

4. 重复步骤2和3，直到gap为1，即对整个数组执行一次插入排序。

5. 最终，数组全部有序。

#include <stdio.h>void shellSort(int arr[], int n) {// 选择初始间隔（gap）for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个gap的子数组执行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;// 插入排序（在gap间隔内）for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}int main() {int arr[] = {8, 4, 5, 7, 1, 3, 2, 6};int size = sizeof(arr) / sizeof(arr[0]);printf("排序前：\n");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");shellSort(arr, size);printf("排序后：\n");for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}