查找和排序
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
我们这里说说八大排序就是内部排序。
当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
一、冒泡排序
思想：重复走访过要排序的序列，一次比较两个元素，如果他们的顺序错误就将他们进行交换，一次冒上来的是最小的，其次是第二小。
时间复杂度：O(n^2)
空间复杂度:O(1)
稳定性：稳定
二、快速排序
思想：通过一趟排序将待排记录分割成两个部分，其中一部分记录关键字均比另一部分记录的关键字小，则可以分别对这两部分关键字继续排序，以达到整个序列有序的目的。
时间复杂度：O(nlogn),最坏的情况下为O(n^2)
空间复杂度：O(1)
稳定性:不稳定
三、直接选择排序:
思想：每一趟排序将会选择出最小的(或者最大的)值，顺序放在已排好序的数列的后面
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
操作方法：
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推.....
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。
四、堆排序
思想：堆排序利用这种堆这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素
时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定
五、插入排序思想：将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录增1的有序表。默认将第一个元素看为有序表，然后依次插入后边的元素
注意：这里插入元素的时候默认的策略是从后向前看，找第一个比自己小的；而不是从前向后看，找第一个比自己大的
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
直接插入排序示例：
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
思想：折半插入排序是基于直接插入排序进行改写的，其可以减少"移动"和"比较"的次数
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
七、希尔排序：
思想：希尔排序也是插入排序的一种，是直接针对插入排序进行改进的，该方法又称为"缩小增量排序"。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
希尔排序的示例：
思想：归并排序是将两个或两个以上的有序表组合成一个有序表，该算法是采用分治法实现
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定
http://blog.****.net/xingdou520/article/details/53232748