C语言程序设计十大排序—插入排序

1.概念✅

  排序是数据处理的基本操作之一，每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法，排序后的数据更易于处理和查找。在计算机发展的历程中，在排序算法的研究一直深受人们重视，出现了很多算法，在思路、效率、应用等方面各有特色。通过学习排序算法，读者可以理解不同算法的优势和局限性，并根据具体情况选择最合适的算法，以提高程序的性能和效率。学习排序算法还有助于培养逻辑思维和问题解决能力，在解决其他类型的问题时也能够应用到类似的思维方法。

2.插入排序🎈

  插入排序（Insertion Sort）是一种“动态”算法，在一个有序数列上这个增加数据，当新增一个数x时，把它插到有序数列中的合适位置，使数列扔保持有序。初始的数列是空的，这个插入所有的n个数据后，这n个数据就排好了序。
  如何把x插到合适的位置？简单的做法是从有序数列的最后一个开始，逐个与x比较，若这个数比x大，就继续往前找，直到找到比x小的数，把x插到它的后面。
  具体操作{12, 11, 13, 5, 6}为例，如下图所示:
 （1）从第一个数a[0]开始，它构成了长度为1的有序数列a[0]。

 （2）新增a[1]，把它插到有序数列{a[0]}中。

  若a[1]>a[0]，完成，
  若a[1]<a[0]，把a[1]插到a[0]的前面。方法是先把a[0]移到数列的第2个位置，然后把a[1]放到数列的第1个位置，得到新的有序数列{a[0],a[1]}。
  （3）新增a[2]，把它插到有序数列{a[0], a[1]}中。

  概括插入排序的原理：将待排序的元素划分为“已排序”和“未排序”两个部分，每次从“未排序的”元素中选取一个插到“已排序”元素中的正确位置。插入排序的一个列子是打扑克时抓牌，每抓一张牌，就插入到手中排好序的牌中。

3.代码实现✅

3.1 直接写✨

#include "stdio.h"
int main() {
    int arr[] = {12, 11, 13, 5, 6}; // 原始数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组大小
    int i;
     // 插入排序实现
    for ( i = 1; i < n; i++) {
        int key = arr[i];  // 当前待插入的元素
        int j = i - 1;

        // 将大于key的元素移到右侧
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // 插入当前元素到正确的位置
        arr[j + 1] = key;
    }

    // 打印排序后的数组
    printf("排序后的数组: \n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

3.2 函数✨

#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--;
        }
        // 插入当前元素到正确的位置
        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]); // 数组大小
    
    insertionSort(arr, n); // 调用插入排序函数
    printf("排序后的数组: \n");
    printArray(arr, n); // 打印排序后的数组

    return 0;
}

4.总结✅

  插入排序的计算复杂度取决于第5行的for循环和第8行的while循环，这是两重循环，各循环O(n)次，总计算复杂度O(n^2)。
    插入排序是不是和冒泡排序一样“聪明”？也就是说，如果待排序的数列已经有序了，再运行插入排序算法，插入排序是否知道已经排好序？此时第8行的while的判断条件a[i]>key始终不成立，while内的不会执行，而实际上就是a[i]=key，没有任何变化。也就是说，再次插入都是插到末尾，不用插到中间。那么for、while这两重循环实际上变成了只有for一个循环，一共计算O(n)次即结束。所以插入排序和“冒泡”排序一样“聪明”。

5.十大排序

1.冒泡排序
2.选择排序