【数据结构】7大基于比较的排序（冒泡排序、快速排序、归并排序）

五.冒泡排序

思想：冒泡排序就是两个相邻的元素之间进行比较，把最大的冒到最后，一般是比较好理解的

//冒泡排序
    public static void bubbleSort(int [] array){
        for(int i=0;i<array.length-1;i++){
            boolean treated=true;
            for(int j=0;j<array.length-i-1;j++){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    treated=false;
                }
            }
            if(treated==true){
                break;
            }
        }
    }

六.快速排序

其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

分割的过程：四种方法

1）左右往中间靠

a.hover  b.挖坑法

2）前后遍历

a,前后遍历  b.把基准值单独处理

 //快速排序
    public static void quickSort(int [] array){
        quickSortInternal(array,0,array.length-1);
    }
    public static void quickSortInternal(int [] array,int left,int right){
        if(left>=right){
            return;
        }
        //1.确定基准值：array[right]作为基准值
        //2.遍历，小的在左，大的在右
        //int pivotIndex1=partioion1(array,left,right);
        //int pivotIndex2=partioion2(array,left,right);
        //int pivotIndex3=partition3(array,left,right);
        int [] indices=partition4(array,left,right);
        //分出两个小区间
        //[left,pivotlndex-1]
        //[pivotlndex+1,right]
        //quickSortInternal(array,left,pivotIndex1-1);
        //quickSortInternal(array,pivotIndex1+1,right);
        //quickSortInternal(array,left,pivotIndex2-1);
        //quickSortInternal(array,pivotIndex2+1,right);
        //quickSortInternal(array,left,pivotIndex3-1);
        //quickSortInternal(array,pivotIndex3+1,right);
        quickSortInternal(array,left,indices[0]-1);
        quickSortInternal(array,indices[1]+1,right);
    }
    public static int partioion1(int [] array,int left,int right){
        int pirot=array[right];
        int great=right;
        int less=left;
        while(less<great){
            while(less<great&&array[less]<=pirot){
                less++;
            }
            while(less<great&&array[great]>=pirot){
                great--;
            }
            swap(array,less,great);
        }
        swap(array,less,right);
        return less;
    }
    public static int partioion2(int []array,int left,int right){
        int pirot=array[right];
        int great=right;
        int less=left;
        while (less < great) {
            while(less<great&&array[less]<=pirot){
                less++;
            }
            array[great]=array[less];
            while(less<great&&array[great]>=pirot){
                great--;
            }
            array[less]=array[great];
        }
        array[less]=pirot;
        return less;
    }
    public static int  partition3(int [] array,int left,int right){
        int less=left;
        int pirot=array[right];
        for(int i=left;i<right;i++){
            if(array[i]<pirot){
                swap(array,i,less);
                less++;
            }
        }
        swap(array,less,right);
        return less;
    }
    public static int [] partition4(int [] array,int left,int right){
        int pirot=array[right];
        int great=right;
        int i=left;
        int less=left;
        while(i<great){
            if(array[i]==pirot){
                i++;
            }
            if(array[i]<pirot){
                swap(array,i,less);
                i++;
                less++;
            }
            else{
                while(i<great&&array[great]>pirot){
                    great--;
                }
                swap(array,i,great);
            }
        }
        return new int [] {less,great-1};
    }

非递归的做法：

自己只用栈记录，待排序区间的左右边界

再利用分割的方法

//快速排序非递归
    public static void quickSortNoR(int [] array){
        Stack<Integer> stack=new Stack<>();
        stack.push(array.length-1);
        stack.push(0);
        while(!stack.isEmpty()){
            int left=stack.pop();
            int right=stack.pop();
            if(left>=right){
                continue;
            }
            int pivotIndex=partition(array,left,right);
            //[left,pivotIndex-1]
            //[pivotIndex+1,right]
            stack.push(right);
            stack.push(pivotIndex+1);
            stack.push(pivotIndex-1);
            stack.push(left);
        }
    }

七.归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

具体实现：

合并两个有序数组的过程

0.平均切分待排序区间，如果待排序区间的左右两个小区间已经有序，则，按照合并有序数组的方法，使最终区间有序

1.先找到中间位置，化分左右两个小区间，直到小区间长度==1或者<1

2.分治的思想，先排左右两个小区间

3.合并有序数组

    //归并排序
    //左闭右开
    public static void mergeSort(int [] array){
        mergeSortInternal(array,0,array.length);
    }
    public static void mergeSortInternal(int[] array, int low, int high) {
        if(low+1>=high){
            return;
        }
        int mid=(high+low)/2;
        //[low,mid)
        //[mid,high)
        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid,high);
        merge(array,low,mid,high);
    }
//合并两个数组
    public static void merge(int [] array,int low,int mid,int high){
        int length=high-low;
        int [] extra=new int [length];
        int iLeft=low;
        int iRight=mid;
        int iExtra=0;
       while(iLeft<mid&&iRight<high){
           if(array[iLeft]<=array[iRight]){
               extra[iExtra++]=array[iLeft++];
           }
           if(array[iLeft]>array[iRight]){
               extra[iExtra++]=array[iRight++];
           }
       }
       while(iLeft<mid){
           extra[iExtra++]=array[iLeft++];
       }
       while(iRight<high){
           extra[iExtra++]=array[iRight++];
       }
       for(int i=0;i<length;i++){
           array[low+i]=extra[i];
       }
    }

非递归的做法：

先使数组中的每个元素为一个区间，然后两两合并为一个区间，再以合并好的区间为一个区间，再两两合并，如下图所示

//非递归归并排序
    public static void mergeSortNoR(int [] array){
        for(int i=1;i<array.length;i=i*2){
            for(int j=0;j<array.length;j=j+2*i){
                int low=j;
                int mid=j+i;
                int high=mid+i;
                if(mid>=array.length){
                    continue;
                }
                if(high>array.length){
                    high=array.length;
                }
                merge(array,low,mid,high);
            }
        }
    }

 最后，对七种排序进行总结：