简单排序--归并排序，快速排序

归并排序以及快速排序

针对于数据量大的排序，一般不会采用冒泡，选择，插入等时间复杂度为O(n²)的，效率上太慢；一般使用归并排序和快速排序时间复杂度为O(nlogn)

快速排序

采用分治的思想进行排序，以一个基准值(pivot)先区分出 area < pivot 的部分 和 area > pivot的部分，然后在进行排序，是一种自上而下的思想，它的处理过程是由上到下的，先分区，然后再处理子问题,是不稳定的

private void quickSort(int[] arr){
    if (arr.length <= 1){
        return;
    }
    // 针对每个部分进行排序
    quickSort(arr,0,arr.length - 1);
}

private void quickSort(int[] arr,int low,int high){
    if (low < high){
        // 进行分区，获得两部分数据
        int pivot = patition(arr,low,high);
        quickSort(arr,low,pivot - 1);
        quickSort(arr,pivot + 1,high);
    }
}

private int patition(int[] arr,int low,int high){
    // 基准值
    int pivot = arr[low];
    while(low < high){
        while (low < high && pivot <= arr[high]) {
            -- high;
        }
        arr[low] = arr[high];
        while (low < high && pivot >= arr[low] ){
            ++ low;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

归并排序

也是采用分治的思想进行排序，由下到上的，先处理子问题，然后再合并，是一种自下而上的思想,是稳定的，但是额外的使用了空间O(n),主要原因是合并函数无法在原地执行

 private void mergeSort(int[] arr){
        mergeSort(arr,0,arr.length - 1);
    }

    private void mergeSort(int[] arr, int low, int high) {
        int mid = ( low + high ) / 2;
        if(low < high){
            mergeSort(arr,low,mid);
            mergeSort(arr,mid + 1,high);
            merge(arr,low,high,mid);
        }
    }

    private void merge(int[] arr, int low, int high, int mid) {
        int[] temp = new int[high - low + 1];
        int i = low,j = mid + 1,k = 0;
        while(i <= mid && j <= high){
            if (arr[i] < arr[j]){
                temp[k ++] = arr[i ++];
            }else{
                temp[k ++] = arr[j ++ ];
            }
        }
        while (i <= mid){
            temp [k ++] = arr[i ++ ];
        }
        while (j <= high){
            temp [k ++] = arr[j ++];
        }
        for (int l = 0; l < temp.length; l++) {
            arr[l + low] = temp[l];
        }
    }

未完。。