常见排序

 排序算法的根本目的就是最大可能，减少比较次数来排序。如冒泡。浪费了很多次比较的结果。所以出现快排。只是调整下位置。下次排序就只要排2部分的其中一部分。

最优和稳定的解当然是每次比较，就稳定少一半。所以所有的排序目的就是如何每次都稳定的求出一半大，一半小。

有空加上堆排：1.先建立大堆，往上冒泡，下来的泡再一直往下。  2,2选1，后插。

排序可以复习下。本身代码简洁。

//常见的排序，冒泡，归并，快排。
    public static class sort
    {
        public static int[] getData()
        {
            int[] ret=new int[]{5,2,9,-3};
            return ret;
        }
        
        //冒泡,浪费了很多次比较，每次循环，没有为下一次循环提供帮助。时间复杂度 n平方
        public static void popo()
        {
            int[] data=getData();
            int tempMax=0;
            for(int i=0;i<data.length;i++)
            {
                int tempIndex=i;
                for(int h=i+1;h<data.length;h++)
                {
                    if(data[h]>data[tempIndex])
                    {
                        tempIndex=h;
                    }
                }
                tempMax=data[tempIndex];
                data[tempIndex]= data[i];
                data[i]=tempMax;
            }
            printLog(data);
        }
        
        public static void printLog(int[] ret)
        {
            for(int i=0;i<ret.length;i++)
            {
                LSLog.printLine(ret[i]+"", 1);
            }
        }
        
        //归并排序， 典型的分治：问题太大。那么就把问题一拆为二，结果分别排序好的组合起来，当为1时，不需要拆和排序。是最小问题。
        public static void merginSort()
        {
            int[] data=getData();
            if(data.length>=2)
            {
                mergin(data, 0, data.length-1);
            }
            printLog(data);
        }
        
        //分解：中分from to.合并2个。  最小问题：1个数字。不用处理。
        private static void mergin(int[] data,int from,int to)
        {
            int lengto=to-from+1;
            int half=lengto/2;
            LSLog.printLine("from:"+from+".to:"+to+".half:"+half, 1);
            assert(half>=0):"???";
            if(lengto==1)
            {
                
            }
            else
            {
                mergin(data, from, from+half-1);
                mergin(data, from+half, to);
                int dynamicFrom=from;
                for(int i=half;i<=to;i++)
                {
                    for(int h=dynamicFrom;h<=half-1+i-half;h++)
                    {
                        if(data[i]<data[h])
                        {
                            int tempMin=data[i];
                            System.arraycopy(data, h, data, h+1,i-h);
                            data[h]=tempMin;
                            dynamicFrom=h+1;
                        }
                    }
                }
            }
        }
        
        
        
        
        //冒泡实在不行，浪费了很多次比较结果。  快排聪明点，每次比较，做点额外工作，左右按大小分边，所以下次查找大或小，就少了一半。
        public static void QuickSort()
        {
            int[] data=getData();
            QSort2(data, 0, data.length-1);
            printLog(data);
        }
        
        //代码简洁，效率稍低：碰到大的就后插。
        private static void QSort2(int[] data,int from ,int to)
        {
            if(to-from<=0){}
            else if(to-from==1)
            {
                if(data[from]>data[to])
                {
                    swapINT(data, from, to);
                }
            }
            else 
            {
                int CompareIndex=getCompareIndex(data, from, to);
                swapINT(data, to, CompareIndex);
                CompareIndex=to;
                for(int i=0;i<CompareIndex;i++)
                {
                    if(data[i]>data[CompareIndex])
                    {
                        int tempBigger=data[i];
                        System.arraycopy(data, i+1, data, i, CompareIndex-i);//modify+1
                        data[CompareIndex]=tempBigger;
                        CompareIndex--;//modify
                        i--;
                    }
                }
                QSort2(data,from, CompareIndex-1);
                QSort2(data,CompareIndex+1, to);//modify
            }
        }
        
        
        //高效版，处理边界麻烦，不小心就错：一大一对调。
        private static void QSort(int[] data,int from ,int to)
        {
            //assert(from<to):"from>to?";
            if(to-from<=0){}
            else if(to-from==1)
            {
                if(data[from]>data[to])
                {
                    swapINT(data, from, to);
                }
            }
            else 
            {
                boolean isSorted=false;
                int centerIndex=getCompareIndex(data, from, to);
                swapINT(data, to, centerIndex);
                int beginCheckIndex=from;
                int endCheckIndex=to-1;
                int lastCenter=0;
                while (!isSorted)
                {
                    for(beginCheckIndex=beginCheckIndex;beginCheckIndex<=endCheckIndex;beginCheckIndex++)
                    {
                        if(data[beginCheckIndex]>data[to])
                        {
                            break;
                        }
                    }
                    if(beginCheckIndex>endCheckIndex)
                    {
                        isSorted=true;
                        lastCenter=to;
                    }
                    else if(beginCheckIndex==endCheckIndex)
                    {
                        swapINT(data, beginCheckIndex, to);
                        lastCenter=beginCheckIndex;
                        isSorted=true;
                    }
                    else 
                    {
                        for(endCheckIndex=endCheckIndex;endCheckIndex>beginCheckIndex;endCheckIndex--)
                        {
                            if(data[endCheckIndex]<data[to])
                            {
                                break;
                            }
                        }
                        if(endCheckIndex==beginCheckIndex)
                        {
                            isSorted=true;
                            swapINT(data, beginCheckIndex, to);
                            lastCenter=beginCheckIndex;
                        }
                        else
                        {
                            swapINT(data, beginCheckIndex, endCheckIndex);
                            isSorted=false;
                            beginCheckIndex++;
                            endCheckIndex++;
                        }
                    }
                    
                QSort(data, from, beginCheckIndex-1);
                QSort(data, beginCheckIndex+1, to);
                //{2,6,9,1,4,0,3,5,7,8};
                // |               |
                }
            }
        }
        
        
        
        private static void swapINT(int[] data,int from ,int to)
        {
            int temp=data[from];
            data[from]=data[to];
            data[to]=temp;
        }
        
        //做成了求推理题目
        private static int getCompareIndex(int[] data,int fromIndex,int toIndex)
        {
            int ret=0;
            int centerIndex=(fromIndex+toIndex)/2;
            //choose bigger
            ret=data[fromIndex]>data[centerIndex]?fromIndex:centerIndex;
            int templeft=data[fromIndex]<=data[centerIndex]?fromIndex:centerIndex;
            //choose smaller
            ret=data[ret]<data[toIndex]?ret:toIndex;
            //choose bigger
            ret=data[ret]>data[templeft]?ret:templeft;
            
            return ret;
        }
        
    }