背景
Time Cat中有个需求，需要把用户的task排序。
排序规则为，先按label排，每个label下按创建日期排，task处于完成状态的话覆盖原来label。label有四个，重要紧急，重要不紧急，紧急不重要，不重要不紧急。label加上完成状态共5组。
实现
思路是先用桶排序分组，再对每个组内用原地归并排序。
考虑到分组有且只有5组，用桶排序逻辑清晰，易于阅读，效率也高。
之所以用原地归并排序，是因为我想学(zhuang)习(bi)。用其他排序方法也是可以的，因为单个用户的task不会太多，而且排序放在网络请求之后，各种排序方法的差别不大。
纯java版原地归并排序
/* * 原地归并 */ 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版非原地归并排序
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); } }
项目运用版 ：桶排序 + 原地归并排序
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); }