面试算法之排序算法集锦

排序算法在面试过程中是经常会考的，这是很基础的，面试官觉得你应该很熟悉这些东西，如果你半个小时内写不出来，那基本就给跪了，因为这真的是狠基础狠基础的东西，所以我们得对一些基本的排序算法烂熟于胸，对这些排序思想，效率了如指掌，才能让面试官觉得你还行。基本的排序算法有：直接插入排序，冒泡排序，简单选择排序，shell排序，归并排序，快速排序，堆排序。其中归并，快速，堆排序是面试时候比较喜欢考的，因为这三个排序算法都是很重要的算法，会有很多实际的应用。下面就简单的介绍这些排序算法，并给出代码。

直接插入排序的思想很简单，就是从排序序列开始，依次将每个元素插入到前面已经排序好的序列中，最终使整个序列有序，直接插入排序的时间复杂度O(n^2)，空间复杂度为O(1)，代码如下：

shell排序在开始时步长d较大，分组较多，但每组的元素较少，故各组内直接插入较快，后来步长d逐渐缩小，分组数逐渐减少，而各组的元素数目逐渐增多，但由于之前排过序，使序列较接近于有序状态，所以新的一趟排序过程也较快。因此，shell排序在效率上较直接插人排序有较大的改进。
shell排序很关键的一点就是步长序列的选定，步长序列的选定决定着排序的效率。一般的建议是d(1) = [ n / 2 ]，d(i+1) = [ (d(i) - 1) / 3 ]，一般认为d都取奇数且互素为好，但这并没有得到理论上的证明。最后一个步长一定为1，这是必然的。
关于shell排序的时间复杂度据说很难分校，理论上没用具体结论，只是提出大致为O(nlgn)~O(n^2)之间，大概为O(n^1.3)。。。下面是代码：
索引i，j初始初始化为序列开始，然后索引j依次后移，如果遇到A[j] <= x，那么就交互A[i + 1]和A[j]，直到索引j移动到末尾，这样结果是索引i左侧的元素都<=x，右侧的元素都>x。达到了partition的目的，这种算法很简单，代码如下：
索引i从左端开始扫描，直到找到第一个大于主元x的元素，索引j从右端开始扫描，直到找到第一个小于等于x的元素，然后将这两个索引对应的元素进行交换。继续上面的操作，直到i > j。代码如下：
具体思路：索引i指向主元的位置，索引j先从右端开始向左扫描，直到遇到第一个<= x主元的元素，然后将该元素移动到索引i所指的位置，然后索引i从当前下一个元素开始向右扫描，直到遇到一个>x的元素，将该指辅导索引j所指的位置。如次循环，直到i = j，主元存放到该位置。代码如下：
欢迎吐槽。。。
累吐血了。。。碎觉。。。
Date: Sept 11, 2013 AM 03:03@dorm
1楼lu07081141171小时前
三点%>_<%