想更一进步的支持我，请扫描下方的二维码，你懂的~
原理：
可以将数组分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序
由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为log_2n的栈空间，因此空间复杂度为O(n+logn)。
另外，对代码进行仔细研究，发现Merge函数中有if(L[i] 也就是说，归并排序是一种比较占用内存，但却效率高且稳定的算法。 javapublicintmerge(intp,intq,intr){intcount=0;int[]right=assignlist(p,q);//赋值左半部分数组（赋值就是用for循环，还有一个哨兵：最后一个元素设置为maxvalue）int[]left=assignlist(q+1,r);//赋值有半部分数组inti=0;intj=0;for(intk=p;k<=r;k++){if(right[i]<=left[j]){arraytoSort[k]=right[i];i++;}elseif(right[i]>left[j]){arraytoSort[k]=left[j];j++;count=count+(q-p+1)-i;}}returncount;}voidMergeSort(intarry[],intstart,intend){if(start javafor(inti=0;i 堆排序借助了堆这个数据结构，堆类似二叉树，又具有堆积的性质（子节点的关键值总小于（大于）父节点）堆排序包括两个主要操作: 对于大数据的处理：如果对100亿条数据选择Topk数据，选择快速排序好还是堆排序好？答案是只能用堆排序。堆排序只需要维护一个k大小的空间，即在内存开辟k大小的空间。而快速排序需要开辟能存储100亿条数据的空间，whichisimpossible. javapublicclassHeapSort{publicvoidbuildheap(intarray[]){intlength=array.length;intheapsize=length;intnonleaf=length/2-1;for(inti=nonleaf;i>=0;i--){heapify(array,i,heapsize);}}publicvoidheapify(intarray[],inti,intheapsize){intsmallest=i;intleft=2*i+1;intright=2*i+2;if(left 空间复杂度：递归造成的栈空间的使用，最好情况，递归树的深度logn空间复杂的logn，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(log2n)。由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。 快速排序的每一轮就是将这一轮的基准数归位，直到所有的数都归为为止，排序结束。（类似冒泡）.partition是返回一个基准值的index,index左边都小于该index的数，右边都大于该index的数。 优点：不需要比较函数，利用地址偏移，对范围固定在[0,k]的整数排序的最佳选择。是排序字节串最快的排序算法。 分析：就是用计数排序中的预处理方法，获得数组C[0...k]，使得C[i]为不大于i的元素的个数。这样落入[a...b]区间内的元素个数有C[b]-C[a-1]。 计数排序的重要性质是他是稳定的。一般而言，仅当卫星数据随着被排序的元素一起移动时，稳定性才显得比较重要。而这也是计数排序作为基数排序的子过程的重要原因 为什么要用基数排序？ 计数排序和桶排序都只是在研究一个关键字的排序，现在我们来讨论有多个关键字的排序问题。 假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(MostSignificantDight)排序。 第二种方式是从最低有效关键字开始排序，称为LSD(LeastSignificantDight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。 通常，基数排序要用到计数排序或者桶排序。使用计数排序时，需要的是Order数组。使用桶排序时，可以用链表的方法直接求出排序后的顺序。 桶排序的思想近乎彻底的分治思想。 桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。 然后基于某种映射函数f，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标i)，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。 接着将各个桶中的数据有序的合并起来:对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。 补充：映射函数一般是f=array[i]/k;k^2=n;n是所有元素个数