【Android TimeCat】 原地归并排序

Android Algorithm
  1. 1. 背景
  2. 2. 实现
    1. 2.1. 纯java版原地归并排序
    2. 2.2. 纯java版非原地归并排序
    3. 2.3. 项目运用版 ：桶排序 + 原地归并排序

背景

Time Cat中有个需求，需要把用户的task排序。

排序规则为，先按label排，每个label下按创建日期排，task处于完成状态的话覆盖原来label。label有四个，重要紧急，重要不紧急，紧急不重要，不重要不紧急。label加上完成状态共5组。

实现

思路是先用桶排序分组，再对每个组内用原地归并排序。

考虑到分组有且只有5组，用桶排序逻辑清晰，易于阅读，效率也高。

之所以用原地归并排序，是因为我想学(zhuang)习(bi)。用其他排序方法也是可以的，因为单个用户的task不会太多，而且排序放在网络请求之后，各种排序方法的差别不大。

纯java版原地归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/* 
 * 原地归并
 */
public class InPlaceMergeSort {

    private static void reverse(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i++] = arr[j];
        arr[j--] = temp;
    }

    // swap [bias, bias+headSize) and [bias+headSize, bias+headSize+endSize)
    private static void swapAdjacentBlocks(int arr[], int bias, int oneSize, int anotherSize) {
        reverse(arr, bias, bias + oneSize - 1);
        reverse(arr, bias + oneSize, bias + oneSize + anotherSize - 1);
        reverse(arr, bias, bias + oneSize + anotherSize - 1);
    }

    private static void inplaceMerge(int arr[], int l, int mid, int r) {
        int i = l;     // 指示左侧有序串
        int j = mid + 1; // 指示右侧有序串
        while(i < j && j <= r)  {//原地归并结束的条件。
            while(i < j && arr[i] <= arr[j]) {
                i++;
            }
            int index = j;
            while(j <= r && arr[j] <= arr[i]) {
                j++;
            }
            swapAdjacentBlocks(arr, i, index-i, j-index);
            i += (j-index);
        }
    }

    public static void mergeSort(int arr[], int l, int r) {
        if(l < r) {
            int mid = (l + r) / 2;
            mergeSort(arr, l, mid);
            mergeSort(arr, mid + 1, r);
            inplaceMerge(arr, l, mid, r);
        }
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i+", ");
        }
        System.out.println();
    }

    /* 测试用例 */
    public static void main(String[] args) {
        int[] arr = {3,5,1,7,0,6,9,11};
        mergeSort(arr, 0, arr.length-1);
        print(arr);
    }
}

纯java版非原地归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private static void merge(int[] dest, int[] src, int l, int mid, int r) {
    int i = l;
    int p = l;
    int q = mid + 1;
    while (p <= mid && q <= r) {
        if (src[p] <= src[q]) {
            dest[i++] = src[p++];
        } else {
            dest[i++] = src[q++];
        }
    }
    while (p <= mid) {
        dest[i++] = src[p++];
    }
    while (q <= r) {
        dest[i++] = src[q++];
    }
    // （原[l, r]范围的内容被复制回原数组）  
    i = l;
    while (i <= r) {  
        src[i] = dest[i++];  
    } 
}
public static void mergeSort(int[] dest, int[] src, int l, int r) {
    if (l < r) {
        int mid = (l + r) / 2;
        mergeSort(dest, src, l, mid);
        mergeSort(dest, src, mid + 1, r);
        merge(dest, src, l, mid, r);
    }
}

项目运用版 ：桶排序 + 原地归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
private ArrayList<DBTask> sort(ArrayList<DBTask> taskArrayList) {
    ArrayList<DBTask> sortedDBTaskList = new ArrayList<>();
    if (taskArrayList == null || taskArrayList.size() <= 0) {
        return sortedDBTaskList;
    }
    ArrayList<DBTask> label_0_DBTaskList = new ArrayList<>();
    ArrayList<DBTask> label_1_DBTaskList = new ArrayList<>();
    ArrayList<DBTask> label_2_DBTaskList = new ArrayList<>();
    ArrayList<DBTask> label_3_DBTaskList = new ArrayList<>();
    ArrayList<DBTask> finished_DBTaskList = new ArrayList<>();

    for (DBTask dbTask : taskArrayList) {
        if (dbTask.getIsFinish()) {
            finished_DBTaskList.add(dbTask);
            continue;
        }
        switch (dbTask.getLabel()) {
            case DBTask.LABEL_IMPORTANT_URGENT:
                label_0_DBTaskList.add(dbTask);
                break;
            case DBTask.LABEL_IMPORTANT_NOT_URGENT:
                label_1_DBTaskList.add(dbTask);
                break;
            case DBTask.LABEL_NOT_IMPORTANT_URGENT:
                label_2_DBTaskList.add(dbTask);
                break;
            case DBTask.LABEL_NOT_IMPORTANT_NOT_URGENT:
                label_3_DBTaskList.add(dbTask);
                break;
        }
    }
    mergeSort2List(label_0_DBTaskList, sortedDBTaskList);
    mergeSort2List(label_1_DBTaskList, sortedDBTaskList);
    mergeSort2List(label_2_DBTaskList, sortedDBTaskList);
    mergeSort2List(label_3_DBTaskList, sortedDBTaskList);
    mergeSort2List(finished_DBTaskList, sortedDBTaskList);

    return sortedDBTaskList;
}

private void reverse(ArrayList<DBTask> arr, int i, int j) {
    while(i < j) {
        DBTask temp = arr.get(i);
        arr.set(i++, arr.get(j));
        arr.set(j--, temp);
    }
}

// swap [bias, bias+headSize) and [bias+headSize, bias+headSize+endSize)
private void swapAdjacentBlocks(ArrayList<DBTask> arr, int bias, int oneSize, int anotherSize) {
    reverse(arr, bias, bias + oneSize - 1);
    reverse(arr, bias + oneSize, bias + oneSize + anotherSize - 1);
    reverse(arr, bias, bias + oneSize + anotherSize - 1);
}

private void inplaceMerge(ArrayList<DBTask> arr, int l, int mid, int r) {
    int i = l;     // 指示左侧有序串
    int j = mid + 1; // 指示右侧有序串
    while(i < j && j <= r) { //原地归并结束的条件。
        while(i < j && isValid(arr, i, j)) {
            i++;
        }
        int index = j;
        while(j <= r && isValid(arr, j, i)) {
            j++;
        }
        swapAdjacentBlocks(arr, i, index-i, j-index);
        i += (j-index);
    }
}

private boolean isValid(ArrayList<DBTask> arr, int i, int j) {
    Date date_i = TimeUtil.formatGMTDateStr(arr.get(i).getCreated_datetime());
    Date date_j = TimeUtil.formatGMTDateStr(arr.get(j).getCreated_datetime());
    return (date_i != null ? date_i.getTime() : 0) <= (date_j != null ? date_j.getTime() : 0);
}

private void mergeSort(ArrayList<DBTask> arr, int l, int r) {
    if(l < r) {
        int mid = (l + r) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        inplaceMerge(arr, l, mid, r);
    }
}

private void mergeSort2List(ArrayList<DBTask> taskArrayList, ArrayList<DBTask> result) {
    if (taskArrayList == null || taskArrayList.size() <= 0) {
        return;
    }
    mergeSort(taskArrayList, 0, taskArrayList.size()-1);
    result.addAll(taskArrayList);
}

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器