2020-03-22

【灵光一现】Hadoop中常用的两种排序-快排&归并

写在前面

众所周知，当执行一个完整的MR流程时，必然会经过快排和归并两种排序，可见这两种排序在日常使用中的重要性。于是，便有了这篇文章，以便捡起过去学过的知识。

冒泡排序

说到排序，最基础的便是冒泡排序，这可能是大多数人一开始最能写的排序，因为其方法过于暴力，所以查询效率通常情况下较慢，时间复杂度最高为n^2，最好能为n，但是相对的，他也较为稳定

思路

数组从前到后依次两两排序，直到最后一位数为一轮，去掉最后一个数（每一轮排序会把数组最大值送到最后一位）开始再重新进行下一轮排序
代码如下

package com.practice.bubblesort1;

public class BubbleSort1 {
    private static int count = 0;
    public static void arrToString(double[] arr , String status){
        String str = "";
        for (double word : arr) {
            str = str + word + "\t";
        }
        System.out.println("当前数组状态："+status+"\t"+str);

    }

    public static void BubbleSort(double[] arr){
        for (int i = 0;i<arr.length;i++){
            for(int j = 0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    double tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
                count++;
            }
        }
    }

    public static void main(String[] args) {
        double[] arr = {21,43,5,67,11,87,33,2};
        arrToString(arr,"UnSorted");
        System.out.println("Sorting.............");
        BubbleSort(arr);
        arrToString(arr,"Sorted");
        System.out.println("循环次数："+count);
    }

}

结果如下

快速排序

快排是冒泡的改进，有很高的上限，最快以及平均的时间复杂度能到o(nlog2n)
，最坏情况则是n^2,稳定性也较差。
这里解释下稳定性：
所谓稳定性是指待排序的序列中有两元素相等,排序之后它们的先后顺序不变.假如为A1,A2.它们的索引分别为1,2.则排序之后A1,A2的索引仍然是1和2。稳定也可以理解为一切皆在掌握中,元素的位置处在你在控制中.而不稳定算法有时就有点碰运气,随机的成分.当两元素相等时它们的位置在排序后可能仍然相同。但也可能不同。是未可知的。
举个例子：5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱

思路

1.一般选择数组第一个数为中枢点，中枢点是基准，或许位置会变，但值是不变的，所以在写代码的时候要记得每次循环定好中枢点的值
2.从末尾开始从右向左读数，直到找到一个小于中枢点的数，标记其位置
3.从起点开始向右读书，直到找到一个大于中枢点的数，标记其位置
4.交换两点，总结就是，比中枢点小的放左边，比中枢点大的放右边。
5.至此，重新定位中枢点位置，递归上述步骤，直到左边的指针大于等于右边的指针，此时即表示所有数都已排序过

ps:当数组个数为奇数时可考虑选中间值为中枢点，可有效提升计算效率

代码如下：

package com.practice.quicksort1;

public class QuickSort1 {
    private static int count = 0;
    public static void arrToString(double[] arr,String status){
        String str = "";
        for (double word : arr) {
            str = str + word + "\t";
        }
        System.out.println("当前状态："+status+"\n"+ str);
    }

    public static void QuickSort(double[] arr,int left, int right){
        if(left>=right){
            return;
        }
        int i = left;
        int j = right;
        double key = arr[left];

        while(i<j){
            while(i<j&&arr[j]>=key){
                j--;
            }
            while(i<j&&arr[i]<=key){
                i++;
            }
            double tmp;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            count++;
        }
        arr[left] = arr[i];
        arr[i] = key;

        QuickSort(arr,left,i-1);
        QuickSort(arr,i+1,right);


    }

    public static void main(String[] args) {
        double[] arr = {21,43,5,67,11,87,33,2};
        arrToString(arr,"0");
        System.out.println("ing...................");
        QuickSort(arr,0,arr.length-1);
        arrToString(arr,"1");
        System.out.println("count:"+count);
    }
}

结果如下：

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的典型利用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。是一种牺牲空间换取时间的算法，算法稳定，平均时间复杂度为O(Nlog2N)同时最坏情况也是这个速度

思路

1.将待排序数据不断对半切分，直至不可再切
2.切分后不断由下往上进行有序合并操作
合并时：
3.申明临时数组，临时指针指向临时数组第一位，以及两个指针分别指向数组第一位和中间值的后一位
4.不断比较两个指针，通过临时指针将较小数存到临时数组后，对应选到的指针和临时指针都朝后移一位，直到左指针指到中间数，或者右指针指到最后一位，即不能继续后移
5.将还没指到终点的指针继续后移，依次将指到的数存到临时数组中
6.将临时数组覆盖写入排序数组

代码如下：

package com.practice.mergesort1;

public class MergeSort1 {
    private static int count = 0;
    public static void arrToString(double[] arr,String status){
        String str = "";
        for (double word : arr) {
            str = str + word + "\t";
        }
        System.out.println("当前状态："+status+"\n"+ str);
    }
    public static void merge(double[] arr,int left,int right,int mid){
        double[] tmp = new double[right-left+1];
        int k = 0;
        int l = left;
        int r = mid+1;
        while(l<=mid&&r<=right){
            if(arr[l]<=arr[r]){
                tmp[k++] = arr[l++];
            }else{
                tmp[k++] = arr[r++];
            }
        }
        while(l<=mid){
            tmp[k++] = arr[l++];
        }
        while(r<=right){
            tmp[k++] = arr[r++];
        }
        //覆盖
        for(int i = 0;i<tmp.length;i++){
            arr[i+left] = tmp[i];
        }
        count++;
    }
    public static void sort(double[] arr ,int left,int right){
        int mid = (left+right)/2;
        if(left<right){
            sort(arr,left,mid);
            sort(arr,mid+1,right);

            merge(arr,left,right,mid);
        }

    }
    public static void main(String args[]){
        double arr[]={21,43,5,67,11,87,33,2};
        arrToString(arr,"UnSorted");
        System.out.println("Sorting.......");
        sort(arr,0,arr.length-1);
        arrToString(arr,"Sorted");
        System.out.println("循环次数："+count);
    }
}