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;
}