spider 01-min.png

Richard Stevens所著的《UNIX® Network Programming Volume 1, Third Edition: The Sockets Networking》一书中,6.2章节"IO Models"列出了五种IO模型,本文将详细介绍这几种IO模型,并说明阻塞(blocking)和非阻塞(non-blocking)的区别、同步(synchronous)和异步(asynchronous)的区别

作者头像
Madman

归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法,它将已经有序的子序列合并,得到完全有序的序列。也就是说,先使每个子序列有序(单个元素组成的序列肯定是有序的),再将两个有序序列合并成一个更大的有序序列。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,将复杂的问题分解成容易解决的小问题,比如将两个只有一个元素的左右子序列排序合并很简单,再一层层合并成更大的有序序列

作者头像
Madman

希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布。希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)

作者头像
Madman

插入排序是一种简单直观的排序算法,它的工作原理非常类似于我们抓扑克牌,对于未排序数据(右手抓到的牌),在已排序序列(左手已经排好序的手牌)中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place sorting,即只需用到 O(1) 的额外空间的排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间