算法入门篇：简单的排序算法 _排序算法

作者：dorseyCh来源：http://www.imooc.com/article/264180很久之前有过一次面试，被问到一个问题，能不能写一个冒泡排序？说实话，尽管在这之前曾经写过不少比这个更加复杂的处理逻辑，但很悲剧的是我当时真不知道什么是冒泡排序。。。只知道如果让我排序某段混乱序列，能很快搞定就是了，最后的结果显而易见，我被赤裸裸的鄙视了。。。（连个性能最差的冒泡排序思维都不会，要你何用= =），第二天回去，看了啥是排序，真的捶胸了半天，名字叫得那么好听，原来是这个。。。
简单的排序算法基本是下面这几种，其中的话冒泡排序，选择排序，插入排序是性能最差，实际应用基本不用但也是最简单，能提高你算法信心的几个小排序方式。

文章插图

下面的话，我们一个个来实现，假如我们要让[1, 2, 32, 23, 321, 45, 8, 90, 227, 99]从小到大排列。
既然要排列，我们第一反应肯定是比较，大的放后边小的放前边，对吧，两两进行比较。
1
冒泡排序

先拿第1第2个数比较，谁大谁后面，接着第2个跟第3个，还是谁大谁后面，继续第3第4，第4第5 。。。这样进行了一轮之后，你是不是可以很肯定，最后的那个数一定是最大的？接下来混乱的序列就少了一位了对吧？就继续剩下的序列继续上面的一轮。而你仔细想一想这个过程，12，23，34，...有没有种演唱会现场一波波人浪冒出来的感觉？嗯，没有错，这就是冒泡，像一块软绵绵的地毯，里面有一颗玻璃珠在滚动，滚着滚着这个地毯就有序了。= =嗯，这就是冒泡排序。下面看看它的代码是怎样。

文章插图

2
选择排序

上面的是最简单的排序了，人的第一直觉就能产生的一种解决问题的思路。但是呢？思维肯定是不断进步的，不可能一直停滞不前的，为什么呢？人浪排序不是很好吗？额不对，冒泡排序不是还不错嘛？简单直观，但是你要知道，有些人的脑回路不一定如此直观，他们解决问题的思路是这样的：
他觉得，我每次比较后符合要求的都去交换，有些处于中间值的，不是要不断的被交换？不是很浪费时间？我能不能选出这段序列中最大的那个数，然后放到最后边？
答案是肯定的，怎么做呢？既然是序列，代码中是数组，那有一个下标，我先把第一个数据给存起来，这个数不断的从第1项比到最后一项，当谁的值比他大时，他就把他的值存起来，这样一轮过后，它拿到了最大值，这时候就把选出的这个数，仍最后。接下来那个第二大的仍这个最后的前面一项，一直到完成整个序列。这样这种通过不断选出剩余项最大值的方法叫做选择排序。
一起看看它的代码是怎样的吧：

文章插图

这种选择排序，虽说没有了交换的过程，但又多了赋值的过程，实际上并不比冒泡强哪去，也还是那样，理论上的性能能稍微好那么一丢丢，基本可以忽略不计。
3
插入排序

跟冒泡和选择同一时期的，还有一个插入排序，插入排序的方式更加的简单，你想一个问题，假如你现在手上多了一个空的数组，那你会怎样排序？是不是先把第一个放到空数组后，往后拿过来的数都跟这个新数组的各个数比较，插入到某两个数（只需注意大的在你后面，小的在你前面就OK）之间，但是呢，实际上，新创建一个数组的开销是不算小的，没理由一个简单的算法都要这样做，所以可以这样：
抽出第2个数，这样就变成了前半段（你的新数组），跟后半段（原来的大数组），这样不断的把你后半段的数，插入到前半段，前半段大的就往后挪腾位置给新数插入，对吧？是不是也可以实现你想要的？一起看看这个插入排序是怎样实现的吧。

文章插图

上面这3种排序，你是不是代码中要有两个for循环，而且是完全的遍历，一步步走的，对吧？一个用于每一轮的比较（这时候只是进行了某一个数的比较，或者说确定了某一个数在整个数组中它所处的位置），一个用于遍历整个数组，把每个成员都拿出来遛一遛。对吧，那就是n²，也就是时间复杂度O(n²)（个人理解，不一定非常准确，但个人认为还是比较好理解的，不至于说得很复杂）