Oct 26
Unix(包含Linux)的初学者,常常会很困惑,不明白目录结构的含义何在。
点击在新窗口中浏览此图片
举例来说,根目录下面有一个子目录/bin,用于存放二进制程序。但是,/usr子目录下面还有/usr/bin,以及/usr/local/bin,也用于存放二进制程序;某些系统甚至还有/opt/bin。它们有何区别?
长久以来,我也感到很费解,不明白为什么这样设计。像大多数人一样,我只是根据《Unix文件系统结构标准》(Filesystem Hierarchy Standard),死记硬背不同目录的区别。
昨天,我读到了Rob Landley的简短解释,这才恍然大悟,原来Unix目录结构是历史造成的。
话说1969年,Ken Thompson和Dennis Ritchie在小型机PDP-7上发明了Unix。1971年,他们将主机升级到了PDP-11。
点击在新窗口中浏览此图片

当时,他们使用一种叫做RK05的储存盘,一盘的容量大约是1.5MB。
点击在新窗口中浏览此图片

没过多久,操作系统(根目录)变得越来越大,一块盘已经装不下了。于是,他们加上了第二盘RK05,并且规定第一块盘专门放系统程序,第二块盘专门放用户自己的程序,因此挂载的目录点取名为/usr。也就是说,根目录"/"挂载在第一块盘,"/usr"目录挂载在第二块盘。除此之外,两块盘的目录结构完全相同,第一块盘的目录(/bin, /sbin, /lib, /tmp...)都在/usr目录下重新出现一次。
后来,第二块盘也满了,他们只好又加了第三盘RK05,挂载的目录点取名为/home,并且规定/usr用于存放用户的程序,/home用于存放用户的数据。
从此,这种目录结构就延续了下来。随着硬盘容量越来越大,各个目录的含义进一步得到明确。
  /:存放系统程序,也就是At&t开发的Unix程序。
  /usr:存放Unix系统商(比如IBM和HP)开发的程序。
  /usr/local:存放用户自己安装的程序。
  /opt:在某些系统,用于存放第三方厂商开发的程序,所以取名为option,意为"选装"。


《Unix文件系统结构标准》 : http://www.pathname.com/fhs/pub/fhs-2.3.html
Understanding the bin, sbin, usr/bin , usr/sbin split: http://lists.busybox.net/pipermail/busybox/2010-December/074114.html
Oct 26


你是否对你喜爱的 Linux 发行版的最新发布版本的代号感到好奇?

比如说今年发布的 Linux Mint 18 的代号是 Sarah,而 Ubuntu 16.10 则叫做 Yakkety Yak,这样的名字还有很多很多。

代号这个问题真不是一个大事,毕竟这些代号不能代表不同的发行版功能之间的不同。然而,对于一个好奇的 Linux 用户来说,你或许想知道每个发行版本代号背后的逻辑。不管怎么说,代号都是每个版本不可分割的一部分,而开发团队也为此付出了不少的努力,对吧?

下面我将会告诉你这些最流行的 Linux 发行版的代号背后的故事,请安坐,有趣的部分即将来到 :)

Ubuntu 的版本号和代号

作为最流行的 Linux 发行版之一,Ubuntu[1] 有着一个稳定的开发周期,每年 4 月份和 10 月份各发布一个主要版本。

其所发布的年份和月份构成了 Ubuntu 发布版本的版本号。它的版本号格式是 XX.YY,其中 XX 是年份后两位,YY 是月份。比如说 Ubuntu 16.04 就是 2016 年 4 月份发布的版本,而 Ubuntu 16.10 则是该年 10 月份发布的。之所以 Ubuntu 没有像其它软件一样有 1.0 版本,也只是因为其第一个版本是发布于 2004 年[2]而已。

这么久以来,在过去的 11 年之中, 除了一次例外之外,Ubuntu 的所有版本都是 4 月份和 10 月份发布的。这唯一的一次例外是 Ubuntu 在 2006 年 4 月份的版本延迟了两个月,并因此其版本号叫做  Ubuntu 6.06,而不是 6.04。

另外,顺便提一句,每两年的 4 月份,都会推出一个长期支持版本(LTS),其支持期长达五年,而非 LTS 版本的支持期通常只有半年。

现在让我们看看 Ubuntu 的代号,你也许注意到了每个 Ubuntu 版本的代号都是两个相同首字母的单词,比如说, Ubuntu 14.04 叫做 Trusty Tahr,就是以两个“T”字母开头的。

Ubuntu 的代号一直遵循两个单词的规则,第一个是一个形容词,第二个则是一种濒危物种的名称(后来也包含一些传说生物,比如独角兽Unicorn、狼人Werewolf)。在前面的例子中,Trusty 是一个表示“忠实的”的形容词,而 Tahr[3] (塔尔羊)则是一种濒危的小物种动物。

另外一个有趣的事情是,这些字母的顺序是按字母表排列的(除了最开始时的两个),所以我们看到,Ubuntu 14.04 是 Trusty Tahr, Ubuntu 14.10 是 Utopic Unicorn, Ubuntu 15.04 是 Vivid Vervet ,明年即将发布的 Ubuntu 17.04 则是 Zesty Zapus 等等。至于再之后的版本,字母“Z”之后该用哪个,目前还没有得到 Canonical 官方的消息,我猜测或许是将没有用过的 A 和 C 用上,或许是从头开始循环,抑或是其它的可能也未尝可知。

如下是当前的 Ubuntu 的版本号和代号:

版本号代号发布日期支持期
桌面版服务器版
4.10Warty Warthog2004-10-202006-04-30
5.04Hoary Hedgehog2005-04-082006-10-31
5.10Breezy Badger2005-10-132007-04-13
6.06 LTSDapper Drake2006-06-012009-07-142011-06-01
6.10Edgy Eft2006-10-262008-04-25
7.04Feisty Fawn2007-04-192008-10-19
7.10Gutsy Gibbon2007-10-182009-04-18
8.04 LTSHardy Heron2008-04-242011-05-122013-05-09
8.10Intrepid Ibex2008-10-302010-04-30
9.04Jaunty Jackalope2009-04-232010-10-23
9.10Karmic Koala2009-10-292011-04-30
10.04 LTSLucid Lynx2010-04-292013-05-092015-04-30
10.10Maverick Meerkat2010-10-102012-04-10
11.04Natty Narwhal2011-04-282012-10-28
11.10Oneiric Ocelot2011-10-132013-05-09
12.04 LTSPrecise Pangolin2012-04-262017-04-26
12.10Quantal Quetzal2012-10-182014-05-16
13.04Raring Ringtail2013-04-252014-01-27
13.10Saucy Salamander2013-10-172014-07-17
14.04 LTSTrusty Tahr2014-04-172019-04
14.10Utopic Unicorn2014-10-232015-07-23
15.04Vivid Vervet2015-04-232016-02-04
15.10Wily Werewolf2015-10-222016-07-28
16.04 LTSXenial Xerus2016-04-212021-04
16.10Yakkety Yak2016-10-132017-07
17.04Zesty ZapusTBATBA

(表格来自维基百科[4])Ubuntu 每次发布新版本都能扩充我们的英语词汇,也会让我们了解一种世界上需要关注的的濒危动物。

Linux Mint 的版本号和代号

作为 Ubuntu 的远亲,Linux Mint 也是一个 Debian 族系的流行发行版。现在让我们深挖一下 Linux Mint 的版本号和代号。

Linux Mint 是基于 Ubuntu 的,通常在 Ubuntu 发布后几个月内,Linux Mint 就会发布它基于 Ubuntu 衍生的版本。

但是不像 Ubuntu,Linut Mint 的版本号并没有遵循年和月的规则,只是简单的递增。所以 Linux Mint 15 之后就是 Linux Mint 16,Linux Mint 17 等等。这是主要版本,还会有维护的小版本,比如 Linux Mint 17.1、Linux Mint 17.2 等等。

这就是 Linux Mint 的版本号,现在让我们看看代号。每个 Linux Mint 版本,无论是主要版本还是维护版本,都有一个代号,而且和 Ubuntu 一样,都是按字母顺序递增的。

更有意思的一点是 Linux Mint 的代号都是女性名,而且以字母“a”结尾,而这些名字都来自于亚伯拉罕诸教[5]。比如说 Linux Mint 17 的代号是 Qiana(国内戏称“钱啊”,其实发言应该是“奎阿纳”)。

主要版本会递增代号的首字母顺序,而通常维护版本会使用相同的首字母,不过在 Linux Mint 17.x 发生了变化,没有继续使用 Linux Mint 17 的“Q”,而是使用了“R”:Linux Mint 17.1 是 Rebecca, 17.2 是 Rafaela,17.3 是 Rosa。

如下是当前的 Linux Mint 的版本号和代号:

版本代号分支上游发布日期支持期
1.0AdaMainKubuntu 6.062006-08-27未知
2.0BarbaraMainUbuntu 6.102006-11-132008-04
2.1BeaMainUbuntu 6.102006-12-202008-04
2.2BiancaMainUbuntu 6.102007-02-202008-04
LightUbuntu 6.102007-03-29
KDE CEKubuntu 6.102007-04-20
3.0CassandraMainBianca 2.22007-05-302008-10
LightBianca 2.22007-06-15
KDE CEBianca 2.22007-08-14
MiniKDE CEBianca 2.22007-08-14
Xfce CECassandra 3.02007-08-07
3.1CelenaMainBianca 2.22007-09-242008-10
LightBianca 2.22007-10-01
4.0DarynaMainCelena 3.12007-10-152009-04
LightCelena 3.12007-10-15
KDE CECassandra 3.02008-03-03
5ElyssaMainDaryna 4.02008-06-082011-04
LightDaryna 4.02008-06-08
x64Ubuntu 8.042008-10-18
KDE CEDaryna 4.02008-09-15
Xfce CEDaryna 4.02008-09-08
Fluxbox CEUbuntu 8.042008-10-21
6FeliciaMainUbuntu 8.102008-12-152010-04
Universal (Light)Ubuntu 8.102008-12-15
x64Ubuntu 8.102009-02-06
KDE CEElyssa 52009-04-08
Xfce CEXubuntu 8.102009-02-24
Fluxbox CEXubuntu 8.102009-04-07
7GloriaMainUbuntu 9.042009-05-262010-10
Universal (Light)Ubuntu 9.042009-05-26
x64Ubuntu 9.042009-06-24
KDE CEKubuntu 9.042009-08-03
Xfce CEXubuntu 9.042009-08-13
8HelenaMainUbuntu 9.102009-11-282011-04
Universal (Light)Ubuntu 9.102009-11-28
Gnome x64Ubuntu 9.102009-12-14
KDEKubuntu 9.102010-02-06
KDE x64Kubuntu 9.102010-02-12
FluxboxHelena Main2010-02-12
XfceXubuntu 9.102010-03-31
LXDEHelena Main2010-03-31
9IsadoraMainUbuntu 10.042010-05-182013-04
Gnome x64Ubuntu 10.042010-05-18
LXDELubuntu 10.042010-07-18
KDEKubuntu 10.042010-07-27
KDE x64Kubuntu 10.042010-07-27
XfceXubuntu 10.042010-08-24
FluxboxLubuntu 10.042010-09-06
10JuliaMainUbuntu 10.102010-11-122012-04
Gnome x64Ubuntu 10.102010-11-12
KDEKubuntu 10.102011-02-23
KDE x64Kubuntu 10.102011-02-23
LXDELubuntu 10.102011-03-11
11KatyaMainUbuntu 11.042011-05-262012-10
Gnome x64Ubuntu 11.042011-05-26
LXDELubuntu 11.042011-08-16
12LisaMainUbuntu 11.102011-11-262013-04
KDEKubuntu 11.102012-02-02
LXDELubuntu 11.102012-03-09
13MayaMainUbuntu 12.042012-05-222017-04
XfceXubuntu 12.042012-07-21
KDEKubuntu 12.042012-07-23
14NadiaMainUbuntu 12.102012-11-202014-05
XfceXubuntu 12.102012-12-21
KDEKubuntu 12.102012-12-23
15OliviaMainUbuntu 13.042013-05-292014-01
Xfce2013-07-12
KDE2013-07-21
16PetraMainUbuntu 13.102013-11-302014-07
KDE2013-12-22
Xfce2013-12-22
17QianaMainUbuntu 14.042014-05-312019-04
KDE2014-06-23
Xfce2014-06-15
17.1RebeccaMain2014-11-29
KDE2015-01-08
Xfce2015-01-11
17.2RafaelaMain2015-06-30
KDE2015-07-23
Xfce2015-07-23
17.3RosaMain2015-12-04
KDE2016-01-09
Xfce2016-01-09
18SarahMainUbuntu 16.042016-06-302021

不过,Sarah 是上述列表中唯一不以“a”结尾的代号,可能是因为没有合适的名称。

elementary OS 的版本号和代号

因为我们谈过了 Ubuntu 和 Linux Mint,让我们继续看看 Ubuntu 家族的另外一位: elementary OS[6] ,它也是基于 Ubuntu 的一个以优美著称的 Linux 发行版。

elementary OS 的版本号都是 0.X 这样递增的,第一个稳定版本是 0.1,然后是 0.2,现在的稳定版本是 0.3——不知道什么时候可以变成 1.0。

开源软件界之前一直有个传统就是使用极其微小的版本,比如 0.1,0.01 这样的,直到作者或开发团队觉得已经非常成熟了,才有可能变成 1.0 这样的看起来正式一些的版本号。当然,也有的软件从未进化到 1.0 就消亡了。不过虽然是这种看起来像是测试版本的版本号,却往往并不代表其质量和功能不可靠。而现在也有一些软件开始飙版本号,比如 Chrome、Firefox 之类的,我觉得用不了几年,或许我们就会见到 xx 100 这样的软件了。

而 elementary OS 的代号则是采用神话中神的名字,通常这些来自于罗马神话或北欧神话中。比如现在已有的三个版本的代号是 Jupiter(罗马神话中的神王)、 Luna (月神,不是“撸哪” )、 Freya(北欧神话中的爱与美之女神,不过 0.3 之前的代号名是 ISIS ,后因避讳而改名),以及现在的 0.4 Loki(北欧神话中的火与恶之神)。

Debian 的版本号和代号

让我们回到 Ubuntu 、Linux Mint 和 elementary OS 的父系看看。Debian[7] 是 Ubuntu 及其族系派生的来源,它的代号命名非常有意思。事实上,Debian 这个发行版本身的名字就来源于其创始人 Ian 及其女朋友 Debra 的名词合写,虽然 Ian 已经去世,但是其名字却会随着 Debian 而长存。

Debian 的版本号是递增的,这并没什么特殊的,不过有趣的是所有的 Debian 发行版本的代号都来自于《玩具总动员[8]》这个动画片中的角色名。这就是你为什么看到 Debian 的代号是 Jessie[9]Woody[10] 这样的原因。

如下是当前的 Debian 的版本号和代号:

版本代号发布日期安全支持期长期支持期
1.1Buzz1996-06-17N/A
1.2Rex1996-12-12N/A
1.3Bo1997-06-05N/A
2.0Hamm1998-07-24N/A
2.1Slink1999-03-092000-10-30
2.2Potato2000-08-142003-06-30
3.0Woody2002-07-192006-03-30
3.1Sarge6 June 20052008-03-31
4.0Etch8 April 20072010-02-15
5.0Lenny14 February 20092012-02-06
6.0Squeeze6 February 20112014-07-192016-02-29
7Wheezy4 May 20132016-04-262018-05
8Jessie25–26 April 20152018-052020-04
9StretchTBATBATBA
10BusterTBATBATBA
11BullseyeTBATBATBA

我觉得动画片《玩具总动员》里面还有很多角色,所以我们不用担心不够用了。

openSUSE 的版本号和代号

openSUSE[11] 的第一个版本 10.2 发布于 2006 年。

SUSE 家族的 Linux 发行版的版本号相当的任性,包括发行版的名字也换来换去。最初,该发行版的名字叫做 S.u.S.E Linux,这个名字从 1994 年用到了 1998 年,后来改成了 SuSE Linux(把名字中的“.”去掉了),然后到了 2003 年的时候变成了 SUSE Linux Enterprise。在 2005 年的时候,Novell 公司宣布将 SUSE 专业版系列变为开源项目,由于当时 SUSE 的版本是 9.X,所以第一个 SUSE Linux 的版本是以 10.0 开始的。到 2006 年底的时候,再次决定改名为 openSUSE,第一个版本是 10.2。接下来将近十年倒是没再改名称,直到 2015 年 openSUSE 已经发展到 13.2 时,又又又改名成 openSUSE Leap,版本号嘛,好吧,就是这么任性,直接变成了 42.1(当然这个数字是说法的[12])。

SUSE 家族最初发布的 Linux 发行版是没有代号的,后来可能是受到了其它 Linux 发行版的启发,从 openSUSE 11.2 开始有了代号。由于 openSUSE 以绿色为代表色,所以它的代号也都是各种绿色色调。

如下是当前的 openSUSE 的版本号和代号:

名字版本代号发布日期生命周期
标准Evergreen/ Major
SUSE Linux10.0N/A2005-10-062007-11-30N/A
10.1N/A2006-05-112008-05-31N/A
openSUSE10.2N/A2006-12-072008-11-30N/A
10.3N/A2007-10-042009-10-31N/A
11.0N/A2008-06-192010-06-26N/A
11.1N/A2008-12-182011-01-142012-04-13
11.2Emerald2009-11-122011-05-122013-11
11.3Teal2010-07-152012-01-16N/A
11.4Celadon2011-03-102012-11-052015-07
12.1Asparagus2011-11-162013-05-15N/A
12.2Mantis2012-09-052014-01-15N/A
12.3Dartmouth2013-03-132015-01-01N/A
13.1Bottle2013-11-192016-012016-11
13.2Harlequin2014-11-04Q1 2017N/A
openSUSE Leap42.1Malachite2015-11-04Q2 2017N/A
42.2N/A2016-11-16Q2 2018N/A

可能你都从来没听说过这么多的绿色色调,或许你会担心 openSUSE 会把绿色都用完,不过我觉得不用担心,毕竟连灰色都有 15 种之多,何况绿色呢?


[1]: http://www.ubuntu.com/
[2]: https://lists.ubuntu.com/archives/ubuntu-announce/2004-October/000003.html
[3]: https://en.wikipedia.org/wiki/Tahr
[4]: https://en.wikipedia.org/wiki/Ubuntu_version_history
[5]: https://zh.wikipedia.org/wiki/%E4%BA%9E%E4%BC%AF%E6%8B%89%E7%BD%95%E8%AB%B8%E6%95%99
[6]: https://elementary.io/
[7]: https://www.debian.org/
[8]: https://zh.wikipedia.org/wiki/%E7%8E%A9%E5%85%B7%E6%80%BB%E5%8A%A8%E5%91%98
[9]: https://en.wikipedia.org/wiki/Jessie_(Toy_Story)
[10]: https://en.wikipedia.org/wiki/Sheriff_Woody
[11]: https://www.opensuse.org/
[12]: https://linux.cn/article-6533-1.html


Oct 15
1、插入排序

描述

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

代码实现

Python

def insert_sort(lists):

    # 插入排序

    count = len(lists)

    for i in range(1, count):

        key = lists[i]

        j = i - 1

        while j >= 0:

            if lists[j] > key:

                lists[j + 1] = lists[j]

                lists[j] = key

            j -= 1

    return lists


2、希尔排序

描述

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

代码实现

Python

def shell_sort(lists):

    # 希尔排序

    count = len(lists)

    step = 2

    group = count / step

    while group > 0:

        for i in range(0, group):

            j = i + group

            while j < count:

                k = j - group

                key = lists[j]

                while k >= 0:

                    if lists[k] > key:

                        lists[k + group] = lists[k]

                        lists[k] = key

                    k -= group

                j += group

        group /= step

    return lists


3、冒泡排序

描述

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

代码实现

Python

def bubble_sort(lists):

    # 冒泡排序

    count = len(lists)

    for i in range(0, count):

        for j in range(i + 1, count):

            if lists[i] > lists[j]:

                lists[i], lists[j] = lists[j], lists[i]

    return lists

4、快速排序

描述

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

代码实现

Python

def quick_sort(lists, left, right):

    # 快速排序

    if left >= right:

        return lists

    key = lists[left]

    low = left

    high = right

    while left < right:

        while left < right and lists[right] >= key:

            right -= 1

        lists[left] = lists[right]

        while left < right and lists[left] <= key:

            left += 1

        lists[right] = lists[left]

    lists[right] = key

    quick_sort(lists, low, left - 1)

    quick_sort(lists, left + 1, high)

    return lists

5、直接选择排序

描述

基本思想:第1趟,在待排序记录r1 ~ r[n]中选出最小的记录,将它与r1交换;第2趟,在待排序记录r2 ~ r[n]中选出最小的记录,将它与r2交换;以此类推,第i趟在待排序记录r[i] ~ r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

代码实现

Python

def select_sort(lists):

    # 选择排序

    count = len(lists)

    for i in range(0, count):

        min = i

        for j in range(i + 1, count):

            if lists[min] > lists[j]:

                min = j

        lists[min], lists[i] = lists[i], lists[min]

    return lists

6、堆排序

描述

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

代码实现

Python

def adjust_heap(lists, i, size):

    lchild = 2 * i + 1

    rchild = 2 * i + 2

    max = i

    if i < size / 2:

        if lchild < size and lists[lchild] > lists[max]:

            max = lchild

        if rchild < size and lists[rchild] > lists[max]:

            max = rchild

        if max != i:

            lists[max], lists[i] = lists[i], lists[max]

            adjust_heap(lists, max, size)



def build_heap(lists, size):

    for i in range(0, (size/2))[::-1]:

        adjust_heap(lists, i, size)



def heap_sort(lists):

    size = len(lists)

    build_heap(lists, size)

    for i in range(0, size)[::-1]:

        lists[0], lists[i] = lists[i], lists[0]

        adjust_heap(lists, 0, i)

7、归并排序

描述

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

代码实现

Python


def merge(left, right):

    i, j = 0, 0

    result = []

    while i < len(left) and j < len(right):

        if left[i] <= right[j]:

            result.append(left[i])

            i += 1

        else:

            result.append(right[j])

            j += 1

    result += left[i:]

    result += right[j:]

    return result



def merge_sort(lists):

    # 归并排序

    if len(lists) <= 1:

        return lists

    num = len(lists) / 2

    left = merge_sort(lists[:num])

    right = merge_sort(lists[num:])

    return merge(left, right)

8、基数排序

描述

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

代码实现

Python


import math

def radix_sort(lists, radix=10):

    k = int(math.ceil(math.log(max(lists), radix)))

    bucket = [[] for i in range(radix)]

    for i in range(1, k+1):

        for j in lists:

            bucket[j/(radix**(i-1)) % (radix**i)].append(j)

        del lists[:]

        for z in bucket:

            lists += z

            del z[:]

    return lists

Oct 15

读而思

天道酬勤是很多人知道的道理,“勤”的重点在哪里?农民很勤,工人很勤劳,但他们仍然是社会的底层。一些创业者每日披星戴月,依然没有摆脱失败的命运。在这里我们必须反思,一个成功的创业者或者公司员工,辛苦的体力只能带给你基本的温饱,如何获得更大的社会认可和上级认可是你必须要面对的问题。

天道不一定酬勤,深度思考比勤奋工作更重要。

我要讲一个故事。我在2003年就认识了雷军。在2010年投资小米之前,我们两个有大约六七年作为朋友的交往经历。这个故事我忘记是发生在哪一年,也许是在2007年,也许是在2006年,也许是在2008年。

有一次,我忘记是什么原因,雷军给我打了一个电话他说:“我一直认为你做投资是有自己的独到之处,你能告诉我,到底怎么样才能做一个成功的投资者?你为什么投资能做得非常不错呢?”

我当时给了他一个答案,“我相信我极其的勤奋。我相信天道一定能酬勤!我相信如果勤奋的话,你一定能做一个非常好的投资者。”我本来以为这个答案至少能得到雷军的部分认同,结果我没想到,他给了我一个让人惊讶的反馈。这个答案就是天道并非一定酬勤。

这个观点当时给了我非常大的刺激。我后来慢慢明白了,可能勤奋是必要的,但是勤奋是远远不够的。

这件体悟,也许我可以和大家分享另外一个有趣故事,是一本书。这本书豆瓣上可以找得到,叫《异类》。在豆瓣的书评里,有这样一段介绍:在《异类》一书中,作家格拉德威尔对社会中那些成功人士进行的分析,让读者看到了一连串颇感意外的统计结果:英超联赛大部分球员都在9月至11月出生;比尔·盖茨和史蒂夫·乔布斯都出生在1955年;纽约很多着名律师事务所的开创者竟然都是犹太人后裔,并且他们的祖辈大多是在纽约的服装行业谋生。

blob.png


为什么会有这些奇怪的统计结果?

我可以给大家再提供几个例子。我昨天上网又查了几个:富豪榜里有几个成功的创业者,我给大家报一报年龄啊。李彦宏1968年11月出生,雷军1969年12月出生,周鸿祎1970年10月份出生,丁磊1971年10月出生,马化腾1971年10月出生的。稍微不一样点,马云1964年10月出生。

我再给大家一个例子,我是中欧98级的。98级中欧的毕业生很有意思。我回中欧的时候,听到这样一个笑话。很多同学和老师说,你们98级的毕业生,是不是有什么特殊的基因。你看,你们班上做风险投资的特别多,比如刘芹,比如石建明,比如红杉资本的计越,CDH的陈文江,还在中国文化创业基金的陈杭。比我们再高一级是97级的也有几位。


为什么都是97或者98级的呢?是我们的基因有什么特殊之处吗?我想和大家分享的最重要的一点是,其实有时候光有勤奋是不靠谱的。机遇很重要。但是作为创业者,机遇是很难捕捉的,重要的是你要去发现这个机遇。


其实乔布斯和比尔盖茨都是1955年出生的原因,在他们大学毕业和辍业的时候,PC行业刚刚开始。为什么PC互联网的创业者1969年,1970年,1971年这个年龄群最多,是因为刚好互联网热潮,是他们刚好那一年参加工作两年到三年。你太早毕业了,像雷军是软件的这一代,他已经被他的“金山软件”给缠住了。你太晚出生,你还在大学里面,你根本没有机会去思考创业的机遇。


我1998年从中欧毕业,紧接着1999年刚好互联网浪潮爆出。不是因为我多么聪明,不是因为我多勤奋,因此机遇更重要。但是机遇不是运气,机遇是你对创业环境趋势的深度思考。深度思考要比你的勤奋更重要!只是绝大部分的机遇只是被动的被利用起来。只有少部分创业者是主动的去判断和捕捉机会。这是我和大家分享的另外一个观点“天道不一定酬勤!深度思考比勤奋工作更重要!”


孤独,是每一个创业者与生俱来的。


做公司早期创始人是非常困难的。因为你面对员工的时候,很难向他去解释,公司可能只有三个月发工资的钱,甚至三个月之后发工资的钱从哪里来,我都不知道。你无法和他们去分享这个事实。你同时还得和他们讲,你在干一件非常伟大的事情。而事实上,你连明天干什么都不知道。


第二,你也无法和你的投资人去分享这件事。因为并不是所有的投资人,都有勇气去听到真实的现状。你也无法站在聚光灯下,向媒体去分享你的创业故事。你讲的都是你的光鲜亮丽,而事实上,你的压力无法得到分担。


这种孤独是一个创业者与生俱来的。而且越是成功的创业者,在工作上孤独感更大。为什么?如果你不成功,你可能失败了以后换一个办公室,两年时间干一番新的事业。如果你成功了,你被成功所累,你有了光环。人人都认为你应该继续更成功。这种光环使得你的孤独感更强。


所以投资人的认同,以及让创业者放下这种所谓的包袱,是创业者本质上最需要的。其实投资者给你投一档钱,这不重要。投一档钱真的是因为跟你投缘,是对你的认同。


只是投资者把这种认同,用一个实实在在的,三个月之后要发的工资这笔账送给他们。因此,你看那些真的很优秀的投资者,他们内心深处是极其尊重创业者的。


他们从内心深处明白,他们之间的位置,不是一个居高临下的俯视态度,他们是平等的,甚至是创业者拥有更高的位置。因此,你作为一个创业者,真正需要找到的是能够认同你的投资人,而不应该是一张支票。我是一个什么都不是的人,但是我热爱创业。我知道怎么能够帮助中国的创业者获得成功,这是真正的财富。这是主流社会真正价值的所在。所以,认同是极其重要的一点。创业需要有价值的东西。


伟大创业者的灵感来自于一些你所忽略的细节。


在座的各位,可能听过我在其他地方的演讲。我曾经提到,创业最重要的愿景,要回答三个关键性的很“虚”的问题。“我是谁?我从哪里来?我向哪里去?”


但是我想今天我不展开讲其他问题。今天我想专攻一点,这三个问题其实一点都不虚一点都不空一点都不大。因为我们最关键的问题都是从蛛丝马迹的核心细节所捕捉出来的。所以要小中见大。


我给大家分享一两个例子。在2007决定投资UCweb,很多人不理解你为什么要投资UCweb这个手机浏览器。因为它有价值。它在浏览器上面放了一个所谓的分类导航目录,就是所谓的网站导航。


我想不出来,为什么在美国,是雅虎首先出现——这是一个人工分类的导航列表——而后谷歌出现,把整个的雅虎价值给打没了。但在中国,却是先有了百度,但是很多年以后,才出现了一个叫hao123的导航页,为什么?


我觉得这是一个很有意思的现象。雅虎一个最原始的人工分类列表,曾经极大规模地推动美国互联网发展。而被谷歌这样一个搜索引擎公司轻而易举地取代了。而在中国,我们一直强调中国有叫“后发优势”,我们却是在百度搜索引擎出现后,为什么又会出现一个人工分类的hao123?


这就存在一个非常非常有意思的核心细节。这说明在中国我们有大量的网民,是不知道怎么用拼音的,不知道怎么用键盘的,甚至是不知道怎么用搜索引擎的。拉丁字母打一个字做搜索非常简单,而中国用拼音写汉字输入到搜索框是很困难的。


这说明,第一,流量在互联网里是很核心;第二,流量的实现不一定纯粹是中国照搬美国。


2007年,没有安卓,没有iPhone。2007年,是塞班的时代。塞班的特点,是用手机键盘输入汉字,更加痛苦。用手机键盘,要去按住搜索框更加痛苦。所以我们发现我们的答案很简单,UCweb在2007年塞班的无线互联网时代是流量聚合核心。


这就是我们2007年投资UCweb最核心的一个观点。这个决策的核心点,来自于我们对hao123一个不起眼的现象的思考。所以我想在这里讲到,作为一个创业者,当你在规划你的创业愿景的时候,不要去捕捉一些概念,要去理解你的核心市场的那些核心细节。小中见大。很多伟大的创业者的灵感是来自于一些你所忽略的细节,一些蛛丝马迹的细节隐藏了大量的有益的洞察力。


洞见力是你有一个愿景的源发点。我看到了很多优秀的创业者,无论是周鸿祎,雷军,马化腾,他们所有都有着极强的洞察力。这些洞察力全是来源于被常人所忽略的蛛丝马迹中所捕捉到。


blob.png


三人行,必有我师,更重要的是与谁行?

“三人行,必有我师。”其实我想大家都懂的。但是实际上“三人行,必有我师”里面最关键的是:你跟谁在一起往前走。


我为什么想提这一点?因为在早期的时候,我们一般谈创业都说,我们多看看你的团队,你的团队执行力,团队的重要。


到底怎么来判断一个团队?有很多人都在问我,我曾经和有的朋友谈过。我说:“我看你娶什么样的老婆,我看你找什么样的女朋友。”其实这里面有一个很重要的一点在于你跟什么人交往,决定了你的优秀程度。


什么样的人是你的创业的合作伙伴,决定了你的创业团队的quality。 “三人行,必有我师。”我们要学会跟身边的人去学习他们身上的闪光点。


我在自己创业的过程中,和我那些投资了很多年的创始人,我从他们身上学到了很多东西。那么在今天如果我不考虑创业,你在组队的时候,你是愿意组一群你很容易说服和崇拜你的人做你的创业团队,还是尽可能找甚至比你还要优秀的能够扶持你创业的?


其实我们判断一个创业者是否有优秀的团队能力,其实就是看你和什么样的人在一起交往。


所以三人行,必有我师。更重要的是与谁行!小米创始人雷军在业内赫赫有名。他在2010年和我谈时说,他想建立一个不一样的创业公司,“我想把我的股权大量分散出去,因为我需要足够多的,尽可能的多的,足够优秀的人。我们小米前十个月没干事,只干一件事:找人。”


其实很多人觉得找人很难,其实首先要问问你,你是不是深刻地认识到,“三人行,必有我师。”谁做你的老师。人人都做你的老师,你跟谁行?所以在这件事情上,第一点,你要尽可能的找到你能够得到最优秀的,而且优秀程度决定了你团队有多优秀。而不是你如果足够优秀,你要找比你差的,这是很多创业者愿意去找一些容易被说服的比较普通的人的误区。


很多人说,我搞不定那些优秀的人。我同意,搞定优秀的人很难。但是这是我送给大家的另外一句话,“领导力来源于不偏不倚的自我认知、空杯心态和知行合一。”在这一点上,其实很多人认为领导的魅力,来自于你的成就,你的名气。我认为都不是。


真正的领导力,首先你要领导一个团队,你要领导自己。你要做一个公正与公平的领袖和领导者,你首先要对自己公平公正。不偏不倚的自我认知,是一个极难的事情。


所以到今天,我从不认为我是一个成功的投资者。我只愿意说,我是一个很热爱投资和创业的投资者。好的不偏不倚的自我认知,不但看清自己,也不看高自己。当你对自己不偏不倚非常诚实的时候,你会发现你身边的人都聚到你身边。因为他们认识到你是一个值得信赖的领袖。


第二,空杯心态。对于很多优秀的成功商人,特别有想法的创业者不是靠你声音大,是要学会能够放下能够倾听,聆听是比什么都重要的素质和能力。要学会坦荡,简单。所以对于一些优秀的团队,最好的管理是不管理!不管理的意思是说让他们变成自驱动的团队,每个人都能很好的管理自己。高效的团队来自于自驱动,而不是来自于KPI指标。


第三,怎么做到“守正出奇”?做减法是一个创业公司最重要的素质。很多时候,特别在互联网行业,追求极致。互联网是一个以点概面的行业。互联网是一个口碑点可以改变整个行业格局的地方。把公司所有的资源,赌在最核心的点上,是极其难的一件事。这是我讲的最后一点。


其实互联网是一个每天都会出现颠覆与创新的地方。每天都有很多创新的想法,但是我也想讲,现在互联网行业里面我看到很多优秀的人没有办法做成大事。原因是因为他们奇兵不断,怎么能够做到守正出奇是一件极难的事。


怎么能够做到守正出奇,这是我与周鸿祎交往时,所观察到的。周鸿祎是个有争议的人,但他在互联网流量这个理解上,是极其深刻的,他以前也是做流氓软件的。他反思了什么才能回到一个守正出奇的状况。


我想我今天不展开,只希望大家思考比较一下,在奇虎之前的周鸿祎,和奇虎之后的周鸿祎是不一样的。我觉得什么叫守正出奇,是互联网行业里面很重要的一个因素。


在座有很多年轻的创业者,你们都非常有创造力,但是怎么能够把你们的创造力放在一个更抢眼的位置。


首先最重要的一点做产品,而不要做生意。不要只做流量的转换收入,而不做核心用户价值。好的公司都是能够创造真正的长期价值。很多人说,小米手机就是一个会炒作的公司,会做营销的公司。有几个人真正理解,小米是这么具有极客精神的公司?


他把市场上所有资源,想办法提供给用户,最好的价值,最好的性价比,最好的体验。他创造的粉丝,和他的产品分不开。所以守正出奇,是互联网行业创业里面很重要的一个点。


创业的三个关键问题


我们在选择投资机会的时候,更看重优秀的创业者,除此之外还会考虑三个关键问题:这事儿是不是足够大;是不是抓住了一个正确时机,切入到一个趋势性的机会;这个公司长期来说能不能形成护城河效应。


第一个关键问题,这事儿是不是足够大,如果今天创业,你选择这个方向,应该问问自己,有没有发展空间,同时你有没有野心。


无论你是做1千万人民币的退出,还是做100亿美元的退出,基本要花6-8年(我们基本上平均投一家企业要经历6-8年时间)。而创始人把一个公司做起来,所投入的时间精力也是一样的,面临的问题和痛苦也相同。既然同样的时间退出,为什么不去选择一些足够大的机会?


第二个问题,是不是抓住了一个正确时机,切入到一个趋势性的机会?时机比选择方向更难,踩对点非常重要。


时机太早,这个市场机会没到,你会发现你很痛苦。90%的失败公司都不是方向、体量的问题,可能绝大部分都是时机太早的问题。领先市场3步、5步,市场还没起来,你就撑不下去了。不能领先太早,最好领先0.5步。太晚当然也不行,市场如果很热,通常意味着红海了,时机已经晚了。


最后一个关键问题,是否能够可持续发展,长期下来能形成竞争壁垒。好的商业模式、好的公司,时间是朋友,意思是说随着时间的推移,你的竞争壁垒越来越高,护城河越来越强,这就是可此续发展。


创业者应该有杀手气质、传教士能力


创业者要具备两个核心能力:一个叫以身作则的犀利杀手气质;另一个是你有传教士能力,能聚一帮牛人。

blob.png



杀手的气质。解决公司业务发展中的短板,就跟打仗一样,你要拿下这个山头,就要有在百万军中取上将首级的能力。公司的发展是长板和短板理论,什么短补什么,所以创业者最重要的能力是杀手气质,还有补短板的能力。你得不停的变,缺什么都能自己顶上,也许不一定能做的最好,但是你要有从0到1解决短板的能力,虽然你不专业,但你永远是那个冲在第一线的。


传教士是什么?就是深入思考和能影响到什么样优秀的人跟你一起的能力。传教士传教一定是你不信我的时候我来传。所以你身边聚一群什么样的人,基本就能衡量你的理念。如果你下面的人,每个都是很有想法的人,那一定是你的想法比他们都大,能把他们震住,你就能取得1+1大于2极强的成功。 雷军就是其中的佼佼者。


总而言之,创业者要有这两个能力:一是在0到1的时候,一定要有以身作则的,把公司的短板补掉,迅速把业务往前推进极强的执行能力。二是有传教士能力和魅力。你的魅力源头是来自于你的理念。两者缺一不可,特立独行的孤胆英雄,在今天很难成功。

May 23
转自:http://blog.jobbole.com/93905/
"hello world"它是最著名的程序。对于每个程序员来说,它几乎被认为是每种程序设计语言的第一个例子,那么这条消息是从哪里来的呢?
作为一个功能,计算机程序简单地告诉计算机显示“Hello, World!”。传统上,它是开发者用来测试系统的第一个程序。对于程序员来说,在屏幕上看到这两个单词意味着他们的代码可以编译、加载和运行,并且他们可以看到输出。
它是一个测试,象征着一个程序的开始。在过去的几十年,它已经成为了一个历史悠久的传统。在某个时候,所有在你之前的程序员在意识到他们成功与电脑进行通讯之后,都会肾上腺素急剧上升。下面将会介绍程序历史上最著名的两个单词开始是怎样出现的:
点击在新窗口中浏览此图片
Brian Kernighan(上面照片中的帅哥)创造了“Hello, World”,他是一本被广泛阅读的书籍(1978 年的《C 程序设计语言》)的作者。他在《C 程序设计语言》的前身(1973 年出版的《B 程序设计语言的入门教程》)中首次引用‘Hello World’。

main( ) {
extrn a, b, c;
putchar(a); putchar(b); putchar(c); putchar(’!*n’);
} 1 ’hell’;
b ’o, w’;
c ’orld’;


不幸的是,这位传奇人物自己也没办法明确地指出何时或者为什么他选择了“Hello, World”这两个单词。当在接受 Forbes India 的访谈中被问到是什么激发了他使用“Hello, World”这个名字的灵感时,他说他的记忆很模糊。“我记得的是我看到了一个卡通片,里面有一个鸡蛋和一只母鸡,并且母鸡说:‘Hello, World’”。
考虑到“Hello, World”代表着计算机编程对于大众是一种普遍现象的诞生,这组单词是很适合的。
当时,Kernighan 和他的同事 Dennis Ritchie(已故的 C 语言之父),都没想到这个语言和教程对今天的编程领域如此重要。因为这些想法只不过是 Bell 实验室(AT&T 的一个研究和开发分部)里面的一个研究项目。
虽然没人可以科学地解释为什么“Hello, World”会变得如此受欢迎,但是“Hello, World”程序标志着编程的历史论调上一个重大改变。下面让我们看下它的历史背景。
萌芽时期
虽然在今天很难想象,但是在 Kernighan 的书中出现“Hello World”之前,即二十世纪七十年代之前,计算机在大众心中是伴随着贬义的。它们是巨大的机器、非常慢、占据了整个房间并且需要科学家或者研究者全职进行维护保养。事实上,在七十年代末以前,计算机科学家编程都是用一叠叠打孔卡。

点击在新窗口中浏览此图片
人们普遍将计算机视为遥不可及的、复杂的和贵得离谱的设备,它们只预留给学术界的精英、国防或者政府。实际上,献身于计算机世界的行业巨头已努力地洗掉这个污名。想想我们已经走了这么远,以至于没有了我们的个人设备之后,切实感受到的焦虑感,这是多么令人惊讶。

第一次使用计算机的著名事迹之一发生在 1890 年的美国,当时自动电子制表机为超过 6 千万美国人计算数据。在二十世纪四十年代,Bombes 和 Colossus 计算机在第二次世界大战期间对德国人的电报密码进行解密。

二十世纪五十年代迎来第一台针对算术运算的商用计算机,像 Zuse 3 和 UNIVAC,但你需要上百万的美元才能买到一台。

从教育的角度来看,很多关于早期程序设计语言(像 FORTRAN 或者 BASIC)的书籍,都会提供这样一个观点作为书本的开始:计算机其实很有用的。这是根据算法学家和研究者 John Mount 的文章得到的。Mount 说“Hello, World”爆炸性受追捧表明一个时代的到来,那个时代里,计算机科学家不再觉得他们需要说服社会,去相信计算机的实用程序是有形的。

例如,在 1964 年的《My Computer Likes Me When I Speak Basic》一书中,介绍部分大体上谈及程序设计语言的意图。此外,第一个例子输出:“MY HUMAN UNDERSTANDS ME”。使用这个例子是为了加深一个不太流行的想法:人类事实上是可以与计算机对话的。1956 年的动态编程开始使用一些可以应用到普通计算的例子。

直到《C 程序设计语言》出现时,“Hello World”才真正地流行起来。
点击在新窗口中浏览此图片
Hello World’ 编程来了

触发“Hello World”传播的一个主要催化剂是 PDP-11(最早成功商用的微型计算机之一)的并行介绍。数字设备公司(DEC)一共卖出超过 600,000 台单价为 $10,000 的 PDP-11,这个价格远远低于通常需要花费数百万美元的计算机的价格。此外,PDP-11 的 16 位系列不需要穿孔卡片。这是首次你可以使用程序设计语言直接与一台电脑对话。

但是为了提高大众的接受程度,DEC 不能提及它是一台计算机。DEC 把它作为“程序控制的数据处理机”来进行推销,以此与过去的大型计算机撇清关系。随着更多的人购买可编程计算机,对《C 程序设计语言》这本书的需求也激增。

C 和 Unix 操作系统在 PDP-11 上首次流行起来。所以,紧接着出现支持新的 C 程序设计语言的商用计算机的热潮,驱使成千上万的人去阅读 200 页的《C 程序设计语言》。这也重新介绍了‘Hello World’。

在八九十年代以后,几乎每个用桌面软件工作的程序员都会拥有那本书的一份拷贝或者参考文献。至今已经卖出数百万份拷贝了。

开始学习编程可能会有很多不同的基础程序可用,但是到目前为止,‘Hello World’是最著名的。每个程序员会记住他们的第一个‘Hello World’,并以此作为他们开始编程的一个仪式。很多人可能没有意识到,但是每次一个程序员通过‘Hello World’这两个单词清除程序设计的第一个障碍后,他们所感受到的甜蜜和胜利的感觉,是经历过的超越历史的时刻。
分页: 6/11 第一页 上页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]