学习嵌入式Day7：C语言之排序算法和字符型数组

上一篇写到一维数组今天接着展开。一、冒泡排序算法相邻两个元素比较小的放在前大的放在后最终实现升序排序。#include stdio.h int main(void) { int a[10] {}; int len sizeof(a)/sizeof(a[0]); int i 0; printf(input 10 numbers:); for(i 0; i len; i) { scanf(%d, a[i]); } i 0; int j 0; //确定需要比较几位 for(i 1; i len; i) { //从第一位开始逐位与相邻元素进行比较 for(j 0; j len-i; j) { //a[j]比a[j1]大则交换 int t 0; if (a[j] a[j1]) { t a[j]; a[j] a[j1]; a[j1] t; } } } for(i 0; i len; i) { printf(a[%d] %d\n,i, a[i]); } return 0; }二、插入排序在一个有序的数列中找到合适位置插入排序的数。非原地插入排序#include stdio.h int main(void) { int a[10] {}; int b[10] {}; int len sizeof(a)/sizeof(a[0]); int i 0; printf(input 10 numbers:); for(i 0; i len; i) { scanf(%d, a[i]); } int t 0; int j 0; //确定插入的数 for (i 0; i len; i) { t a[i];//取数 j i;//准备放的位置 //依次与已经排列好的有序数列的数比较 while (j 0 b[j-1] t) { //如果比前一位数小则交换 b[j] b[j-1]; --j; } //找到合适的位置插入 b[j] t; } for(i 0; i 10; i) { printf(a[%d] %d\n, i, b[i]); } return 0; }这种插入排序占用的内存多空间复杂度较高。可以有优化成下面的这种排序原地插入排序只展示关键算法int t 0; int j 0; for (i 0; i len; i) { t a[i];//取数 j i;//准备放的位置 //依次与已经排列好的有序数列的数比较 while (j 0 a[j-1] t) { //如果比前一位数小则交换 a[j] a[j-1]; --j; } //找到合适的位置插入 a[j] t; }三、算法比较如何判断算法好坏时间复杂度衡量算法随着问题规模变化所需时间的趋势。分为最好、最坏和平均一般看最坏的时间复杂度。大O计算法//冒泡排序 for(i 1; i len; i) { for(j 0; j len-i; j) { int t 0; if (a[j] a[j1]) { t a[j]; a[j] a[j1]; a[j1] t; } } } //选择排序 for (i 0; i len-1 ; i) { for (j i1; j len; j) { if (a[j] a[i]) { int t a[j]; a[j] a[i]; a[i] t; } } } //插入排序 for (i 0; i len; i) { t a[i]; j i; while (j 0 b[j-1] t) { b[j] b[j-1]; --j; } b[j] t; }选择排序、冒泡排序和插入排序的算法复杂度都是O(n^2)。四、二分查找排序的目的就是方便查找。二分查找的前提数据本身是有序的。思路首先确认中间位置将中间位置上的值与要查找的值比较若要查找的值更大则在后面的位置继续二分查找若要查找的值较小则在前面的位置继续二分查找若相等则直接输出。#include stdio.h int main(void) { int a[10] {}; int n; int len sizeof(a)/sizeof(a[0]); int i 0; printf(input 10 numbers:); for(i 0; i len; i) { scanf(%d, a[i]); } int t 0; int j 0; //确定插入的数 for (i 0; i len; i) { t a[i];//取数 j i;//准备放的位置 //依次与已经排列好的有序数列的数比较 while (j 0 a[j-1] t) { //如果比前一位数小则交换 a[j] a[j-1]; --j; } //找到合适的位置插入 a[j] t; } printf(input a number:); scanf(%d, n); int mid; int begin 0; int end len - 1; while(begin end) { //计算中间值 mid (begin end)/2; //要查找的值比中间值大 if (n a[mid]) { //到中间的后段继续查找 begin mid1; } //要查找的值比中间值小 else if (n a[mid]) { //到中间的前段继续查找 end mid-1; } //相等直接跳出循环 else { break; } } //如果begin大于end说明没有找到值输出not found if (begin end) { printf(HAS BEEN FOUND\n); }else { printf(NOT FOUND\n); } return 0; }五、字符型一维数组定义char str[];初始化char str[10] {h,e,l,l,o};hello 从字符数组的角度看字符串字符串是一种特殊的字符数组 (始终以\0作为结束标志)//数组 char str[10] {h,e,l,l,o,5,6,7,8,9}; //全部初始化 char str[10] {h,e,l,l,o}; //部分初始化因为后面有0所以可以当作字符串 char str[10] {0}; //初始化为 0 char str[10] {}; char str[10]; //不初始化 ---随机值 char str[] {h,e,l,l,o,5,6,7,8,9}; //字符串 char str[10] hello; //hello 字符串常量 char str[10] {hello}; char str[10] {h,e,l,l,o,\0}; //放了一个字符串 char str[] hello; //h,e,l,l,o,\0字符型数组可以用来存放字符串。C语言中将字符串当成字符型数组来处理。字符串是以\0结尾的操作字符串时更关注的是字符串本身什么时候结束而不是数组。代码中处理字符串是以\0作为结束判断的标志。puts/gets函数getschar *gets(char *s);功能:从标准输入获得字符串参数:s可以传一个 字符型一维数组的数组名。数组名从所代表的值角度代表的是数组首元素的地址也是数组的起始地址。返回值:成功 返回s失败 NULL注意:不推荐使用因为很容易导致数组越界。putsint puts(const char *s);功能:将s所在空间上的字符串输出参数:s表示存放字符串的一块空间的其实地址返回值:成功 返回非负数失败 -1六、总结今天学习了冒泡排序和插入排序算法加上昨天的选择排序算法一共三种排序算法。这三种算法是这两天的重点需要熟练掌握笔试面试要求能手写代码。冒泡相邻两两比较交换一趟把最大值 “浮” 到末尾选择每一轮选定位置在后面找到合适元素放到当前位置插入维护有序区把新元素插入有序区对应位置