能带你起飞的【数据结构】成王第十四篇:七大排序2

基准值的选择

1.选择边上（左或者右）

2.随机选取基准法:有可能每次随机的数据,作为基准的时候,也会出现单分支情况.

需要考"人品"

3.几数取中（例如三数取中）：array[left], array[mid], array[right] 大小是中间的为基准值

4.把和基准相同的数据,从两边,移到跟前来

5.利用直接插入排序,越有序越快的规则,来进行优化

第三种是最常用的做法,我们的重点是第三种

什么是几数取中?

例如上图,我们要取中间值,

中间值不是指mid下标的值

好比第一行的中间值是left下标的值

第二行的中间值是mid下标的值

我们拿这个7作为找基准的方式 

如何知道三个下标所对应的值哪个是中间大小呢

 假设不管mid,先比较start和end的大小

代码实现:

 
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);

    }

    public static void quick(int[] array, int start,int end){
        if(start >= end){
            return;
        }
        //1.找基准之前,我们找到中间大小的值-使用三数取中法
        int midValIndex = findMidValIndex(array,start,end);
        swap(array,start,midValIndex);

        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);

    }
    private static int findMidValIndex(int[] array, int left,int right){
        int mid = left + ((right - left) >>> 1);
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[left]){
                return left;
            }else if (array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }


    }

    private static int partition(int[] array, int start,int end){
        int tmp = array[start];
        while(start < end){
            while(start < end && array[end] >= tmp){
                end--;
            }
            //end下标就遇到了小于tmp的值
            array[start] = array[end];
            while(start < end && start <= tmp){
                start++;
            }
            //start下标就遇到了>tmp的值
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;

    }
    public static void main(String[] args) {
        int[] array = {12,5,18,10,4,12};
        quickSort(array);
        System.out.println(Arrays.toString(array));

    }

第一步还是先找基准

找完之后我们需要借助栈

 然后把左边区间的数对和右边区间的数对放到栈里面

左边区间left下标也就是0下标放到站里面,right下标也就变成了基准减一是4下标

然后再把右区间的left下标也就是基准下标加一,6下标,和right下标9下标放到栈里面

 

接下来弹出栈顶的两个元素

此时start对应的就是6下标,end对应的就是9下标

 

 弹完之后继续在6下标和9下标区间找基准

 此时就找到了基准9

然后再把6下标和7下标放到栈里面

 右边放不放呢,此时发现右边之后有一个9下标数据了,他是有序了,不放,所以说碰到左边或者右边都只剩一个数据的时候都不往栈里放了,那怎么知道左边或者右边只剩一个数据了呢,就看基准的位置,此时基准的下标是8,right的下标是9,当基准值不

依次往下类推,每弹两个元素就找基准

总结:

1.划分之后,把左右的数对都放到栈当中.前提:Pivot左边有两个元素,右边有两个元素

代码实现

private static int partition(int[] array, int start,int end){
        int tmp = array[start];
        while(start < end){
            while(start < end && array[end] >= tmp){
                end--;
            }
            //end下标就遇到了小于tmp的值
            array[start] = array[end];
            while(start < end && start <= tmp){
                start++;
            }
            //start下标就遇到了>tmp的值
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;

    }
    public static void quickSort2(int[] array){
        Stack stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array,left,right);
        if(pivot > left + 1){
            stack.push(left);
            stack.push(pivot -1);
        }

        if(pivot < right - 1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();

            pivot = partition(array,left,right);
            if(pivot > left + 1){
                stack.push(left);
                stack.push(pivot -1);
            }

            if(pivot < right - 1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {12,5,18,10,4,12};
        quickSort2(array);
        System.out.println(Arrays.toString(array));

    }

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

思路

 找到中间位置之后,先递归左边,再递归右边

 代码实现

 
    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length-1);

    }
    private static void mergeSortInternal(int[] array, int left ,int right){
        if (left >= right){
            return;
        }
        int mid = left + ((right - left)>>>1);
        mergeSortInternal(array,left,mid);
        mergeSortInternal(array,mid+1,right);
        //递归结束进行归并
        merge(array,left,mid,right);

    }
    public static void merge(int[] array, int left ,int mid,int right){
        int[] tmp = new int[(right - left) + 1];
        int k = 0;
        int s1 = left;
        int end1 = mid;

        int s2 = mid + 1;
        int end2 = right;

        while (s1 <= end1 && s2 <= end2){
            if(array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }
        while(s1 <= end1){
            tmp[k++] = array[s1++];
        }
        while (s2 <= end2){
            tmp[k++] = array[s2++];
        }
        //拷贝tmp数组的元素,放入原来的数组array当中
        for (int i = 0; i  

每组从一个数据变成每组两个数据,在变成每组四个数据

定义一个I下标遍历原来这个数组

int left = i;

int mid = left + gap -1;

int right = mid + gap;

代码实现

  public static void merge(int[] array, int left ,int mid,int right){
        int[] tmp = new int[(right - left) + 1];
        int k = 0;
        int s1 = left;
        int end1 = mid;

        int s2 = mid + 1;
        int end2 = right;

        while (s1 <= end1 && s2 <= end2){
            if(array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }
        while(s1 <= end1){
            tmp[k++] = array[s1++];
        }
        while (s2 <= end2){
            tmp[k++] = array[s2++];
        }
        //拷贝tmp数组的元素,放入原来的数组array当中
        for (int i = 0; i = array.length){
                    mid = array.length -1;
                }
                int right = mid + gap;
                if (right >= array.length){
                    right = array.length - 1;
                }
                //下标确定之后进行排序
                merge(array,left,mid,right);

            }
            gap *= 2;
        }
    }
    public static void main(String[] args) {
        int[] array = {1,11,3,4,456,6,7};
        mergeSort3(array);
        System.out.println(Arrays.toString(array));

    }

对这一组数据从小到大排序

首先这些数字都是十进制的

搞十个桶

 首先,先以个位数字是几,就放到几号桶

 我们把这些桶看做队列,先入的先出,比如170先放进去的,先出来

然后从0号桶开始一个一个往外出

此时我们发现,个位数有序了,接下来再以十位数是几就往几号桶里放

 

 此时十位上有序了

然后再以百位上数字是几就往几号桶里放

此时就有序了 

假设此时我们已经确定了计数数组的大小

一开始计数数组里面都是0

A数组的0下标是2,A数组下标里面的内容就是相当于C数组的下标

因为A数组的0下标里面的内容是2,所以C数组2下标里面的内容加1

A数组的1下标里面的内容是5,所以C数组5下标里面的内容加1

以此类推

 

 总结:

1.确定计数数组的大小

2.这个计数排序,适合用在0-99范围

代码写法:

1.求数组的最大值maxVal,最小值minVal

maxVal - minVal + 1 = 数组长度

2.count [array[i - minVal]] :计数数组的下标

代码实现

    public static void couningSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < minVal){
                minVal = array[i];
            }
            if(array[i] > maxVal){
                maxVal = array[i];
            }
        }
        //说明已经找到最大值和最小值
        int[] count = new int[maxVal - minVal + 1];
        //统计array数组当中,每个数据出现的次数
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            count[index - minVal]++;
        }
        //说明,在计数数组当中,已经把array数组当中,每个数据出现的次数已经统计好了
        //接下来,只需要遍历计数数组,把数据写会array
        int indexArray = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i] > 0){
                array[indexArray] = i + minVal;
                count[i] --;
                indexArray++;
            }
        }
    }
    public static void main(String[] args) {
        int[] array = {1,11,3,4,456,6,7};
        couningSort(array);
        System.out.println(Arrays.toString(array));

    }