排序算法
排序 对一序列对象根据某个关键字进行排序
1 冒泡排序
算法描述
*比较相邻的元素，如果第一个比第二个大，交换它们两个
*对每一对相邻元素作同样的工作，从开始的第一队到对尾的最后一对，这样在最后的元素应该是最大的数
*针对所有的元素重复以上的步骤，除了最后一个
*重复上述步骤 直至排序完成。
代码实现
算法分析 最佳情况 T(n)=O(n) 最差情况：T(n)=O(n^2) 平均情况 T(n)=O(n^2)
选择排序
表现最稳定的算法之一
*初始状态 无序号区R【1..n】,有序区为空
*滴i趟排序（i=1，2，3...n-1）开始时，当前有序区和无序区分别为R【1...i-1】和R（1...n）。该趟排序从当前无序区中 选出关键字最小的记录R【k】，将它与无序区中的第一个R交换，使R【1....i】和R【i+1】分别变为记录数据增加1个的新有序区和记录数据减少一个的新无序区
*n-1趟结束 数组有序化了
算法分析 最佳情况 T(n)=O(n^2) 最差情况 T(n)=O(n^2) 平均情况 T(n)=O(n^2)
3 、插入排序
插入排序的算法是一种比较简单直观的排序算法，它的工作原理是构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
算法描述
* 从第一个元素开始 该元素可以被认为是已经被排序
*取出下一个元素 在已经排序的元素序列中从后向前扫描
*如果该元素（已排序）大于新元素，将该元素移动到下一位置。
*重复步骤3 直到找到已排序的元素小于或者等于新元素的位置。
*将该元素插入到该位置
*重复步骤2---5
算法分析
最佳情况 T(n)=O(n) 最坏情况 T(n)=O(n^2) 平均情况 T(n)=O(n^2)
4 希尔排序
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序；随着增量逐渐减少 ，每组包含的关键词越来越多。当增量减至1时，整个文件恰被分成一组，算法终止。
算法描述
选择增量 gap=length/2,缩小增量继续以gap=gap/2的方式，这种增量选择我们可以用一个序列来表示 {n/2,(n/2)/2,.....1},称为增量序列
* 选择一个增量序列t1,t1,t3,.......，tk, 其中ti>tj,tk=1；
*按增量序列个数k,对序列进行k趟排序
* 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各个子序列进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度为序列长度。
算法分析 最佳情况 T(n)=O(nlog2n) 最坏情况 T(n)=O(nlog2n) 平均情况 T(n)=O(nlog2n)
归并排序
归并排序和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多。
算法描述
* 把长度为n的输入序列分成两个长度为n/2的子序列
* 对这两个子序列分别采用归并排序
* 将两个排序好的子序列合并成一个最终的排序序列
=================================================================================
1. 在数组中选一个基准数（通常为数组第一个）；
2. 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边；
3. 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。
代码实现：
算法分析 T(n) = O(n) 最差情况 ：T(n)=O(nlohn) 平均情况：T(n)=O(nlogn)
快速排序
快速排序的思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分的关键字比另一部分小，则可分别对这两部分记录继续进行排序。以达到整个序列有序。
算法描述：快速排序用分治法把一个串分为两个子串，具体描述为：
* 从数列中挑选出一个元素，称为“基准”
* 重新排序数列，所有元素比基准小的摆放在基准前面，所有元素比基准大的值摆在基准的后面。在这个分区退出之后
二分查找
二分查找也称折半查找 是一种在数组中查找特定元素的搜索方法。
1 从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步
2 如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤1的操作。
3 如果某一步数组为空，则表示找不到目标元素。