题目

给一组整数，按照升序排序。使用归并排序，快速排序，堆排序或者任何其他 O(n log n) 的排序算法。

解题

归并排序

public class Solution {    /**     * @param A an integer array     * @return void     */    public void sortIntegers2(int[] A) {        // Write your code here        if(A==null || A.length <=1)            return;        int low = 0;        int high = A.length - 1;        mergeSort(A,low,high);                }    public void mergeSort(int[] A,int low ,int high){        if(low>=high)            return;        int mid = low + (high - low)/2;        mergeSort(A,low,mid);        mergeSort(A,mid+1,high);        merge(A,low,mid,high);                    }    public void merge(int[] A,int low,int mid,int high){        int len = high - low + 1;        int[] C = new int[len];        int i = low;        int j = mid + 1;        int k = 0;        while(i<=mid && j<= high){            if(A[i]>A[j]){                C[k++] = A[j];                j++;            }else{                C[k++] = A[i];                i++;            }        }        while(i<=mid){            C[k++] = A[i];            i++;        }        while(j<=high){            C[k++] = A[j];            j++;        }        for(k=0;k