嵌入式 数据结构之基础算法
1.冒泡排序⭐⭐⭐⭐
冒泡排序(Bubble Sort)是一种较简单的排序算法,其思想是重复地走访要排序的元素列,依次比较两个相邻的元素,如果顺序错误就交换它们。这个过程会重复进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成。算法的名字来源于越小的元素会经由交换慢慢“浮”到数列的顶端,就像碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,因此得名“冒泡排序”。
#include <iostream> using namespace std; void bubbleSort(int arr[], int n) { for(int i = 0; i < n - 1; i++){ for(int j = 0; j < n - i - 1; j++){ if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
2.选择排序⭐⭐⭐⭐
选择排序是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,继续放在起始位置直到未排序元素个数为0。
选择排序的步骤:
- 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小(大)元素,然后放到未排序序列的起始位置。
- 重复第二步,直到所有元素均排序完毕。
#include <iostream> using namespace std; void selectionSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { int minIndex = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }
3.插入排序⭐⭐⭐⭐
插入排序是一种简单直观的排序算法,它的工作原理是通过对未排序部分的元素逐一进行比较,并按大小顺序逐步“插入”到已排序部分中的适当位置,最终完成整个序列的排序。
插入排序步骤:
- 从第一个元素开始,该元素可以认为已经被排序:将待排序序列的第一个元素作为已排序序列的起始。
- 取下一个元素tem,从已排序的元素序列从后往前扫描:从待排序序列中选择下一个元素,暂存到变量tem中。
- 如果该元素大于tem,则将该元素移到下一位:比较已排序序列中的元素与tem的大小,如果发现某个已排序元素大于tem,将该元素后移一位。
- 重复步骤3,直到找到已排序元素中小于等于tem的元素:继续向前扫描已排序序列,直到找到一个小于等于tem的元素。
- tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置:将tem插入到已排序序列中小于等于tem的元素的后面。如果已排序中的所有元素都大于tem,则将tem插入到已排序序列的首位。
- 重复步骤2~5:重复以上步骤,直到待排序序列中所有元素都被插入到已排序序列中。
#include <iostream> using namespace std; void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; 默认i之前的元素是排列好的 // 将大于key的元素向后移动 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }
4.希尔排序⭐⭐
希尔排序,也被称为缩小增量排序,是插入排序的一种改进算法。它通过将原始序列分割为多个较小的子序列来进行排序,最终将整个序列排序。
希尔排序的步骤如下:
- 首先,选择一个增量序列,可以是固定的间隔或者动态计算得到。
- 根据增量序列,将整个序列分割成若干个子序列。
- 对每个子序列进行插入排序。
- 不断缩小增量,重复步骤2和3,直到增量为1。
- 最后一次使用增量为1的子序列进行排序,完整的排序过程结束。
作者自我理解:实际上希尔排序就是插入排序的优化,也就是他的插入排序 plus,所以我们只需要知道他怎么把插入排序用到了里边就可以理解这个算法。
1.首先假如有五个元素 5 3 2 4 6
2.第一次增量取 n/2,增量就是两个数之间的位置间隔,间隔一样的是一组;比如现在取的是5/2=2,那么 【5 2 6】 是一组,【3,4】是一组。
以此类推。。。。。。
【5 3 2 4 6】 void shellSort(int arr[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j; 这里就是插入排序 需要把i插入到前边的组里。 for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本人2022年毕业于山东大学,目前就职国内某芯片厂。打算把之前校招时做的笔记通过专栏发出来,本专栏适合于C/C++、嵌入式方向就业的同学,本篇面经总结数千篇面经的知识集合,实时更新全网最新的嵌入式/C++最新内容,囊括了C语言、C++、操作系统、计算机网络、嵌入式、算法与数据结构、数据库等一系列知识点,在我看来这些是求职者在面试中必须掌握的知识点。最后呢祝各位能找到自己合适的工作。