转载请注明原文地址：http://www.cnblogs.com/ygj0930/p/6594855.html
一：归并排序==通过中间值进行左右划分递归，然后调用合并函数对左右递归的结果进行合并（用临时数组存放合并结果，再覆盖原数组对应区间）
第一步：把数组通过递归，划分成 一个元素区间大小；
第二步：相邻区间合并成一个更大的区间，合并过程中实现有序，小者在前（此步相当于排序了上一递归时划分出的元素区间）；
第三步：把当前合并得到的有序区间返回上层递归，与同等大小的相邻有序区间再次进行合并；
...
第N/2步：把两个N/2大小的有序区间合并，得到有序的整个数组。
复杂度计算：T=N/2（合并次数）*logN（递归划分次数）=O(N*logN)
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
if(A!=null && n>0){
MergeSort(A,0,n-1);
}
return A;
}
//划分：通过中间值划分出左右区间，然后对左右区间进行合并。
public void MergeSort(int[] A,int left,int right){
if(left<right){
int mid=(left+right)/2;
MergeSort(A,left,mid);
MergeSort(A,mid+1,right);
Combine(A,left,mid,right);
}
}
//合并：通过临时数组存放合并结果，每次取两区间开头值的较小者合并，一方为空后另一方全部依次合并，最后把合并结果覆盖原数组对应区间
public void Combine(int[] A,int left,int mid,int right){
int[] temp=new int[right-left+1];//临时数组存放合并结果
int leftindex=left;//左区间下标
int rightindex=mid+1;//右区间下标
int tempindex=0;//临时数组当前保存元素下标
while(leftindex<=mid && rightindex<=right){//如果两个区间都还有元素
//则取两区间开头元素进行比较，最小值合并到临时数组
if(A[leftindex]<A[rightindex]){
temp[tempindex++]=A[leftindex++];
}else{
temp[tempindex++]=A[rightindex++];
}
}
//如果左区间已经取完了，右区间还有，则把右区间的依次合并到临时数组
while(rightindex<=right){
temp[tempindex++]=A[rightindex++];
}
//如果右区间已经取完了，左区间还有，则把左区间的依次合并到临时数组
while(leftindex<=mid){
temp[tempindex++]=A[leftindex++];
}
//最后，把临时数组的合并结果，覆盖到原数组中的合并区间
int temp_copy_index=0;
for(int i=left;i<=right;++i){
A[i]=temp[temp_copy_index++];
}
}
}
二：快速排序==挖坑填数思想进行排序：用左边第一个元素作为参照值，并挖出来，空出位置；然后从右边往左找到第一个小于参照值的数填进来；此时右边空出一个位置；然后从左边找到一个大于参照值的数，填到右边的空位，此时左边空出一个位置......不断左右找数填坑，最终左右遍历坐标相等时的坑位就是参照值的位置。由 挖坑填数 排序得到的参照值的位置划分序列，分别进行左右递归；
第一步排序左右：选一个参照值，定义两个下标left和right，一个从头到尾，一个从尾到头遍历。各自找到一个大于/小于 参照值 的元素则停下，然后把这个元素与参照值进行交换，使得小于参照值的都在右边，大于的在右边。两下标相等时停止遍历。此时参照值的位置就划分了左右序列，把此时参照值位置返回。
第二步递归左右：对第一步得到的参照值的左、右序列继续执行排序操作——选参照值、前后遍历与参照值比较交换，最终使参照值处于合适位置。
复杂度计算：T=N（每次排序交换左右遍历N个元素）*logN（每次平分序列，logN次可以把序列分至单个元素一个区间）=O（N*logN）。
public class QuickSort {
public int[] quickSort(int[] A, int n) {
quick(A,0,n-1);
return A;
}
//由 挖坑填数 排序得到的参照值的位置划分序列，分别进行左右递归
public void quick(int[] A,int left,int right){
if(left<right){
int mid=sort(A,left,right);//先进行左右排序，并把排序结果的分界点下标返回，作为递归的中间值
quick(A,left,mid);//然后对左右排序的左序列、右序列进行递归
quick(A,mid+1,right);
}
}
//由挖坑填数思想进行排序：用左边第一个元素作为参照值，并挖出来，空出位置；然后从右边往左找到第一个小于参照值的数填进来；此时右边空出一个位置；然后从左边找到一个大于参照值的数，
//填到右边的空位，此时左边空出一个位置......不断左右找数填坑，最终左右遍历坐标相等时的坑位就是参照值的位置。
public int sort(int[] A,int left,int right){
int i=left;
int j=right;
int temp=A[i];
while(i<j){
while(j>i && A[j]>=temp){//从右往左找到第一个小于参照值的元素
--j;
}
if(j>i){//根据元素位置判断是否可以作出交换,是i则把参照值交换到右边，使找到的元素处于参照值左边，然后移动左边下标
A[i++]=A[j];
}
while(i<j && A[i]<=temp){
++i;
}
if(i<j){
A[j--]=A[i];
}
}
if(i==j){
A[i]=temp;//当左右遍历下标相等时，这个位置就是参照值的位置：左边都是小于它的数，右边都是大于它的数
}
return i;
}
}
三：希尔排序==每个步长的排序都从A[K]开始遍历，对每个元素（下标j），与j-k位比较交换，交换后修改j=j-k继续比较交换，插入到合适位置；遍历完后修改步长k；
第一轮：初始步长为k，从A[k]开始遍历，每个元素A[i]与前面A[i-n*k]元素进行插入排序（比较交换到合适位置）；
第二步：--k，从A[k]开始遍历，每个元素A[i]与前面A[i-n*k]元素进行插入排序（比较交换到合适位置）；
。。。
第k步：k==1，从A[1]开始遍历整个数组执行一次插入排序。
复杂度计算：T=(n-k)+(n-k+1)+...+n，T取决于k的选取，上限为O（n^1.5）。
public class ShellSort {
public int[] shellSort(int[] A, int n) {
//如果数组为空或数组只有一个元素，直接返回
if(A==null||n<2){
return A;
}
//令步长为n/2
int k=n/2;
//对步长k进行遍历
while(k>=1){
//每个步长的排序都从A[K]开始遍历
for(int i=k;i<=n-1;++i){//遍历k~n-1的元素
//对每个元素(下标j)，与j-k位比较交换，交换后修改j=j-k继续比较交换，插入到合适位置
for(int j=i;j>=k;){//下标j负责执行当前元素与向前k位的元素进行比较交换.注意是 j>=k，因为比较时front=j-k就可以取到0了。
int front=j-k;
if(front>=0){//检查j的前k位是否越界
//如果当前元素小于前面第k个元素，则交换二者位置，同时修改当前元素下标j为j-k；继续与前面第k个进行比较
if(A[j]<A[front]){
int temp=A[front];
A[front]=A[j];
A[j]=temp;
j=front;
}else{//一旦交换到j大于j-k下标的元素，则说明当前元素已经插入到当前步长的合适位置。跳出循环，遍历下一元素
break;
}
}
}
}
--k;//修改步长
}
return A;
}
}
四：堆排序==由数组建立最大堆（从小塔堆出大塔），然后重复：取堆头值并删除堆头（A[0]与A[len]交换，无序数组长len减一）；调整堆成为最大堆（移动金字塔）；当堆中只有一个元素时，该数组已经有序（因为每次把堆头移到构造堆的数组的末尾，而构造堆的数组是基于原数组的无序部分的）
复杂度计算：T=t(n)(建堆）+n（取堆头n次）*logn（每次调整堆需要logn）=O（n*logn）
堆的定义：n个长数组array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)
① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；
② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；//区分开大根堆和BST！大根堆是父节点大于两子结点即可。
调整方法为：当前节点与左右儿子（2r+1/2r+2）比较，若小于左右儿子中的较大者，则交换；此时，为了维持子堆的是最大堆，继续对交换后的结点与左右儿子比较交换...直到一个处于一个其左右儿子均小于它的位置。我用“移动金字塔”来描述这个过程——从要调整的结点p开始，p与其左右儿子p1、p2构成一个金字塔，如果p小于p1、p2中的较大者，则交换使得三者中最大者处于塔尖；然后移动金字塔，令p继续处于塔尖，继续与其新的左右儿子p1、p2的较大者比较......直到一个位置，p处于塔尖，p1、p2均小于p，则p处于合适位置了。
建立最大堆：
我们来看建立一个最大堆的右下角的第一个大根子堆：最后一个叶子结点为n-1，由公式 父节点=floor[（r-1）/2] 得父节点下标 （n-2)/2，比较父节点与左右儿子（叶子），把三者之间最大者交换成为父节点。构成了整个最大堆的最底层的一个小大根堆；
我们知道最大堆在数组中是逐层存放的，所以最后一个叶子结点的父节点(n-2)/2在数组中就是划分中间结点与叶子结点的分界；
我们从 (n-2)/2 倒过来逐个结点进行调整（建立小金字塔），就实现了逐层建立起最大堆的过程（从最底层金字塔开始堆叠出完成的大金字塔）；
public class HeapSort {
public int[] heapSort(int[] A, int n) {
for(int i=(n-2)/2;i>=0;--i){//从最后一个中间结点开始，倒着逐层建立最大堆
siftdown(A,i,n);
}
//从最大堆取数：每次把堆头与无序数组最后一个元素交换;然后无序数组长度减一，把堆头从无序数组建立的堆中调整好位置
for(int i=0;i<n;++i){
swap_head(A,n-i);
siftdown(A,0,n-i-1);
}
return A;
}
public void siftdown(int[] A,int i,int len){
int curr_father=i;//要调整的结点作为父节点
while(curr_father*2+1<len){//当至少一个儿子存在时
int left=curr_father*2+1;
int max_of_son=left;//记录儿子中较大者,如果没有右儿子的情况下默认是左儿子
if(left!=len-1){//由于是完全二叉树，如果左儿子不是数组最后一个结点，则绝对有右儿子
//比较左右儿子，取较大者
int right=left+1;
max_of_son=(A[left]>A[right]?left:right);
}
//比较父节点与儿子较大者,父节点大于儿子中较大者，则位置适合，调整结束;否则交换位置，并更新待调整结点下标为原max_of_son的下标，移动金字塔，该结点仍然为curr_father
if(A[curr_father]>A[max_of_son]){
break;
}else{
int temp=A[curr_father];
A[curr_father]=A[max_of_son];
A[max_of_son]=temp;
curr_father=max_of_son;
}
}
}
public void swap_head(int[] A,int len){
int temp=A[0];
A[0]=A[len-1];
A[len-1]=temp;
}
}