【嵌入式八股22】排序算法与哈希算法

一、排序算法

排序算法是计算机科学中用于将一组数据按照特定顺序排列的方法。常见的排序算法包括选择排序、插入排序、希尔排序、冒泡排序、快速排序、堆排序和归并排序等。以下将详细介绍几种常见排序算法的特性、实现及比较。

排序算法的性能比较可以参考以下图示：

（一）选择排序

选择排序是一种简单直观的排序算法。其基本思想是在每一轮从待排序序列中选择最小（或最大）的元素，将其放置到已排序序列的末尾。该算法的时间复杂度无论数据初始状态如何，均为 ，因此适用于数据规模较小的情况。它的优点是不占用额外的内存空间，空间复杂度为 。

1. 时间复杂度
   • 平均：
   • 最好：
   • 最坏：
2. 空间复杂度：
3. 算法步骤
   • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
   • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
   • 重复第二步，直到所有元素均排序完毕。
4. 动图演示

5. 代码实现

/* 直接选择排序 */
void selection_sort(int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (x[j] < x[min]) {
                min = j;
            }
        }
        if (min != i) {
            // 假设 swap 函数已实现，用于交换数组 x 中索引为 i 和 min 的元素
            swap(x, i, min); 
        }
    }
}

（二）插入排序

插入排序是一种简单直观的排序算法，其原理类似于整理扑克牌时的操作。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序有一个优化版本，即折半插入排序，通过二分查找来确定插入位置，提高了部分情况下的效率。

1. 时间复杂度
   • 平均：
   • 最好：（当数据基本有序时）
   • 最坏：
2. 空间复杂度：
3. 算法步骤
   • 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
   • 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
4. 动图演示

5. 代码实现

/* 直接插入排序 */
void insertion_sort(int n) {
    for(int i = 1; i < n; i++) {
        int t = x[i];
        int j;
        for (j = i; j > 0 && x[j-1] > t ; j--) {
            x[j] = x[j - 1];
        }
        x[j] = t;
    }
}

（三）希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。它是一种非稳定排序算法。其基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

1. 时间复杂度
   • 平均：
   • 最好：（当数据具有特定的有序性时）
   • 最坏：
2. 空间复杂度：
3. 算法步骤
   • 选择一个增量序列 ，其中 （），且 。
   • 按增量序列个数 ，对序列进行 趟排序。
   • 每趟排序，根据对应的增量 ，将待排序列分割成若干长度为 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4. 代码实现

/* 希尔排序 */
void shell_sort(int n) {
    for (int inc = n/3; inc >= 1; inc /= 3 ) {
        for (int i = inc; i < n; i++) {
            int t = x[i];
            int j;
            for (j = i; j >= inc && x[j - inc] > t ; j -= inc) {
                x[j] = x[j - inc];
            }
            x[j] = t;
        }
    }
}

（四）冒泡排序

冒泡排序是一种简单的比较排序算法。其基本思想是重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到数列不再需要交换，也就是说该数列已经排序完成。

1. 时间复杂度
   • 平均：
   • 最好：（当数据已经有序时）
   • 最坏：
2. 空间复杂度：
3. 算法步骤
   • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
   • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
   • 针对所有的元素重复以上的步骤，除了最后一个。
   • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
4. 动图演示

5. 代码实现

/* 冒泡排序 */
void bubble_sort(int n) {
    bool change = true;
    for (int i = n-1; i >= 1 && change; i--) {
        change = false;
        for (int j = 0; j < i; j++) {
            if(x[j] > x[j + 1]) {