整理一下最常用的三种排序：快速排序，归并排序，堆排序

以LeetCode56题为例，原理就不多说了

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public int[][] merge(int[][] intervals) {
    quickSort(intervals, 0, intervals.length - 1);
    ArrayList<ArrayList<Integer>> res = new ArrayList();
    for(int i = 0; i < intervals.length; i++) {
        if(res.size() != 0 && intervals[i][0] <= res.get(res.size() - 1).get(1)) {
            if(intervals[i][1] > res.get(res.size() - 1).get(1)) {
                res.get(res.size() - 1).remove(1);
                res.get(res.size() - 1).add(intervals[i][1]);
            }
        }
        else
            res.add(new ArrayList(Arrays.asList(intervals[i][0], intervals[i][1])));
    }
    int[][] ret = new int[res.size()][2];
    int i = 0;
    for(ArrayList<Integer> list : res) {
        ret[i][0] = list.get(0);
        ret[i][1] = list.get(1);
        i++;
    }
    return ret;
}

快速排序

private void quickSort(int[][] intervals, int start, int end) {
    if(start >= end)
        return;
    int l = start;
    int r = end;
    int[] cur = {intervals[start][0], intervals[start][1]};
    boolean flag = true;
    while(l < r) {
        if(flag) {
            if(intervals[r][0] >= cur[0]) {
                r--;
                continue;
            }
            intervals[l][0] = intervals[r][0];
            intervals[l][1] = intervals[r][1];
            l++;
            flag = !flag;
        } else {
            if(intervals[l][0] <= cur[0]) {
                l++;
                continue;
            }
            intervals[r][0] = intervals[l][0];
            intervals[r][1] = intervals[l][1];
            r--;
            flag = !flag;
        }
    }
    intervals[l][0] = cur[0];
    intervals[l][1] = cur[1];
    quickSort(intervals, start, l - 1);
    quickSort(intervals, l + 1, end);
}

归并排序

private void mergeSort(int[][] intervals, int start, int end) {
    if(start >= end)
        return;
    int mid = (start + end) / 2;
    mergeSort(intervals, start, mid);
    mergeSort(intervals, mid + 1, end);
    if(intervals[mid][0] < intervals[mid +1][0])
        return;
    int[][] temp = new int[end - start + 1][2];
    for(int i = start; i <= end; i++) {
        temp[i - start][0] = intervals[i][0];
        temp[i - start][1] = intervals[i][1];
    }
    int i = start;
    int j = mid + 1;
    int cur = start;
    while(i <= mid || j <= end) {
        if(i > mid) {
            intervals[cur][0] = temp[j - start][0];
            intervals[cur][1] = temp[j - start][1];
            j++;
            cur++;
        } else if(j > end) {
            intervals[cur][0] = temp[i - start][0];
            intervals[cur][1] = temp[i - start][1];
            i++;
            cur++;
        } else if(temp[j - start][0] < temp[i - start][0]) {
            intervals[cur][0] = temp[j - start][0];
            intervals[cur][1] = temp[j - start][1];
            j++;
            cur++;
        } else {
            intervals[cur][0] = temp[i - start][0];
            intervals[cur][1] = temp[i - start][1];
            i++;
            cur++;
        }
    }
}

堆排序

private void heapSort(int[][] intervals) {
    int len = intervals.length;
    for(int i = len / 2 - 1; i >= 0; i--)
        modifyHeap(intervals, i, len - 1);
    for(int i = len - 1; i >= 0; i--) {
        swap(intervals, 0, i);
        modifyHeap(intervals, 0, i - 1);
    }
}
private void modifyHeap(int[][] intervals, int start, int end) {
    int cur = start;
    int left = 2 * cur + 1;
    while(left <= end) {
        if(left < end && intervals[left][0] < intervals[left + 1][0]) {
            left++;
        }
        if(intervals[cur][0] >= intervals[left][0])
            break;
        else {
            swap(intervals, cur, left);
            cur = left;
            left = 2 * cur + 1;
        }
    }
}
private void swap(int[][] intervals, int i, int j) {
    int[] temp = new int[2];
    temp[0] = intervals[i][0];
    temp[1] = intervals[i][1];
    intervals[i][0] = intervals[j][0];
    intervals[i][1] = intervals[j][1];
    intervals[j][0] = temp[0];
    intervals[j][1] = temp[1];
}