选择排序算法
为什么学习0（n^2）的排序算法
1.基础
2.编码简单，易于实现，是一些简单情景的首选
3.有些特殊情况下，简单的算法更有效
4.简单的排序短发思想衍生出复杂排序算法。
5.作为子过程，改进跟复杂的排序算法。
Selecttion Sort 基本思路
思路：
首先在整个数组的范围里找到第一名的位置（假设从小到大排序），找到最小的1，将1与现在第一名的位置交换，在剩下的数组中在找最小的2，与数组中现在第二名的位置交换，以此类推，直到所有数都有序。
插入排序法 Insertion Sort
思想: 玩扑克牌的时候整理牌的思想就是 插入排序的思想。就是看后片的每一张牌，把这张牌插入合适位置，当我们对最后一张牌作为这个操作以后就已经排序完成。
看下面这个数组为例，先看第一个位置8，不动，在看第二个位置，此时6比8小所以前两个数调换下位置，此时前两个位置就已经排好序了，在看第三个元素2，把它插入前面合适的位置，首先2和8比 交换位置，2在和6比 还是交换位置，这样2,6,8 这三个元素已经排序完成，后面一次类推
插入排序法的改进
插入排序优点：最大优点是可以提前终止内部循环，所以一个近乎有序的数组，插入排序非常高效
上面排序的缺点是，在每次循环都需要调换位置，而调换位置是很耗时的，所以我们改进的想法是，每循环一遍只调换一次位置。
思想：假设现在考察2这个元素，首先把2这个元素复制出来，之后来考察2是不是该呆在这个位置，2比这个为位置前面位置的8 小，所以2不应该放在这个位置，我们把这个位置赋值成8，之后来考察2是不是应该放在原来8这个位置，2比这个位置前一个值6小，所以我们将6赋值放在这个位置，在看2是不是应该放在原来6这个位置，因为是第0个位置，所以直接赋值，下面的一次类推。
更多关于0（n^2）排序算法思考
选择排序：缺点，对于任何一个数组，两层循环，每一层循环都必须完全执行完成，所以选择排序效率在任何情况下都是非常慢的。
插入排序：最差的时间复杂度是0^2级别的，但是在数组近乎有序的情况下排序性能非常高甚至会比nlogn基本的排序算法 性能还要高。
---延伸算法（希尔排序）：插叙排序是每一次都和之前的一个元素比较，而希尔排序尝试每一次和之前第h个元素比较，这个将h从之前很大的值逐步缩小的1，一步一步讲一个完全无序数组，编程的一个近乎有序的数组，最终编程排好序的数组。
冒泡排序（Bubble Sort）：性能整体没有插入排序好，所以使用性不强。
冒泡排序的基本思想就是：从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。
算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。
高级排序
归并排序法
思想：当我们要排序一首数组时，首先将数组分成一半，之后将左边数组排序，右边数组排序，继续分半，当分到一定粒度时，每个就一个元素，他自然就有序的，之后再将其向上归并。逐层上升。
我们看上图，用最多画分到3层，通过层级来简化时间复杂度，对多为n*long(N)
而我们将左边和右边都变得有序时，如何归并成最终有序数组那！可以通过开辟临时空间的方法实现， 所以当今我们设计算法优先考虑时间复杂度，不考虑空间的使用，
实现方法：整体我们需要3个索引在数组中进行追踪，蓝色箭头表示，在最终在归并的过程中需要跟踪的位置，两个红色箭头分别指向这两个已经排好序的数组，首先考虑1,2这两个元素谁应该先放在最终的数组中，1比2小所以将1先放到最终的数组中，这样蓝色箭头可以考虑下一个位置，与此同时1所在的箭头也可以考虑下一个位置，在下一次比较中，2和4谁跟小，将2放在最终数组中，之后蓝色箭头下移，2所在的红色箭头下移，之后就考虑，3和4这两个元素了，以此类推，最终有序
对索引的定义，两个红色的i,j 是当前正在比较的元素索引，k,表示比较后最终放入元素的位置索引。最左边的元素l,最右边的元素r.中间为位置m(放在第一个排好序的数组的最后的位置)。
public class MergeSort {
/** 分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果. */
//递归使用递归排序，对arr[l....r]的范围排序
private void _mergeSort(int[] arr,int l,int r){
//对于一个递归函数来说 要处理一个递归到底的情况 就是l>=r的情况,
// 就是剩一个元素或一个元素都没有,就直接返回就好，否则就需要处理归并排序
if(l>=r){
return;
}
//1.首先计算这个区间中点位置在哪
int mid=(l+r)/2;
//2.下面就可以对分开的左右两个部分进行归并排序
_mergeSort(arr,l,mid);
_mergeSort(arr,mid+1,r);
//3.归并排序分解完后，就需要在合并了
_merge(arr,l,mid,r);
}
//将arr[l...mid]和arr[mid+1....r]两部分进行归并
private void _merge(int[] arr,int l,int mid,int r){
//归并 首先需要临时空间
int[] aux=new int[r-l+1];
//将当前的arr里的内容全复制到aux中 aux是从0 开始的 arr是从l开始的
for (int i=l;i<=r;i++){
aux[i-l]=arr[i];
}
//下面开始具体归并 首先设置那两个个数组
int i=l,j=mid+1 ;
for (int k=l;k<=r;k++){//我们用k这个索引来遍历
if(i>mid){
arr[k]=aux[j-l];
j++;
}else if(j>r){
arr[k]=aux[i-l];
i++;
}else if(aux[i-l]<aux[j-l]){ //说先比较aux中 两遍需要放到k中元素的大小
arr[k]=aux[i-l];
i++;
}else {
arr[k]=arr[j-l];
j++;
}
}
}
public void mergeSort(int[] arr,int n){
//本质是一次递归排序，在这个过程中，我们需要对arr数组不同部分，继续进行归并排序，为此我们要做一个子函数
_mergeSort(arr,0,n-1);
}
public static void main(String[] args) {
}
}
归并排序算法的优化
看下面的实现结果，对一个近乎或完全有序的数组进行排序的话，插入排序要比归并排序效率高。
优化1
在递归归并排序之后，判断下 如果，arr[mid]<=arr[mid+1]时，arr就是有序的，我们整个过程保证保证了l到mid是有序的， 从mid+1到r也是有序的，所以我们真正需要merge是arr[mid]>arr[mid+1],
经过这一步的优化，看下图
优化2
所有需要递归的算法，都有一个问题就是递归到底的情况，现在我们递归到只有1个元素，而我们可以改进为只有少量元素时可以用插入排序，原因是元素少的时候有序的概率就大，插入排序有优势，另外一方面插入排序最差时间复杂度是n^2级别的，归并排序是n(longN)级别的，前面都有一个常数的系数的，对于这个系数而言，插入排序要比归并排序小的，当n小到一定程度，插入排序会比归并排序要快一些 。举个例子，我们递归到16个元素，看下面优化后的结果。
自底向上的归并排序算法
思想：比如果我们一个数组，我们可以从左到右一次将这个数组画分成小段，比如两个元素一个小段，然后来进行归并排序的过程，当归并排序完一轮之后，我们在四个元素一个小段的来进行归并排序，最终完成整个归并排序，在这样有一个实现中，我们并不需要递归，只需要迭代就可以完成归并排序。
实际上自底向上和自顶向下的排序，效率差不多，从统计学角度看，第一种自顶向下的效率要高一些。但是由于自底向上排序算法，没有使用索引，所以可以为链表结果的数组排序。
20世纪最伟大的排序算法-----快速排序
思想：选着一个基点元素如4，想办法把这个元素挪到他排好序的位置，这就使得这个数组具有了一个性质，4之前的元素都小于4,4之后的元素都大于4，之后我们要做的就是对小于4的子数组和大于4的子数组分别用快速排序的思路来排序。逐渐递归下去，完场整个排序规程。
对于快速排序算法 最重要的就是 如何把选定的元素快速挪到正确的位置上.
下面看i这个元素，看当前元素要怎么变化，才能使整个数组，还保持这样的性质，
情况1，当前这个元素e>v 这样简单，将e直接放到大于v的队列里，i++
情况2，当前这个元素e<v,这样我们要想办法吧当前的e放到橙色部分，我们只需要把当前橙色部分（也就是j所指向的位置）后一个元素，和当前所考察的e这个元素进行位置交换，
就是 有一个大于v的元素放到了i这个为位置，而我们当前考察的e放到了j的后面，之后j++, 之后我们在进行i++来进行下一个元素的考察。
整个遍历玩就是下面的样子，整个数组分成三部分.
具体代码：
public class QuickSort {
public void quickSort(Integer arr[],int n){
//使用递归的方式排序，
_quickSort(arr,0,n-1);
}
//对arr[l....r]部分进行快速排序
private void _quickSort(Integer[] arr,int l,int r){
//首先对递归到底的情况处理
if(l>=r){
return;
}
//调用子函数
int p=partition(arr,l,r);
_quickSort(arr,l,p-1);
_quickSort(arr,p+1,r);
}
//对arr[l....r]部分进行partition操作
//返回索引值p, 使得arr[l...p-1]<arr[p];arr[p+1....r]>arr[p]
private int partition(Integer[] arr,int l,int r) {
//首先需要一个标准元素（第一个元素）
int v=arr[l];
//开始遍历后面的所有元素，使得后面可以分成两个部分
int j=l;
for(int i=l+1;i<=r;i++){
//出现第一种情况，我们什么都不用做，i++就好了
if(arr[i]<v){//属于第二种情况
//我们要交换位置
SortTestHelper.( arr,j+1,i);
j++;
}
}
SortTestHelper.( arr,l,j);
return j;
}
}测试结果：快速排序要比归并排序，效率高30%左右
优化1
高级的递归排序算法 到底层都可以采用插入排序来替换，看下图速度比之前提高一些。
优化2
看下面 在近乎与有序的数组上，快速排序和归并排序的比较，在近乎有序数组上，快速排序效率非常差，
看下图，快速排序其实也是一种快速差分的过程，但是快速排序并不能保障差分的平衡度，高度也很有可能比longN要高，最差的情况可能退回O(n^2)的时间复杂度
当整个数组完全有序，我们使用最左边的这位置作为标定点，就会出现，没有任何位置小于
它，那么生成的数，左边没有东西，只有右边的树，此时这个树的高度是n,每层处理是用on的复杂度，此时就退化成O(n^2)。
如何解决上面的问题：就是选择的标准点尽可能是数组的中间位置。我们不能快速定位中间元素，所以我们的解决方案，是随机选择一个元素，此时快速排序的期望值是n*longN的。
双路快速排序
我们看下面的图，如果有大量重复数出现的快速排序，也是非常慢的。
原因：当有大量重复数出现的情况下，partition 操作会把数组分成极度不平衡的两部分，在这种情况下 我们快速排序就会退化成O(n^2)
解决方案：首先我们对于partition操作，将大于或小于v的放到数组的两端，我们就需要一个新索引J 来记录大于v这一段下一个要扫描的元素的位置，如：我们从i这个位置开始向后扫描，当我们面对的元素任然是小于v的元素，我们就继续直到我们碰到了某一元素e,e>=v的我们停止，同样我们对j也是同样的，我们从j向前扫描如果是大于v就继续直到碰到元素e ,e<=v,此时i和j 这两个交换下位置就可以了。此时橙色部分都是小于等于v的元素，紫色部分都是大于等于v的元素。之后继续，直到i和j 这两个索引重合。
新思路的partition 代码
private int partition2(Integer[] arr,int l,int r) {
//随机选着一个标定点
SortTestHelper.(arr,l,rand()%(r-l+1)+l);
int v=arr[l];
//首先做两个临界点i和j arr[l+1...i)<=v;arr(j...r]>=v
int i=l+1,j=r;
while (true){
while (i<=r&&arr[i]<v){
i++;
}
while (j>=l+1&&arr[j]>v){
j--;
}
if(i>j){//整个循环结束了
break;
}else {//交换两个元素
SortTestHelper.(arr,i,j);
i++;
j--;
}
}
//将v放到合适位置
SortTestHelper.(arr,l,j);
return j;
}三路快速排序
思想：把整个数组分成三部分，小于，大于，等于，下面我们需要以下索引，lt,gt,i 这三个索引。
情况1，当前处理的元素e是等于v的，就纳入等于v的部分，相应的i++
情况2，当前处理e小于v,我们只需要把这个元素和等于v部分的第一个元素进行交换，lt++,i++,来查看下一个元素
情况3，当前处理的e大于v,我们只需要把这个元素和gt-1的位置交换，之后gt--,
此时i不需要动，他依然指向一个没有被处理的元素，就是被，调换过来的元素。
最后数组分成三部分，最后i与gt重合时 就是完成时。最后我们只需要将l位置元素和lt位置元素交换位置就可以。
代码实现
/三路快速排序处理arr[l....r]
//将arr[l...r]分为<v,=V,>v三部分
//之后递归对<v;>v两部分继续进行三路快速排序
private void _quickSort3(Integer[] arr,int l,int r){
//首先对递归到底的情况处理
if(l>=r){
return;
}
// if(r-l<=15){
// InsertionSort.selecttionSort(arr,l,r);
// return;
// }
//partition部分
//随机选着一个标定点
SortTestHelper.(arr,l,rand()%(r-l+1)+l);
int v=arr[l];
int lt=l;//arr[l+1..lt]<v
int gt=r+1;//arr[gt...r]>v
int i=l+1;//ar[lt+1....i)==v
while (i<gt){
if(arr[i]<v){//情况1
SortTestHelper.(arr,i,lt+1);
lt++;
i++;
}else if(arr[i]>v){//情况2
SortTestHelper.(arr,i,gt-1);
gt--;
}else {
i++;
}
}
SortTestHelper.(arr,l,lt);
//之后递归
_quickSort3(arr,l,lt-1);
_quickSort3(arr,gt,r);
}
//对arr[l....r]部分进行partition操作
//返回索引值p, 使得arr[l...p-1]<arr[p];arr[p+1....r]>arr[p]
private int partition3(Integer[] arr,int l,int r) {
//随机选着一个标定点
SortTestHelper.(arr,l,rand()%(r-l+1)+l);
int v=arr[l];
//首先做两个临界点i和j arr[l+1...i)<=v;arr(j...r]>=v
int i=l+1,j=r;
while (true){
while (i<=r&&arr[i]<v){
i++;
}
while (j>=l+1&&arr[j]>v){
j--;
}
if(i>j){//整个循环结束了
break;
}else {//交换两个元素
SortTestHelper.(arr,i,j);
i++;
j--;
}
}
//将v放到合适位置
SortTestHelper.(arr,l,j);
return j;
}看测试结果：
结论1 ：当有大量重复元素时，就是最后一个结果，三路快速排序远远好于其他。
结论2；其他境况下，三路快速排序也基本和其他排序在一个数量级上，且优于归并排序。
堆排序
public class MaxHeap {
private Integer[] item;
private int count;
public MaxHeap(int capacity){
this.item=new Integer[capacity+1];
}
public int size(){
return count;
}
public Boolean isEmpty(){
return count==0;
}
void insert(int data) {
item[count+1]=data;//首先给新添加元素一个为位置
count++;
//新加入元素有可能破坏了对的定义，所以我们需要shifUP比较
shipUp(count);
}
private void shipUp(int k){
//我们每一次看k这个位置与父节点（k/2）比较
while (k>1&&item[k/2]<item[k]){
SortTestHelper.(item,k/2,k);
k/=2;
}
}
}堆排序的实现
我们利用堆实现第一个排序算法，首先将数组arr中的元素全部加入到堆中，maxHeap.insert(arr[i]),之后我们再从堆中将数一个一个取出来就是从大到小的顺序，想要从小到大的顺序，就反正去出来就可以了。
下面是测试结果，看结果堆排序，相对于快排和归并来书说稍慢，但是还是在一个数量级内的，堆排序本身也是一个n*longN的排序。
Heapify
就是给定一个数组并且让数组形成堆形状，我们称之为Heapify。
如下图，我们拿到一个数组，就可以直接转化成二叉数，当然，这样的二叉树不符合我完全二叉树的定义，下面有两个属性；
属性一：所有叶子节点（就是没有孩子的节点，本身就一个元素，本身符合完全二叉树）可以不用考虑。
属性二:第一个父节点是数组长度除以2的得到了。
我们可以从第一个父节点入手用执行shift down操作就可以了。
新的构造函数
我们利用新的Heapify得构造函数，实现排序算法
下图为测试结果：
第二个堆排序性能优第一个对排序，但还是没有前两个算法好，所以系统级别的算法一般不用堆排序，堆这种数据结构，更多是对动态数据的维护。
排序算法总结
稳定排序
应用：比如说一个学生成绩单，初始是按照学生的字典序，我们按照学生分数排序，稳定的排序就能做到，对于相同分数学生，他们之间依然是按照字典序排的。
插入排序为什么是稳定排序：因为插入排序 后面的元素和前面的相等，那么后面的元素永远不会超越前面，只能安原来的顺序排， 从而保证稳定性。
归并排序为什么是稳定排序：我们在比较是之后后面部分的元素小于前面的元素，才放到归并数组中，否则，都是前面元素放到数组中，所以顺序也不变，
堆排序，在组建堆的过程中，很有可能破坏先后顺序，快速排序，随机选择标定点时，也可能破坏先后顺序。
总结：
基础排序（0（n^2））
选择排序：在整个数组范围内找到第一名位置，找到最小的1，将1与第一名位置交换，在剩下数组中找最小的2，与第二名位置交换，直到所有数都有序。
插入排序：类似于整理扑克牌，把每一张牌放到合适的位置，从头开始让整个数据一点一点变得有序
希尔排序：插叙排序是每一次都和之前的一个元素比较，而希尔排序尝试每一次和之前第h个元素比较，这个将h从之前很大的值逐步缩小的1，一步一步讲一个完全无序数组，编程的一个近乎有序的数组，最终编程排好序的数组。
冒泡排序
高级排序（n(logn)）
1.归并排序：
当我们要排序一首数组时，首先将数组分成一半，之后将左边数组排序，右边数组排序，继续分半，当分到一定粒度时，每个就一个元素，他自然就有序的，之后再将其向上归并。逐层上升。
2.快速排序---20世纪最伟大的排序
选着一个基点元素如4，想办法把这个元素挪到他排好序的位置，这就使得这个数组具有了一个性质，4之前的元素都小于4,4之后的元素都大于4，之后我们要做的就是对小于4的子数组和大于4的子数组分别用快速排序的思路来排序。逐渐递归下去，完场整个排序规程。
3.堆排序：
所以系统级别的算法一般不用堆排序，堆这种数据结构，更多是对动态数据的维护。