排序

1、快速排序
先从数列中取出一个数作为基准数。
将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
再对左右区间重复第二步，直到各区间只有一个数。

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[] a, int left, int right) {
        if (left < right) {
            int i = left;
            int j = right;
            int x = a[i];
            while (i<j) {
                while (i<j && a[j] > x)
                    j--;
                if (i<j)
                    a[i++] = a[j];
                while (i<j && a[i] < x)
                    i++;
                if (i<j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quickSort(a, left, i-1);
            quickSort(a, i+1, right);
        }
    }
}

2、归并排序
递归划分整个区间为基本相等的左右区间，直到左右区间各只有一个数字，然后就合并两个有序区间。

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