Java之排序（下）快排，归并，堆排

快速排序

排序思想：
分而治之，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。
**时间复杂度：**最好情况下：O（nlog2n） 最坏情况下：O（n^2）
空间复杂度： O（log2n）
稳定性： 不稳定
优点： 极快，数据移动少
选取基准的方式
1、固定位置选取基准法（定义最左边low的为基准）
2、随机选取基准法（用随机数随机选取基准）
3、三分取中法
注意！选取基准的方法可以和实现快排的方法结合使用。
优化方式
1、当待排序序列中，序列中的数字，少于一定的个数时，直接插入排序。

if(high-low+1 <= 10) {//当前序的长度小于一定长度时
            insertSort(array,low,high);//调用插排
            return;
        }

2、聚集相同基准元素法。（数组中数重复较多时，效率较高）将与基准相同的元素，聚集到基准的左右两边。

public static int[] Focus_Same_Num(int[] array, int low, int par, int high,
                                       int left, int right){//聚集相同基准元素法
        int par_right = par+1;//定义p_r的位置
        for (int i = par+1; i <= high; i++) {//从基准右边开始查找，查找的范围
            if(array[i] == array[par]) {//当元素相同时
                if(i != par_right) {//如果不相邻
                    swap(array,i,par_right);//交换元素
                    par_right++;//右移
                }else {//相邻时
                    par_right++;
                }
            }
        }
        right = par_right;//将p_r的值赋给right
        int par_left = par-1;//定义p_l的位置
        for (int i = par-1; i >= low; i--) {//从基准左边开始查找，查找的范围
            if(array[i] == array[par]) {//当元素相同时
                if(i != par_left) {//如果不相邻
                    swap(array,i,par_left);//交换元素
                    par_left--;//左移
                }else {//相邻时
                    par_left--;
                }
            }
        }
        left = par_left;//将p_l的值赋给left
        int[] tmp = new int[2];//定义一个长度为2的数组来存储与基准相同的数的
		                       //最左最右的下标
        tmp[0] = left;//存储最左边与基准相同的下标
        tmp[1] = right;//存储最右边与基准相同的下标
        return tmp;//返回数组，用于下次查找
    }

核心代码解析
进行第一次快排

public static int partion(int[] array,int low,int high) {//进行一趟快速排序
	                                                         //时间复杂度O(n)
        int tmp = array[low];//采用固定位置选取基准法，先将l下标的值赋值给tmp，
		                     //即就是基准
        while(low < high) {//说明至少存在两个元素
            while((low < high) && array[high] >= tmp) {//当l<h,并且h下标的值不小于tmp
                high--;//h往前挪一位
            }
            if(low >= high) {//说明此时只有一位元素
                break;
            }else {//如果h下标的值小于tmp
                array[low] = array[high];//将h下标的值赋值给l下标
            }
            while ((low < high) && array[low] <= tmp) {//当l<h,并且l下标的值不大于tmp
                low++;//l往前挪一位
            }
            if(low >= high) {//说明此时只有一位元素
                break;
            }else {//如果l下标的值大于tmp
                array[high] = array[low];//将l下标的值赋值给h下标
            }
        }
        array[low] = tmp;//将选取的基准回归原位
        return low;
    }

实现快排的方式
都是在一趟快排之后进行
1、用递归实现快排（采用的是固定位置选取基准）

public static void quick(int[] array,int low,int high) {//采用递归的方法
        int par = partion(array,low,high);//执行完partion后当前序列已经分为两个部分  
        if(par > low+1) {//左边有两个元素以上包含两个元素
            quick(array,low,par-1);//调用本身，从基准的左边继续排序，递归时间复杂度O(log2N)
        }
        if(par < high-1) {//右边有两个元素以上包含两个元素
            quick(array,par+1,high);//调用本身，从基准的右边继续排序
        }
    }

2、非递归实现快排（采用的是固定位置选取基准，借用了栈来实现）

public static void quickSort(int[] array) {//采用非递归的方法
        int low = 0;//第一次l的位置
        int high = array.length-1;//第一次h的位置
        int par = partion(array,low,high);//进行一趟的快速排序
        int len = (int)(log((double)array.length)/log((double)2));//数组的大小，
		                             //可以等于array的大小，也可准确它的大小，如上
        int[] stack = new int[2*len];//定义一个数组来存放进栈的下标
        int top = 0;//栈的下标
        if(par > low +1) {//说明左边有两个数据
            stack[top++] = low;//将l的下标入栈
            stack[top++] = par-1;//将基准-1的下标入栈
        }
        if(par < high-1) {//说明右边有两个数据
            stack[top++] = par+1;//将基准+1的下标入栈
            stack[top++] = high;//将h的下标入栈
        }
        while(top > 0) {//当栈不为空时，进行出栈
            high = stack[--top];//将h指向先出栈的下标
            low = stack[--top];//将l指向后出栈的下标
            par = partion(array,low,high);//进行一次快排
			//继续判断基准的左右是否有两个数据
            if(par > low +1) {
                stack[top++] = low;
                stack[top++] = par-1;
            }
            if(par < high-1) {
                stack[top++] = par+1;
                stack[top++] = high;
            }
        }
    }

画图详解

归并排序

排序思想：
将待排序的元素序列分成若干长度相等的子序列（子序列内的元素个数可为2^n,n =0,n++），对每一个子序列进行排序，然后将他们逐渐合并成一个序列。
**时间复杂度：**最好情况下：O（nlog2n） 最坏情况下：O（nlog2n）
空间复杂度： O（n）
稳定性： 稳定
优点： 效率较高
缺点： 比较爱占内存
核心代码解析

public static void merge(int[] array,int gap) {//归并段内的排序
        int[] tmpArr =  new int[array.length];//定义一个备用数组
        int i = 0;//tmpArr的下标
		//定义四个位置变量
        int start1 = 0;
        int end1 = start1+gap-1;
        int start2 = end1+1;
        int end2 = start2+gap-1 < array.length ? start2+gap-1 : array.length-1;

        while (start2 < array.length) {//肯定有两个对归并段
            //两个归并段都有数据
            while(start1 <= end1 && start2 <= end2) {//当归并段内至少有两个数据时
                if(array[start1] < array[start2]) {//s1的值小于s2时
                    tmpArr[i++] = array[start1++];//将s1内的值赋予tmpArr,两个下标都向前+1
                }else {//s1的值大于s2时
                    tmpArr[i++] = array[start2++];//将s2内的值赋予tmpArr,两个下标都向前+1
                }
            }
            while (start1 <= end1) {//当归并段内只有一个数据时
                tmpArr[i++] = array[start1++];//将s1内的值赋予tmpArr,两个下标都向前+1
            }
            while (start2 <= end2) {//同上
                tmpArr[i++] = array[start2++];
            }//一个归并段排序结束
            //确定下一个归并段的开始和结束位置
            start1 = end2+1;
            end1 = start1+gap-1;
            start2 = end1+1;
            end2 = start2+gap-1 < array.length ? start2+gap-1 : array.length-1;
        }
        while (start1 < array.length) {//只有一个归并段时
            tmpArr[i++] = array[start1++];//将s1内的值赋予tmpArr,两个下标都向前+1
        }
        //array = tmpArr.clone();
        for (int j = 0; j < tmpArr.length; j++) {
            array[j] = tmpArr[j];//将备用数组中的值拷贝到原数组
        }
    }
    public static void mergeSort(int[] array) {//归并排序
        for (int i = 1; i < array.length; i *= 2) {//定义归并段的大小
            merge(array,i);
        }
    }

画图详解

堆排序

什么是堆？
答：堆通常是一个可以被看作是一棵树的数组对象。有大根堆小根堆两种（如下图）

排序思想：
利用堆进行排序，将待排序的序列造成一个大堆。然后，整个序列的最大值就是堆顶元素（根结点），将它移走，即与堆末尾的元素进行交换，然后再依次重新建堆，如此反复执行，即可完成排序。
时间复杂度：
最好情况下：O（nlog2n） 最坏情况下：O（nlog2n）
空间复杂度： O（1）
稳定性： 不稳定
优点： 用于较大的序列时，性能较好
核心代码解析

    public static void adjust(int[] array,int start,int end){//建立大根堆
        int tmp = array[start];//从父节点开始交换
        for (int i = 2*start+1; i <= end ; i = 2*i+1) {
            //判断是否有右孩子，如果有，找到左右孩子的最大值。
            if((i < end) && array[i] < array[i+1]) {
                i++;
            }//肯定i是最大值的下标
            if(array[i] > tmp) {//当i号下标的值大于tmp为的值时，两者进行交换
                array[start] = array[i];
                start = i;
            }else {
                break;//直接跳出
            }
        }
        array[start] = tmp;
    }
    public static void heapSort(int[] array) {//堆排序
        for (int i = (array.length-1-1)/2; i >= 0 ; i--) {//(array.length-1-1)/2
		                                                  //代表最后一个小堆的父节点
            adjust(array,i,array.length-1);
        }//大根堆已经建立，大根堆的时间复杂度：O(n*log2n)
		 //将大根堆的0号下标的值与最后一个值进行交换
        int tmp = 0;
        for (int i = 0; i <= array.length-1; i++) {
            tmp = array[0];
            array[0] = array[array.length-1-i];
            array[array.length-1-i] = tmp;
            adjust(array,0,array.length-1-i-1);//完成一次大根堆交换，后面的最后一个
			                                   //就已经有序了，便不用再次排序了，其余
											   //的继续建立大根堆
        }
    }

画图详解