由Inria Flower实验室(位于法国波尔多)研究小组创建的 Poppy,是一台经济实惠、易于安装的人形机器人,拥有强大而灵活的硬件配置。使用现成部件(电机及电子元件)和 3D打印的肢体,降低创客自制门槛。
快速排序算法(QSort,快排)及C语言实现
上节介绍了如何使用起泡排序的思想对无序表中的记录按照一定的规则进行排序,本节再介绍一种排序算法——快速排序算法(Quick Sort)。
C语言中自带函数库中就有快速排序——qsort函数 ,包含在 <stdlib.h> 头文件中。
快速排序算法是在起泡排序的基础上进行改进的一种算法,其实现的基本思想是:通过一次排序将整个无序表分成相互独立的两部分,其中一部分中的数据都比另一部分中包含的数据的值小,然后继续沿用此方法分别对两部分进行同样的操作,直到每一个小部分不可再分,所得到的整个序列就成为了有序序列。
例如,对无序表{49,38,65,97,76,13,27,49}进行快速排序,大致过程为:
- 首先从表中选取一个记录的关键字作为分割点(称为“枢轴”或者支点,一般选择第一个关键字),例如选取 49;
- 将表格中大于 49 个放置于 49 的右侧,小于 49 的放置于 49 的左侧,假设完成后的无序表为:
{27,38,13,49,65,97,76,49}; - 以 49 为支点,将整个无序表分割成了两个部分,分别为
{27,38,13}和{65,97,76,49},继续采用此种方法分别对两个子表进行排序; - 前部分子表以 27 为支点,排序后的子表为
{13,27,38},此部分已经有序;后部分子表以 65 为支点,排序后的子表为{49,65,97,76}; - 此时前半部分子表中的数据已完成排序;后部分子表继续以 65为支点,将其分割为
{49}和{97,76},前者不需排序,后者排序后的结果为{76,97}; - 通过以上几步的排序,最后由子表
{13,27,38}、{49}、{49}、{65}、{76,97}构成有序表:{13,27,38,49,49,65,76,97};
整个过程中最重要的是实现第 2 步的分割操作,具体实现过程为:
- 设置两个指针 low 和 high,分别指向无序表的表头和表尾,如下图所示:

- 先由 high 指针从右往左依次遍历,直到找到一个比 49 小的关键字,所以 high 指针走到 27 的地方停止。找到之后将该关键字同 low 指向的关键字进行互换:

- 然后指针 low 从左往右依次遍历,直到找到一个比 49 大的关键字为止,所以 low 指针走到 65 的地方停止。同样找到后同 high 指向的关键字进行互换:

- 指针 high 继续左移,到 13 所在的位置停止(13<49),然后同 low 指向的关键字进行互换:

- 指针 low 继续右移,到 97 所在的位置停止(97>49),然后同 high 指向的关键字互换位置:

- 指针 high 继续左移,此时两指针相遇,整个过程结束;
该操作过程的具体实现代码为:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#define MAX 8 typedef struct { int key; }SqNote; typedef struct { SqNote r[MAX]; int length; }SqList; //交换两个记录的位置 void swap(SqNote *a,SqNote *b){ int key=a->key; a->key=b->key; b->key=key; } //快速排序,分割的过程 int Partition(SqList *L,int low,int high){ int pivotkey=L->r[low].key; //直到两指针相遇,程序结束 while (low<high) { //high指针左移,直至遇到比pivotkey值小的记录,指针停止移动 while (low<high && L->r[high].key>=pivotkey) { high--; } //交换两指针指向的记录 swap(&(L->r[low]), &(L->r[high])); //low 指针右移,直至遇到比pivotkey值大的记录,指针停止移动 while (low<high && L->r[low].key<=pivotkey) { low++; } //交换两指针指向的记录 swap(&(L->r[low]), &(L->r[high])); } return low; } |
该方法其实还有可以改进的地方:在上边实现分割的过程中,每次交换都将支点记录的值进行移动,而实际上只需在整个过程结束后(low==high),两指针指向的位置就是支点记录的准确位置,所以无需每次都移动支点的位置,最后移动至正确的位置即可。
所以上边的算法还可以改写为:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//此方法中,存储记录的数组中,下标为 0 的位置时空着的,不放任何记录,记录从下标为 1 处开始依次存放 int Partition(SqList *L,int low,int high){ L->r[0]=L->r[low]; int pivotkey=L->r[low].key; //直到两指针相遇,程序结束 while (low<high) { //high指针左移,直至遇到比pivotkey值小的记录,指针停止移动 while (low<high && L->r[high].key>=pivotkey) { high--; } //直接将high指向的小于支点的记录移动到low指针的位置。 L->r[low]=L->r[high]; //low 指针右移,直至遇到比pivotkey值大的记录,指针停止移动 while (low<high && L->r[low].key<=pivotkey) { low++; } //直接将low指向的大于支点的记录移动到high指针的位置 L->r[high]=L->r[low]; } //将支点添加到准确的位置 L->r[low]=L->r[0]; return low; } |
快速排序的完整实现代码(C语言)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <stdio.h> #include <stdlib.h> #define MAX 9 //单个记录的结构体 typedef struct { int key; }SqNote; //记录表的结构体 typedef struct { SqNote r[MAX]; int length; }SqList; //此方法中,存储记录的数组中,下标为 0 的位置时空着的,不放任何记录,记录从下标为 1 处开始依次存放 int Partition(SqList *L,int low,int high){ L->r[0]=L->r[low]; int pivotkey=L->r[low].key; //直到两指针相遇,程序结束 while (low<high) { //high指针左移,直至遇到比pivotkey值小的记录,指针停止移动 while (low<high && L->r[high].key>=pivotkey) { high--; } //直接将high指向的小于支点的记录移动到low指针的位置。 L->r[low]=L->r[high]; //low 指针右移,直至遇到比pivotkey值大的记录,指针停止移动 while (low<high && L->r[low].key<=pivotkey) { low++; } //直接将low指向的大于支点的记录移动到high指针的位置 L->r[high]=L->r[low]; } //将支点添加到准确的位置 L->r[low]=L->r[0]; return low; } void QSort(SqList *L,int low,int high){ if (low<high) { //找到支点的位置 int pivotloc=Partition(L, low, high); //对支点左侧的子表进行排序 QSort(L, low, pivotloc-1); //对支点右侧的子表进行排序 QSort(L, pivotloc+1, high); } } void QuickSort(SqList *L){ QSort(L, 1,L->length); } int main() { SqList * L=(SqList*)malloc(sizeof(SqList)); L->length=8; L->r[1].key=49; L->r[2].key=38; L->r[3].key=65; L->r[4].key=97; L->r[5].key=76; L->r[6].key=13; L->r[7].key=27; L->r[8].key=49; QuickSort(L); for (int i=1; i<=L->length; i++) { printf("%d ",L->r[i].key); } return 0; } |
运行结果:
|
1 |
13 27 38 49 49 65 76 97 |
总结
快速排序算法的时间复杂度为O(nlogn),是所有时间复杂度相同的排序方法中性能最好的排序算法。
参考链接
I2C总线协议图解
I2C 总线在物理连接上非常简单,分别由SDA(串行数据线)和SCL(串行时钟线)及上拉电阻组成。通信原理是通过对SCL和SDA线高低电平时序的控制,来产生I2C总线协议所需要的信号进行数据的传递。在总线空闲状态时,这两根线一般被上面所接的上拉电阻拉高,保持着高电平。
I2C通信方式为半双工,只有一根SDA线,同一时间只可以单向通信,RS485也为半双工,SPI和UART为双工。
ubuntu 18.04启动samba图形管理界面
|
1 2 3 4 5 6 7 8 9 |
$ sudo apt-get install samba $ sudo apt-get install system-config-samba $ sudo apt-get install libcanberra-gtk-module $ sudo touch /etc/libuser.conf $ sudo system-config-samba |
参考链接
ubuntu 18.04 systemd-udevd进程CPU占用特别高,禁用WiFi可以解决
继续阅读ubuntu 18.04 systemd-udevd进程CPU占用特别高,禁用WiFi可以解决
VirtualBox 6.0中Windows XP系统配置virtio驱动
VirtualBox 6.0 下已经支持 准虚拟化网络(virtio-net) 驱动,这个可以提供更高的网络性能。
继续阅读VirtualBox 6.0中Windows XP系统配置virtio驱动
ubuntu 16.04/18.04/20.04/21.10配置远程桌面访问
远程桌面在 Linux 中一般使用 VNC ,下面我们总结一下 ubuntu 16.04/18.04 下的配置总结:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
$ sudo apt-get update # ubuntu 18.04/20.04 默认使用gdm3,导致VNC工作异常,需要切换到 lightdm # ubuntu 16.04 默认使用 lightdm 因此一般不需要调整 $ sudo apt install lightdm # 配置切换到 lightdm $ sudo dpkg-reconfigure gdm3 $ sudo apt install xserver-xorg-video-dummy # 如果从 gdm3 切换到 lightdm 需要重启系统,否则不能正常工作 $ sudo reboot $ sudo apt-get install x11vnc # ubuntu 20.04 # sudo apt-get install net-tools # 设置登录密码,如果不设置密码,会导致任意人都可以登录 $ sudo x11vnc -storepasswd /etc/x11vnc.pass # 需要手工设置一下权限,默认设置的权限可能会导致其他用户无法正常读取 $ sudo chmod 755 /etc/x11vnc.pass # '-rfbport' 参数指定监听端口,'-forever' 参数指定客户端断开后不要停止服务而是继续等待下一次的连接请求 '-rfbauth' 参数指定验证密码的存储文件 $ sudo x11vnc -auth guess -rfbauth /etc/x11vnc.pass -rfbport 5900 -forever -display :0 |
设置开机启动
|
1 2 3 |
$ sudo apt-get install vim $ sudo vim /etc/systemd/system/x11vnc.service |
里面内容如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
[Unit] Description=x11vnc (Remote access) After=network-online.target [Service] Type=simple ExecStart=/usr/bin/x11vnc -auth guess -rfbauth /etc/x11vnc.pass -rfbport 5900 -forever -display :0 ExecStop=/bin/kill -TERM $MAINPID ExecReload=/bin/kill -HUP $MAINPID KillMode=control-group Restart=on-failure [Install] WantedBy=graphical.target |
配置 systemd 启用服务
|
1 2 3 4 5 |
$ sudo systemctl daemon-reload $ sudo systemctl enable x11vnc $ sudo systemctl start x11vnc |
如果登录之后,只出现一个桌面背景,没有任何菜单,如下:

参考 Intel NUC(NUC6i3SYH)在不接显示器的情况下VNC不显示桌面(Ubuntu 18.04) 解决,网上搜索相关问题的时候可以使用关键词 HEADLESS X11 查找解决方案,其实就是不插入显示器的情况下,如何强制显卡渲染。
如果系统是 ubuntu 21.10 版本,则需要编辑
|
1 2 3 |
# ubuntu 21.10 版本配置文件 $ sudo vim /etc/X11/xorg.conf |
然后在文件尾部,增加如下配置:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Section "Device" Identifier "Configured Video Device" Driver "dummy" EndSection Section "Monitor" Identifier "Configured Monitor" HorizSync 31.5-48.5 VertRefresh 50-70 EndSection Section "Screen" Identifier "Default Screen" Monitor "Configured Monitor" Device "Configured Video Device" DefaultDepth 24 SubSection "Display" Depth 24 Modes "1920x1080" EndSubSection EndSection |
完成后,重启系统。
注意:如果系统上使用 nvidia 显卡,需要首先通过 nvidia-xconfig 生成默认配置,如果没有默认配置,会导致 nvidia-smi 找不到显卡,一些使用显卡的计算任务或者机器学习框架会出现问题。
参考命令如下:
|
1 |
$ sudo nvidia-xconfig -a --virtual=1920x1200 |
可能会生成类似如下配置内容:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
# nvidia-xconfig: X configuration file generated by nvidia-xconfig # nvidia-xconfig: version 495.44 Section "ServerLayout" Identifier "Default Layout" Screen 0 "Screen0" InputDevice "Keyboard0" "CoreKeyboard" InputDevice "Mouse0" "CorePointer" EndSection Section "InputDevice" # generated from default Identifier "Keyboard0" Driver "kbd" EndSection Section "InputDevice" # generated from default Identifier "Mouse0" Driver "mouse" Option "Protocol" "auto" Option "Device" "/dev/psaux" Option "Emulate3Buttons" "no" Option "ZAxisMapping" "4 5" EndSection Section "Monitor" Identifier "Monitor0" VendorName "Unknown" ModelName "Unknown" Option "DPMS" EndSection Section "Device" Identifier "Device0" Driver "nvidia" VendorName "NVIDIA Corporation" BoardName "NVIDIA GeForce RTX 3060" EndSection Section "Screen" Identifier "Screen0" Device "Device0" Monitor "Monitor0" DefaultDepth 24 SubSection "Display" Virtual 1920 1200 Depth 24 EndSubSection EndSection |
然后在配置文件的尾部增加
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Section "Device" Identifier "Configured Video Device" Driver "dummy" EndSection Section "Monitor" Identifier "Configured Monitor" HorizSync 31.5-48.5 VertRefresh 50-70 EndSection Section "Screen" Identifier "Default Screen" Monitor "Configured Monitor" Device "Configured Video Device" DefaultDepth 24 SubSection "Display" Depth 24 Virtual 1920 1200 Modes "1920x1200" EndSubSection EndSection |
最后修改 Section "ServerLayout" 字段里的 Screen 0 为新增的屏幕(Section "Screen" 字段中的 Identifier定义的名字)。
修改参考如下:
|
1 2 3 4 5 6 |
Section "ServerLayout" Identifier "Default Layout" Screen 0 "Default Screen" InputDevice "Keyboard0" "CoreKeyboard" InputDevice "Mouse0" "CorePointer" EndSection |
修改后的完整内如如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
# nvidia-xconfig: X configuration file generated by nvidia-xconfig # nvidia-xconfig: version 495.44 Section "ServerLayout" Identifier "Default Layout" Screen 0 "Default Screen" InputDevice "Keyboard0" "CoreKeyboard" InputDevice "Mouse0" "CorePointer" EndSection Section "InputDevice" # generated from default Identifier "Keyboard0" Driver "kbd" EndSection Section "InputDevice" # generated from default Identifier "Mouse0" Driver "mouse" Option "Protocol" "auto" Option "Device" "/dev/psaux" Option "Emulate3Buttons" "no" Option "ZAxisMapping" "4 5" EndSection Section "Monitor" Identifier "Monitor0" VendorName "Unknown" ModelName "Unknown" Option "DPMS" EndSection Section "Device" Identifier "Device0" Driver "nvidia" VendorName "NVIDIA Corporation" BoardName "NVIDIA GeForce RTX 3060" EndSection Section "Screen" Identifier "Screen0" Device "Device0" Monitor "Monitor0" DefaultDepth 24 SubSection "Display" Virtual 1920 1200 Depth 24 EndSubSection EndSection Section "Device" Identifier "Configured Video Device" Driver "dummy" EndSection Section "Monitor" Identifier "Configured Monitor" HorizSync 31.5-48.5 VertRefresh 50-70 EndSection Section "Screen" Identifier "Default Screen" Monitor "Configured Monitor" Device "Configured Video Device" DefaultDepth 24 SubSection "Display" Depth 24 Virtual 1920 1200 Modes "1920x1200" EndSubSection EndSection |
尽管经过上面的设置,可以正确使用 VNC ,但是更推荐使用 RDP 协议,功能更丰富,性能更高,安全性更好。参考 VNC 还是 RDP? 云上的远程桌面究竟该如何选。
参考链接
Chrome浏览器出现“由贵单位管理”原因及解决去除方法
最近有很多 Chrome 浏览器用户突然发现设置选项提示“由贵单位管理”,并且还可能在操作中心里弹出这个通知,或者在“下载”页面中出现“您的浏览器由所属组织管理”,或者在“关于 Google Chrome(G)”页面中出现“您的浏览器受管理”。
如果是企业用户遇到这个通知可能还能理解但不少个人用户也遇到这种情况,使用的并非谷歌浏览器企业版。
macOS上使用Openconnect代替Cisco Anyconnect
OpenConnect 是一个 Cisco Anyconnect 的替代品,具有开源、易获取、可靠等优点。而官方版本的 Cisco Anyconnect 配置较为繁琐,需要在管理界面同时部署多平台客户端才能支持多平台。相比之下 OpenConnect 在这点就具有优势,可以在官方版本无法跨平台时替代使用。
命令行模式:
|
1 2 3 4 |
$ brew install openconnect # 用法示例如下 $url 服务器的域名 $username用户名认证时候的用户名 $ sudo openconnect $url --protocol=anyconnect --user $username |
GUI 界面模式:
|
1 |
$ brew cask install openconnect-gui |
使用起来是非常简单的。
注意:对于OS X EI Caption来说(Mac mini(Early 2009)已经不能升级系统了),由于openconnect-gui需要QT 5.8以上的版本,而HomeBrew已经不支持这个版本的系统,因此,安装的openconnect-gui之后,运行的时候进程会崩溃。
上面的情况,一般建议使用命令行版本进行操作。
参考链接
MAC修改主机名/计算机名
|
1 |
$ sudo scutil --set HostName longskys-MBP |
继续阅读MAC修改主机名/计算机名