1 package com.dongbin.sort;  2   3 import java.util.Arrays;  4   5 /**  6  * 排序  7  * @author dongbin  8  *  9  */ 10 public class AllSort { 11      12     public static void main(String[] args) { 13         int[] arr = {1,32,43,11,23,45}; 14         MergeSort(arr); 15         System.out.println(Arrays.toString(arr)); 16     } 17  18     /** 19      * 冒泡排序 20      * @param arr 21      * @return 22      */ 23     public static int[] BubbleSort(int[] arr){ 24          25         for(int i=0;i<arr.length-1;i++){ 26             for(int j=i+1;j<arr.length;j++){ 27                 if(arr[i]>arr[j]){ 28                     int temp = arr[i]; 29                     arr[i] = arr[j]; 30                     arr[j] = temp; 31                 } 32             } 33         } 34         return arr; 35     } 36      37     /** 38      * 选择排序 39      * @param arr 40      * @return 41      */ 42     public static int[] SelectionSort(int[] arr){ 43          44         int min; 45         for(int i=0;i<arr.length-1;i++){ 46             min=i; 47             for(int j=i+1;j<arr.length;j++){ 48                 if(arr[i]>arr[j]){ 49                     min = j; 50                 } 51             } 52              53             if(min!=i){ 54                 int temp = arr[i]; 55                 arr[i] = arr[min]; 56                 arr[min] = temp; 57             } 58         } 59         return arr; 60     } 61      62     /** 63      * 插入排序 64      * @param arr 65      * @return 66      */ 67     public static int[] InsertSort(int[] arr){ 68          69         for(int i=1;i<arr.length;i++){ 70             int current = arr[i]; 71             int pos = i; 72             for(int j=i-1;j>=0;j--){ 73                 if(arr[j]>current){ 74                     arr[j+1] = arr[j]; 75                     pos = j; 76                 } 77             } 78             arr[pos]=current; 79         } 80         return arr; 81     } 82      83     /** 84      * 快速排序 85      * @param arr 86      * @return 87      */ 88     public static int[] QuickSort(int[] arr){ 89         if(arr.length<=1){ 90             System.out.println("传入的数组长度小于或等于1"); 91         }else{ 92             _quickSort(arr, 0, arr.length-1); 93         } 94          95         return arr; 96     } 97      98     public static void _quickSort(int[] arr ,int start, int end){ 99         if(start>=end){100             return;101         }102         103         int i = start,j=end,current = arr[j];104         boolean flag = false;105         106         while(i!=j){107             if(flag){108                 if(arr[j]<current){109                     int temp = arr[j];110                     arr[j] = arr[i];111                     arr[i] = temp;112                     flag = false;113                 }else j--;114             }else{115                 if(arr[i]>current){116                     int temp = arr[j];117                     arr[j] = arr[i];118                     arr[i] = temp;119                     flag = true;120                 }else i++;121             }122         }123         124         _quickSort(arr, start, i-1);//左边125         _quickSort(arr, j+1, end);//右边126     } 127     128     129     /**130      * 归并排序131      * @param arr132      * @return133      */134     public static int[] MergeSort(int[] arr){135         _mergeSort(arr, 0, arr.length-1);136         return arr;137     }138     139     public static void _mergeSort(int[] arr,int left,int right){140 141         if (left < right) {142             int mid = (left + right) / 2;143             // 划分144             _mergeSort(arr, left, mid);145             _mergeSort(arr, mid + 1, right);146 147             // 合并148             _merge(arr, left, mid, right);149         }150 151     }152     public static void _merge(int[] arr,int left,int mid,int right){153         154         int[] newArr = new  int[arr.length];//新数组155         int center = mid+1;156         int tmp = left;157         int pos = left;158         159         while(left<=mid&&center<=right){160             if(arr[left]<=arr[center]){161                 newArr[pos++]=arr[left++];162             }else{                163                 newArr[pos++]=arr[center++];164             }165         }166         167         while(left<=mid){168             newArr[pos++]=arr[left++];169         }170         171         while(center<=right){172             newArr[pos++]=arr[center++];173         }174         175         while(tmp<=right){176             arr[tmp] = newArr[tmp++];177         }178         179         180         181     }182 }