Java 中常見的排序算法

  其實小編是不太想寫關于java的相關文章，因為是這個編程語言實在是會用的人太多了，網上的博文數不勝數，沒必要在重復造輪子了，但是雖然java這門語言會用的人很多，但是會用、掌握、熟練、和精通可不是鬧著玩的，想要達到精通的級別，小編敢說，一個正規的開發公司能過達到精通java的開發人員屈指可數，所以小編這里就跳過關于java哪些簡單的API 、語法，直接給大家介紹一些相對提升能力，并且不是那么基礎的知識，說不定以后面試就會用到，尤其是排序，真的，不曉得為啥都喜歡在面試的時候出排序的題，實際大數據開發中真正手寫排序的還真不多，我想可能是各個面試官想要看到的是，各個應聘者是否能夠get到排序算法的精髓吧。
  好了，每次寫博客都要廢話一堆，自我檢討，但是不想改變，接下來小編介紹幾種創建的排序算法以及他們的java實現。

1. 冒泡排序

  原理：從第一個元素開始，和它相鄰的比較，如果前面一個元素大于后面一個元素，就把他們互換位置。
  原理圖：

   代碼實現：

public static void main(String[] args) {
        int arr[] = { 15, 16, 145, 91, 9, 5, 0 };
        int temp1=0;

        for(int i=0;i<arr.length-1;i++){  //控制循環次數：arr.length-1
            for(int j=0;j<arr.length-i-1;j++){  //控制比較次數：arr.length-i-1
                if(arr[j]>arr[j+1]){
                    temp1=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp1;
                }
            }
        }
}

   增強版冒泡排序：

public static void main(String[] args) {
        int arr[] = { 1,0,2,3,4,5,6,7,8 };
        int temp1;
        for(int i=0;i<arr.length-1;i++){  //控制循環次數：arr.length-1
            boolean flag=true;  //判斷內層循環是否執行
            for(int j=0;j<arr.length-i-1;j++){  //控制比較次數：arr.length-i-1
                if(arr[j]>arr[j+1]){
                    temp1=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp1;
                    flag=false;
                }
            }
            if(flag){  //如果內層循環的if一次都沒有執行，說明已經排序結束
                break;
            }
        }

2.選擇排序

  原理：從第一個位置開始，將他與后面的所有元素比較，如果前面大于后面的，就交換位置。
  原理圖：

  代碼實現：

public static void main(String[] args) {
    int arr[] = { 45,15,48,9,3,65,22 };
 for(int i=0;i<arr.length-1;i++){  //控制位置，從第一個位置開始，到倒數第二個位置
        for(int j=i+1;j<arr.length;j++){ //當前位置的下一個位置開始，與后面的所有比較
            if(arr[i]>arr[j]){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }

3. 插入排序

  原理：從第二個元素位置開始，將他與他之前的元素比較，如果比之前的元素小，就將他插入到，那個元素的前面。
  原理圖：

  代碼實現：

public static void main(String[] args) {
int arr[] = { 45, 15, 48, 9, 3, 65, 22 };
// 插入排序
int temp1;
for (int i = 1; i < arr.length; i++) { //從第二個數開始，一直到最后一個數
    for (int j = 0; j < i; j++) { //i之前的所有數，全部比較
        if (arr[i] < arr[j]) {
            temp1 = arr[i];
            for (int k = i; k > j; k--) { //將前面的數據把后面的覆蓋，從j開始，一直到i 
                arr[k] = arr[k - 1];
            }
            arr[j] = temp1;
        }
    }
}

4. 快速排序

  原理：先選取一個基準點，作用：基準點左側小于基準點的數據 基準點右側放的數據都是大于基準點的數據。基準點：最常用的基準點選第一個,最終一個大數組不停的進行查分 拆分的最終結果每個數組只有一個元素。
  原理圖：

解釋：大循環中有兩個循環，一個是從右往左，找比基準點小的，一個是從左往右找比基準點大的（找到之后，與基準點交換位置）。最終大循環，在left>=right時結束。
（2） 快排拆分：

解釋：使用遞歸的方式，將數組左右兩邊一次次拆分，直到left>=right時，遞歸結束。
  代碼實現：

public class QuickSort {
    public static void main(String[] args) {
        int arr[]= {2,7,1,2,8,1,3,9,415,189,123};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int [] arr,int left ,int right) {
        //遞歸的出口，當左側==右側
        if(left>=right) {
            return;
        }
        //獲取基準點
        int point=getPoint(arr,left,right);
        //左邊排序(遞歸)
        sort(arr,left,point-1);
        //右邊排序(遞歸)
        sort(arr,point+1,right);
    }
    public static  int getPoint(int [] arr,int left ,int right) {
        int key=arr[left];
        while(left<right) {
            //從右向左循環,只要右邊的比基準點大，就繼續循序
            while(key<=arr[right]&&left<right) {
                //每循環一次，right的索引向左移一個
                right--;
            }
            //交換基準點的位置
            arr[left]=arr[right];
            //從左向右循環,只要左邊的比基準點小，就繼續循序
            while(arr[left]<=key&&left<right) {
                left++;
            }
            //交換基準點
            arr[right]=arr[left];
        }
        //最后給基準點賦值
        arr[left]=key;
        return left;
    }
}

注意：了解快速排序有助于了解MR的map-reduce過程，因為在MRmap階段環形緩沖區滿了之后，會將數據溢寫到文件中，這個過程中就是使用了快速排序。

5. 計數排序

  原理：對一個已有數組進行排序，那么就新建一個數組，數組長度為數組中元素的最大值+1。并把已有數組中的元素，對應上新建數組的下標，放入里面，新建數組的元素為，已有數組中元素的出現次數。
  原理圖：

解釋：新創建一個數組，長度為需要排序的數組的最大值+1，遍歷數組，將數組中的值分別找到新數組的索引，將索引處的元素+1，最后，遍歷輸出新數組的下標（只輸出相應的值>0的下標，并且值為多少就輸出幾次）。
  代碼實現：

public class CountSort {
    public static void main(String[] args) {
        int arr[]= {2,7,1,2,8,1,3,9,415,189,123};
        sort(arr,415);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int arr[],int max) {
        int index=0;
        int newarr[]=new int [max+1];
        for(int i=0;i<arr.length;i++) {
            newarr[arr[i]]++;
        }
        for(int i=0;i<newarr.length;i++) {
            if(newarr[i]!=0) {
                for(int j=0;j<newarr[i];j++) {
                    arr[index++]=i;
                }
            }
        }
    }
}

注意：了解計數排序，有助于了解hbase的布隆過濾器，布隆過濾器的特點就是，我說沒有就沒有，我說有不一定有（有一定的誤判率）。

6. 歸并排序（兩路）

原理：針對多個有序的數據集進行排序。（時間復雜度：n*logN）
歸并排序有兩個階段：
一個是歸：將一個數據集拆分到每一個小的數據集只有一個元素。
實現一個數據集的歸：

public static void chai(int arr[],int first,int last,int [] newarr) {
        if(first>=last) {
            return;
        }
        //找中間點
        int mid=(first+last)/2;
        //左邊歸
        chai(arr,first,mid,newarr);
        //右側拆
        chai(arr,mid+1,last,newarr);
        //拆完之后并
        meger(arr,first,last,mid,newarr);
}

一個是并：將兩個有序的數據集，合并成為一個有序的大數據集。
實現兩個有序數據集的并：

public int[] bing(int arr1[], int arr2[]) {
        //創建一個最終結果的數組：長度為arr1和arr2長度之和
        int newarr[] = new int[arr1.length+arr2.length];
        //新數組的元素標記
        int index=0;
        //記錄arr1和arr2的下標
        int arr1_index=0;
        int arr2_index=0;
        //只要有一個數組，遍歷結束，就停止循環
        while(arr1_index<arr1.length&&arr2_index<arr2.length) {
            //進行判斷，將數據存儲在新數組中
            if(arr1[arr1_index]<arr2[arr2_index]) {
                newarr[index++]=arr1[arr1_index++];
            }else {
                newarr[index++]=arr2[arr2_index++];
            }
        }
        //可能是arr1沒有遍歷完全
        while(arr1_index<arr1.length) {
            newarr[index++]=arr1[arr1_index++];
        }
        //可能是arr2沒有遍歷完全
        while(arr2_index<arr2.length) {
            newarr[index++]=arr2[arr2_index++];
        }
        return newarr;
    }

完整代碼實現：

public class bingSort {
    public static void main(String[] args) {
        int arr[]= {1,8,7,6,11,2,4};
        int newarr[]=new int[arr.length];
        System.out.println(Arrays.toString(arr));
        chai(arr,0,arr.length-1,newarr);
        System.out.println(Arrays.toString(newarr));
    }
    //歸
    public static void chai(int arr[],int first,int last,int [] newarr) {
        if(first>=last) {
            return;
        }
        //找中間點
        int mid=(first+last)/2;
        //左邊歸
        chai(arr,first,mid,newarr);
        //右側拆
        chai(arr,mid+1,last,newarr);
        //拆完之后并
        meger(arr,first,last,mid,newarr);
    }
    /**
     *  并
     * @param arr 原數組
     * @param first 開始位置
     * @param last 結束位置
     * @param mid 中間位置
     * @param newarr  存放最終結果的數組
     */
    public static void meger(int arr[],int first,int last,int mid,int [] newarr) {
        //第一個數據集的起始下標
        int arr1_start=first;
        //第一個數據集的終止下標
        int arr1_end=mid;
        //第二個數據集的起始下標
        int arr2_start=mid+1;
        //第二個數據集的終止下標
        int arr2_end=last;
        int index=0;
        while(arr1_start<=arr1_end&&arr2_start<=arr2_end) {
            if(arr[arr1_start]<arr[arr2_start]) {
                newarr[index++]=arr[arr1_start++];
            }else {
                newarr[index++]=arr[arr2_start++];
            }
        }
        while(arr1_start<=arr1_end) {
            newarr[index++]=arr[arr1_start++];
        }
        while(arr2_start<=arr2_end) {
            newarr[index++]=arr[arr2_start++];
        }
        /**
         * 因為歸并排序，需要使用兩個有序的數據集，而arr一開始時無需的，所有每一次歸并的時候
         * 需要將歸并好之后的那一段數據集，賦值到arr中，使之后的歸并仍然有序
         */
        //賦值的循環的次數，是本次歸并的元素的個數
        for(int i=0;i<index;i++) {
            //每次賦值的時候，是從first開始
             arr[first+i]=newarr[i];
        }
    }
}

注意：在MR程序中，其中有兩個階段使用到了歸并，一個是在緩沖區溢寫小文件時，最后會將多個小文件歸并成一個大文件，另一個則是在reduce拉去map處理的數據到本地是會生成很多小文件，此時也會做一次歸并。

7. 二分法查找數據

  原理：在已經排好序的基礎上，將數組元素折半查找。
  原理圖：

  代碼實現：

public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
        // 二分法查數據
        int num = new Scanner(System.in).nextInt(); //查找的數
        int start = 0;
        int end = arr.length - 1;
        int middle = (start + end) / 2;
        while (true) {
          //如果end<start說明全部找完也沒有找到
            if (end < start) {
                System.out.println(num + "不在此數組中");
                break;
            }
            if (arr[middle] > num) {
                end = middle - 1;
            } else if (arr[middle] < num) {
                start = middle + 1;
            } else {
                System.out.println("這個數的索引下標為" + middle);
                break;
            }
            middle = (start + end) / 2;
        }