1. 调用库函数Arrays.sort
2. 冒泡排序BubbleSort
3. 快速排序QuickSort
4. 归并排序MergeSort
5. 堆排序HeapSort

1. 调用库函数Arrays.sort

import java.util.Arrays;
public class Solution {
    public int[] MySort (int[] arr) {
        //调用库函数sort；
        Arrays.sort(arr);
        return arr;
    }
}

2. 冒泡排序BubbleSort--可能会超时

　　以升序排列为例：将第一个元素和第二个元素比较，若前者大于后者，则交换两者的位置，再将第二个元素与第三个元素比较，若前者大于后者则交换两者位置，以此类推直到倒数第二个元素与最后一个元素比较，若前者大于后者，则交换两者位置。这样一轮比较下来将会把序列中最大的元素移至序列末尾，这样就安排好了最大数的位置，接下来只需对剩下的（n-1）个元素，重复上述操作即可。 　　时间复杂度： 　　若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成，时间复杂度依然为O(n）； 　　若是倒序，比较次数为 n-1+n-2+...+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n2） 　　空间复杂度： 　　使用常数个辅助单元：O(1）

 

import java.util.*;
import java.util.Arrays;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        if(arr.length<2)
        {
            return arr;
        }
        for(int i=0;i<arr.length-1; i++)
        {
            for(int j=0;j<arr.length-i-1;j++)
            {
                if(arr[j]>arr[j+1])
                {
                    swap(arr,j,j+1);
                }
            }
        }
        return arr;
    }
    public void swap(int[]arr,int i,int j)
    {
        int tmp;
        tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
}

3. 快速排序QuickSort

　　快速排序(Quick Sort)：是对冒泡排序的一种改进方法，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，y速度较快，故称为“快速排序”。 快速排序的基本思想是：

1. 在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
2. 将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
3. 对左右两个分区重复以上步骤直到所有元素都是有序的

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        quickSort(arr , 0 , arr.length-1);
        return arr;
    }
    public void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组，找到分割点
            int point = partition(list, left, right);
            // 递归调用，对左子数组进行快速排序
            quickSort(list, left, point - 1);
            // 递归调用，对右子数组进行快速排序
            quickSort(list, point + 1, right);
        }
    }
 
    /**
     * 分割数组，找到分割点
     */
    public int partition(int[] list, int left, int right) {
        // 用数组的第一个元素作为基准数
        int first = list[left];
        while (left < right) {
            while (left < right && list[right] >= first) {
                right--;
            }
 
            // 交换
            swap(list, left, right);
 
            while (left < right && list[left] <= first) {
                left++;
            }
 
            // 交换
            swap(list, left, right);
        }
        // 返回分割点所在的位置
        return left;
    }
 
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

4. 归并排序MergeSort

　　归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。 　　归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 将给定数组排序
   * @param arr int整型一维数组 待排序的数组
   * @return int整型一维数组
   */
  public int[] MySort (int[] arr) {
      mergeSort(arr,0,arr.length-1);
      return arr;
  }
 
  public void mergeSort(int[] arr,int l,int r){
      if(l==r){
          return;
      }
      int mid =(l+r)/2; //中点位置，即(l+r)/2
      mergeSort(arr,l,mid);
      mergeSort(arr,mid+1,r);
      merge(arr,l,mid,r);
  }
 
  public void merge(int[] arr,int l,int mid,int r){
      int [] help= new int[r-l+1];    //辅助数组
      int i=0;
      int p1=l; //左半数组的下标
      int p2=mid+1; //右半数组的下标
 
      //判断是否越界
      while(p1<=mid && p2<=r){
          help[i++]=arr[p1]<arr[p2] ? arr[p1++] : arr[p2++];
      }
      //p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
      while(p1<=mid){
          help[i++]=arr[p1++];
      }
      //p2没有越界，说明p1越界了
      while(p2<=r){
          help[i++]=arr[p2++];
      }
      //将辅助数组元素拷贝会原数组
      for(i=0;i<help.length;i++){
          arr[l+i]=help[i];
      }
  }
}

5. 堆排序HeapSort

heapInsert和heapify 大根堆最重要的两个操作就是heapInsert和heapify，前者是当一个元素加入到大根堆时应该自底向上与其父结点比较，若大于父结点则交换；后者是当堆中某个结点的数值发生变化时，应不断向下与其孩子结点中的最大值比较，若小于则交换。下面是对应的代码：

//判断该结点与父结点的大小，大结点一直往，建立大根堆
   public static void heapInsert(int[] arr,int index){
       while(arr[index]>arr[(index-1)/2]){
           swap(arr,index,(index-1)/2);
           index=(index-1)/2;
       }
   }   
   //一个值变小往下沉的过程
   public static void heapify(int[] arr,int index,int size){
       int left=index*2+1;
       while(left<size){
           int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1 : left;
           largest = arr[largest] > arr[index] ? largest :index;
           if(largest==index){
               break;
           }
           swap(arr,largest,index);
           index=largest;
           left=index*2 +1;
 
       }
   }

public int[] MySort (int[] arr) {
    heapSort(arr);
    return arr;
}
 
public static void heapSort(int[] arr){
    if(arr == null || arr.length<2){
        return;
    }
    for(int i=0;i<arr.length;i++){
        heapInsert(arr,i); //构造完全二叉树
    }
    int size = arr.length;
    swap(arr,0,--size);
    while(size>0){
        heapify(arr,0,size);// 最后一个数与根交换
        swap(arr,0,--size);
    }
 
}
//判断该结点与父结点的大小，大结点一直往，建立大根堆
public static void heapInsert(int[] arr,int index){
    while(arr[index]>arr[(index-1)/2]){
        swap(arr,index,(index-1)/2);
        index=(index-1)/2;
    }
}
 
//一个值变小往下沉的过程
public static void heapify(int[] arr,int index,int size){
    int left=index*2+1;
    while(left<size){
        int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1 : left;
        largest = arr[largest] > arr[index] ? largest :index;
        if(largest==index){
            break;
        }
        swap(arr,largest,index);
        index=largest;
        left=index*2 +1;
 
    }
}
 
//交换函数
public static void swap(int[] arr, int i, int j){
    int tmp;
    tmp=arr[i];
    arr[i]=arr[j];
    arr[j]=tmp;
}