C 语言实现插入排序

1. 插入排序基础概念

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in - place排序（即只需用到O(1)的额外空间的排序），在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序的基本操作就是将一个数据插入到已经排好序的数组中的适当位置。对于给定的一组数据，假设第一个数据是已经排好序的，然后从第二个数据开始，将其与前面已排好序的数据依次比较，找到合适的位置插入。例如，对于数组 [5, 3, 4, 6, 2]，首先认为 [5] 是已排序的部分，然后对于 3，将其与 5 比较，发现 3 小于 5，于是将 5 向后移动一位，将 3 插入到 5 原来的位置，此时已排序部分变为 [3, 5]。接着对 4 进行操作，先与 5 比较，4 小于 5，5 向后移动一位，再与 3 比较，4 大于 3，所以将 4 插入到 3 和 5 之间，已排序部分变为 [3, 4, 5]，依此类推，直到所有数据都插入到合适位置，数组变为 [2, 3, 4, 5, 6]。

2. C 语言实现插入排序的原理

在C语言中实现插入排序，我们需要遍历数组，对于每个元素，将其插入到已排序部分的合适位置。具体步骤如下：

1. 从数组的第二个元素开始遍历数组（因为我们认为第一个元素已经是排好序的）。
2. 对于当前遍历到的元素，将其存储在一个临时变量中（例如 key）。
3. 从当前元素的前一个元素开始，与 key 进行比较。如果当前比较的元素大于 key，则将该元素向后移动一位。
4. 重复步骤3，直到找到一个小于或等于 key 的元素，或者已经比较到数组的开头。
5. 将 key 插入到上一步找到的位置之后。

下面是一个详细的C语言代码示例，展示了插入排序的实现过程：

#include <stdio.h>

// 插入排序函数定义
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // 将大于 key 的元素向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 打印数组的函数
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

3. 代码解析

3.1 插入排序函数 insertionSort

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

• 变量声明：

  • i 用于遍历数组，从第二个元素（索引为1）开始。
  • key 用于存储当前要插入的元素。
  • j 用于在已排序部分中寻找合适的插入位置。

• 外层循环：

  • for (i = 1; i < n; i++) 这个循环从数组的第二个元素开始，依次处理每个元素，直到数组末尾。

• 内层循环：

  • while (j >= 0 && arr[j] > key) 这个循环从当前元素的前一个元素开始，向前比较。只要当前比较的元素大于 key，就将该元素向后移动一位，同时 j 减1，继续向前比较。当找到一个小于或等于 key 的元素，或者 j 小于0（即已经比较到数组开头）时，循环结束。

• 插入操作：

  • 循环结束后，j 的位置就是 key 应该插入的位置的前一个位置。所以 arr[j + 1] = key 将 key 插入到合适的位置。

3.2 打印数组函数 printArray

void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

这个函数很简单，通过一个 for 循环遍历数组，并使用 printf 函数将每个元素打印出来，最后换行。

3.3 主函数 main

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

• 数组初始化：

  • int arr[] = {12, 11, 13, 5, 6}; 定义并初始化了一个整数数组。
  • int n = sizeof(arr) / sizeof(arr[0]); 计算数组的长度。

• 打印原始数组：

  • 使用 printArray 函数打印数组的原始状态。

• 调用插入排序函数：

  • insertionSort(arr, n); 调用插入排序函数对数组进行排序。

• 打印排序后的数组：

  • 再次使用 printArray 函数打印排序后的数组。

4. 插入排序的时间复杂度和空间复杂度

4.1 时间复杂度

插入排序的时间复杂度取决于数据的初始状态。

• 最好情况：当数组已经是有序的时候，插入排序的时间复杂度为 O(n)。因为对于每个元素，只需要与它前面的一个元素比较一次（由于数组有序，不需要移动元素），总共n - 1次比较，所以时间复杂度为线性时间。
• 最坏情况：当数组是逆序的时候，插入排序的时间复杂度为 O(n^2)。对于第i个元素，需要与前面i - 1个元素比较并移动i - 1次。总的比较和移动次数为1 + 2 + 3 +... + (n - 1)，根据等差数列求和公式，其和为n(n - 1)/2，所以时间复杂度为 O(n^2)。
• 平均情况：平均情况下，插入排序的时间复杂度也是 O(n^2)。虽然实际应用中数据很少是完全有序或逆序的，但平均下来，比较和移动操作的次数仍然与 n^2 成正比。

4.2 空间复杂度

插入排序是一种in - place排序算法，它只需要一个额外的变量（即 key）来存储当前要插入的元素，所以空间复杂度为 O(1)。这意味着无论数组的大小如何，插入排序所需的额外空间都是固定的。

5. 插入排序的应用场景

1. 小规模数据：由于插入排序在小规模数据上表现良好，并且实现简单，当数据量较小时，使用插入排序可以快速完成排序任务。例如，在一些嵌入式系统中，处理的数据量通常较小，插入排序可以在资源有限的情况下高效地完成排序。
2. 部分有序数据：如果数据已经部分有序，插入排序可以利用这一特点，快速地将剩余元素插入到合适位置，时间复杂度接近最好情况的 O(n)。比如，在一些实时数据处理场景中，新的数据不断到来，并且这些数据可能是大致按顺序的，插入排序就可以有效地对新数据进行排序并融入到已有的有序数据中。
3. 作为其他算法的子过程：插入排序有时会作为更复杂排序算法的一部分。例如，在快速排序中，当子数组规模较小时，使用插入排序可以避免递归调用带来的额外开销，提高整体排序效率。

6. 优化插入排序

虽然标准的插入排序在大多数情况下时间复杂度为 O(n^2)，但我们可以对其进行一些优化。

1. 二分查找优化：在寻找插入位置时，可以使用二分查找来代替线性查找。标准插入排序中，在已排序部分寻找插入位置是通过线性比较实现的，时间复杂度为 O(n)。而二分查找可以将这一过程的时间复杂度降低到 O(log n)。不过，虽然查找位置的时间复杂度降低了，但移动元素的时间复杂度仍然是 O(n)，所以整体时间复杂度还是 O(n^2)，但在一定程度上可以提高效率。以下是使用二分查找优化后的插入排序代码：

#include <stdio.h>

// 二分查找函数，返回要插入的位置
int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == key)
            return mid + 1;
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low;
}

// 优化后的插入排序函数
void insertionSortOptimized(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        int pos = binarySearch(arr, 0, j, key);

        while (j >= pos) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 打印数组的函数
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    insertionSortOptimized(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

2. 链表实现：使用链表来实现插入排序可以减少元素移动的开销。在数组中，移动元素需要将后续元素依次向后或向前移动，而链表只需要修改指针即可。不过，链表实现的插入排序在查找插入位置时可能会稍微复杂一些，因为链表不支持随机访问，需要从头遍历。以下是一个简单的链表插入排序示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 创建新节点的函数
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 打印链表的函数
void printList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 链表插入排序函数
struct Node* insertionSortList(struct Node* head) {
    if (head == NULL || head->next == NULL)
        return head;

    struct Node* sorted = head;
    struct Node* current = head->next;
    sorted->next = NULL;

    while (current != NULL) {
        struct Node* temp = current;
        current = current->next;

        if (temp->data < sorted->data) {
            temp->next = sorted;
            sorted = temp;
        } else {
            struct Node* search = sorted;
            while (search->next != NULL && search->next->data < temp->data) {
                search = search->next;
            }
            temp->next = search->next;
            search->next = temp;
        }
    }
    return sorted;
}

// 主函数
int main() {
    struct Node* head = createNode(12);
    head->next = createNode(11);
    head->next->next = createNode(13);
    head->next->next->next = createNode(5);
    head->next->next->next->next = createNode(6);

    printf("Original list: \n");
    printList(head);

    head = insertionSortList(head);

    printf("Sorted list: \n");
    printList(head);

    return 0;
}

7. 与其他排序算法的比较

1. 与冒泡排序比较：

   • 时间复杂度：冒泡排序和插入排序在最坏和平均情况下的时间复杂度都是 O(n^2)。但在最好情况下，插入排序为 O(n)，而冒泡排序仍为 O(n^2)，因为冒泡排序即使在数组有序时也需要进行 n - 1 次比较，而插入排序只需要 n - 1 次简单比较，不需要移动元素。
   • 稳定性：两者都是稳定的排序算法。稳定性是指相等元素在排序前后的相对顺序不变。在插入排序中，当遇到相等元素时，后出现的元素会插入到后面，相对顺序不变；冒泡排序在交换元素时，也不会改变相等元素的相对顺序。
   • 实现复杂度：插入排序实现相对简单，代码量通常较少，尤其是对于小规模数据的处理更具优势。

2. 与选择排序比较：

   • 时间复杂度：选择排序在任何情况下的时间复杂度都是 O(n^2)，而插入排序在最好情况下为 O(n)。选择排序每次都从未排序部分选择最小（或最大）的元素，与未排序部分的起始位置交换，无论数据的初始状态如何，比较次数都是固定的。
   • 稳定性：选择排序是不稳定的排序算法，例如对于数组 [5, 5, 3]，选择排序在第一次选择最小元素时，会将第一个 5 与 3 交换，改变了两个 5 的相对顺序。而插入排序是稳定的。
   • 移动次数：选择排序每次交换都要移动元素，移动次数为 n - 1 次；插入排序在最好情况下不需要移动元素，平均和最坏情况下移动次数较多，但在部分有序数据的情况下，移动次数会相对较少。

3. 与快速排序比较：

   • 时间复杂度：快速排序平均时间复杂度为 O(n log n)，在大多数情况下比插入排序的 O(n^2)要快得多。但快速排序的最坏时间复杂度为 O(n^2)，例如当每次选择的基准元素都是数组中的最大或最小元素时。而插入排序在小规模数据或部分有序数据上可能表现更好。
   • 空间复杂度：快速排序需要额外的栈空间来进行递归调用，平均空间复杂度为 O(log n)，最坏情况下为 O(n)；插入排序的空间复杂度为 O(1)，在空间要求严格的情况下，插入排序更有优势。
   • 稳定性：快速排序通常是不稳定的，而插入排序是稳定的。如果数据中相等元素的相对顺序很重要，插入排序可能是更好的选择。

通过对插入排序的深入分析，包括原理、实现、复杂度、应用场景、优化以及与其他排序算法的比较，我们可以更好地理解这一经典排序算法，并在实际编程中根据具体需求灵活应用。无论是小规模数据处理，还是作为其他复杂算法的一部分，插入排序都有着独特的价值。