Arrays.sort

2019-03-18 20:13:04

一. int[]排序

  • 数组元素个数小于287
    • 数组元素个数小于47
      • 排序区间是最左边的,传统的插入排序
      • 排序区间不是最左边的,双插入排序
    • 数组元素个数大于等于47
      • 选5个基准值
      • 如果5个基准值各不相同
        • 双轴快排
          • 递归排序左部分和右部分
          • 数组中间部分长度太大的话,先缩小一下范围
          • 递归排序中间部分
      • 5个基准值中有重复的
        • 单轴快排
  • 数组元素个数大于等于287
    • 判断数组无序程度
      • 如果有序子序列个数大于等于67,此时可以认为数组基本无序,直接用上面的快排
      • 否则归并排序
  1. // Arrays
  2. public static void sort(int[] a) {
  3. DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
  4. }

这个方法进来后,先进行了一个判断,判断要排序的元素个数是否小于一个阈值(287),如果小于,则特殊处理

  1. static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) {
  2. // Use Quicksort on small arrays
  3. if (right - left < QUICKSORT_THRESHOLD) { // 286
  4. sort(a, left, right, true);
  5. return;
  6. }
  7. ...
  8. }

上面的sort方法进来之后,又做了一次判断,判断排序元素的个数是否小于47,如果小于47并且这段数组是最左边的就直接采用插入排序,在元素数量比较小的时候,插入排序会有更好的效率。

  1. private static void sort(int[] a, int left, int right, boolean leftmost) {
  2. int length = right - left + 1;
  3. // Use insertion sort on tiny arrays
  4. if (length < INSERTION_SORT_THRESHOLD) { // 47
  5. if (leftmost) { // 这段数组是最左边的
  6. // 插入排序
  7. for (int i = left, j = i; i < right; j = ++i) {
  8. int ai = a[i + 1];
  9. while (ai < a[j]) {
  10. a[j + 1] = a[j];
  11. if (j-- == left) {
  12. break;
  13. }
  14. }
  15. a[j + 1] = ai;
  16. }
  17. } else { // 这段数组不是最左边的,采用双插入排序,这个排序方法在左边有可能数组越界
  18. // 跳过最长的上升序列
  19. do {
  20. if (left >= right) {
  21. return;
  22. }
  23. } while (a[++left] >= a[left - 1]);
  24. // 双插入排序,每次迭代的过程完成两个元素的插入
  25. for (int k = left; ++left <= right; k = ++left) {
  26. int a1 = a[k], a2 = a[left];
  27. // 保证a1 >= a2
  28. if (a1 < a2) { // 一次迭代完成两个元素的插入排序
  29. a2 = a1; a1 = a[left]; // 0 1 2 3 4 5 下标值
  30. } // 4 7 8 9 6 5 6和5为a1和a2
  31. // 找到a1的插入位置 // 4 7 6 7 8 9 找到6的位置,此时k = 1
  32. while (a1 < a[--k]) { // 4 5 6 7 8 9 找到5的位置
  33. a[k + 2] = a[k];
  34. }
  35. a[++k + 1] = a1;
  36. // 由于a2 <= a1,所以可以接着刚才的k继续向前遍历
  37. while (a2 < a[--k]) {
  38. a[k + 1] = a[k];
  39. }
  40. a[k + 1] = a2;
  41. }
  42. int last = a[right];
  43. // 由于除去前面有序部分后面的元素个数为单数,还剩一个元素没插入
  44. while (last < a[--right]) {
  45. a[right + 1] = a[right];
  46. }
  47. a[right + 1] = last;
  48. }
  49. return;
  50. }
  51. // 长度/7 的近似值
  52. int seventh = (length >> 3) + (length >> 6) + 1;
  53. // 以seventh为间隔,在数组中找了5个基准值
  54. int e3 = (left + right) >>> 1; // The midpoint
  55. int e2 = e3 - seventh;
  56. int e1 = e2 - seventh;
  57. int e4 = e3 + seventh;
  58. int e5 = e4 + seventh;
  59. // 下面这4个if是用插入排序的方式对这5个基准值进行排序,只有5个元素,所以没有写成循环的形式
  60. if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
  61. if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
  62. if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  63. }
  64. if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
  65. if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  66. if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  67. }
  68. }
  69. if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
  70. if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
  71. if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
  72. if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
  73. }
  74. }
  75. }
  76. // Pointers
  77. int less = left; // The index of the first element of center part
  78. int great = right; // The index before the first element of right part
  79. // 如果这5个基准值都不相等
  80. if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
  81. // 选择第2个和第4个作为双轴快排的两个基准值,这样数组分成了三部分
  82. int pivot1 = a[e2];
  83. int pivot2 = a[e4];
  84. // 开始快排
  85. // 将数组最左边的值放在第一个基准值的位置上,最右边的值放在第二个基准值的位置上
  86. a[e2] = a[left];
  87. a[e4] = a[right];
  88. while (a[++less] < pivot1); // 最左部分找到第一个不小于pivot1的值
  89. while (a[--great] > pivot2); // 最右部分找到第一个不大于pivot2的值
  90. /*
  91. * Partitioning:
  92. *
  93. * left part center part right part
  94. * +--------------------------------------------------------------+
  95. * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
  96. * +--------------------------------------------------------------+
  97. * ^ ^ ^
  98. * | | |
  99. * less k great
  100. *
  101. * Invariants:
  102. *
  103. * all in (left, less) < pivot1
  104. * pivot1 <= all in [less, k) <= pivot2
  105. * all in (great, right) > pivot2
  106. *
  107. * Pointer k is the first index of ?-part.
  108. */
  109. // 这几个变量区间范围内的数组元素总会保持上面注释中的大小关系
  110. outer:
  111. for (int k = less - 1; ++k <= great; ) {
  112. // 从less开始向后遍历,此时less是从左边开始第一个不小于prvot1的位置
  113. int ak = a[k];
  114. if (ak < pivot1) {
  115. // ak < pivot1时,ak需要被移动到左侧左侧部分
  116. // 交换a[less]和a[k],并将less++
  117. // 交换后ak就被移到了左侧部分
  118. a[k] = a[less];
  119. a[less] = ak;
  120. ++less;
  121. } else if (ak > pivot2) { // Move a[k] to right part
  122. // ak > pivot2时,ak需要被移动到右侧部分
  123. while (a[great] > pivot2) {
  124. if (great-- == k) {
  125. break outer;
  126. }
  127. }
  128. // a[great]需要移动到左侧
  129. if (a[great] < pivot1) { // a[great] <= pivot2
  130. // 这部分操作相当于[less, k)区间最左侧的元素移到了区间右侧
  131. // 然后less++,结果就是这个区间的元素整体右移
  132. a[k] = a[less];
  133. a[less] = a[great]; // a[great]移到左侧
  134. ++less;
  135. } else { // pivot1 <= a[great] <= pivot2
  136. a[k] = a[great]; // a[great]加入[less, k)区间
  137. }
  138. // ak移动到右侧部分
  139. a[great] = ak;
  140. --great;
  141. }
  142. }
  143. // 将基准值放入对应的位置
  144. a[left] = a[less - 1]; a[less - 1] = pivot1;
  145. a[right] = a[great + 1]; a[great + 1] = pivot2;
  146. // 现在数组分成三个区间
  147. // [left, less - 2] < pivot1
  148. // [less, great] >= pivot1 && <= pivot2
  149. // [great + 2, right] > pivot2
  150. // 对最左和最右部分递归排序
  151. sort(a, left, less - 2, leftmost);
  152. sort(a, great + 2, right, false);
  153. // 如果中间部分范围太长,就缩小一下,将与基准值相等的全放到区间两边
  154. // 这样可以只排序中间 > pivot1 && < pivot2的
  155. // 缩小了[less, great]范围
  156. if (less < e1 && e5 < great) {
  157. // 跳过和两边的基准值相等的元素
  158. while (a[less] == pivot1) {
  159. ++less;
  160. }
  161. while (a[great] == pivot2) {
  162. --great;
  163. }
  164. /*
  165. * Partitioning:
  166. *
  167. * left part center part right part
  168. * +----------------------------------------------------------+
  169. * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
  170. * +----------------------------------------------------------+
  171. * ^ ^ ^
  172. * | | |
  173. * less k great
  174. *
  175. * Invariants:
  176. *
  177. * all in (*, less) == pivot1
  178. * pivot1 < all in [less, k) < pivot2
  179. * all in (great, *) == pivot2
  180. *
  181. * Pointer k is the first index of ?-part.
  182. */
  183. // 类似于上面的代码,只不过这个是将与两个基准值相等的元素全放到区间两端
  184. outer:
  185. for (int k = less - 1; ++k <= great; ) {
  186. int ak = a[k];
  187. if (ak == pivot1) { // Move a[k] to left part
  188. a[k] = a[less];
  189. a[less] = ak;
  190. ++less;
  191. } else if (ak == pivot2) { // Move a[k] to right part
  192. while (a[great] == pivot2) {
  193. if (great-- == k) {
  194. break outer;
  195. }
  196. }
  197. if (a[great] == pivot1) { // a[great] < pivot2
  198. a[k] = a[less];
  199. a[less] = pivot1;
  200. ++less;
  201. } else { // pivot1 < a[great] < pivot2
  202. a[k] = a[great];
  203. }
  204. a[great] = ak;
  205. --great;
  206. }
  207. }
  208. }
  209. // 递归对中间部分排序
  210. sort(a, less, great, false);
  211. } else { // Partitioning with one pivot
  212. // 如果这5个基准值有重复的,就假定当前数组中有许多重复的元素,退化到传统单轴快排
  213. // 用数组中间位置的值作为基准值
  214. int pivot = a[e3];
  215. /*
  216. * Partitioning degenerates to the traditional 3-way
  217. * (or "Dutch National Flag") schema:
  218. *
  219. * left part center part right part
  220. * +-------------------------------------------------+
  221. * | < pivot | == pivot | ? | > pivot |
  222. * +-------------------------------------------------+
  223. * ^ ^ ^
  224. * | | |
  225. * less k great
  226. *
  227. * Invariants:
  228. *
  229. * all in (left, less) < pivot
  230. * all in [less, k) == pivot
  231. * all in (great, right) > pivot
  232. *
  233. * Pointer k is the first index of ?-part.
  234. */
  235. // 下面的循环将将数组分成三部分
  236. // [left, less - 1] < pivot
  237. // [less, great] == pivot (因为此时假定数组中有很多重复的元素)
  238. // [great + 1, right] > pivot
  239. for (int k = less; k <= great; ++k) {
  240. if (a[k] == pivot) {
  241. continue;
  242. }
  243. int ak = a[k];
  244. if (ak < pivot) { // Move a[k] to left part
  245. a[k] = a[less];
  246. a[less] = ak;
  247. ++less;
  248. } else { // a[k] > pivot - Move a[k] to right part
  249. while (a[great] > pivot) {
  250. --great;
  251. }
  252. if (a[great] < pivot) { // a[great] <= pivot
  253. a[k] = a[less];
  254. a[less] = a[great];
  255. ++less;
  256. } else { // a[great] == pivot
  257. a[k] = pivot;
  258. }
  259. a[great] = ak;
  260. --great;
  261. }
  262. }
  263. // 只需对左右两部分递归排序
  264. sort(a, left, less - 1, leftmost);
  265. sort(a, great + 1, right, false);
  266. }
  267. }

如果数组长度大于等于287,进行归并排序

  1. // 评估数组无序程度
  2. // 数组run存放的是每个递增或递减的子序列的开始下标
  3. int[] run = new int[MAX_RUN_COUNT + 1];
  4. int count = 0; run[0] = left;
  5. // Check if the array is nearly sorted
  6. for (int k = left; k < right; run[count] = k) {
  7. // Equal items in the beginning of the sequence
  8. while (k < right && a[k] == a[k + 1])
  9. k++;
  10. if (k == right) break; // Sequence finishes with equal items
  11. if (a[k] < a[k + 1]) { // 递增
  12. while (++k <= right && a[k - 1] <= a[k]);
  13. } else if (a[k] > a[k + 1]) { // 递减
  14. while (++k <= right && a[k - 1] >= a[k]);
  15. // 递减序列转换成递增序列
  16. for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  17. int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  18. }
  19. }
  20. // 一个递减序列转换成递增序列后是否可以合并到前一个递增序列
  21. if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
  22. count--;
  23. }
  24. // 子序列个数达到一定阈值就可以认为数组基本是无序的,直接采用上面改进过的快排排序
  25. if (++count == MAX_RUN_COUNT) {
  26. sort(a, left, right, true);
  27. return;
  28. }
  29. }
  30. // These invariants should hold true:
  31. // run[0] = 0
  32. // run[<last>] = right + 1; (terminator)
  33. if (count == 0) {
  34. // 数组元素都相等
  35. return;
  36. } else if (count == 1 && run[count] > right) {
  37. // 只有一个序列,数组已经有序
  38. return;
  39. }
  40. // 正常情况下,run[count] == right + 1,但也有例外
  41. // 最后一段元素都是相等的,或者最后一个序列只有一个元素
  42. // 此时,要将right+1添加到数组尾部,作为哨兵
  43. right++;
  44. if (run[count] < right) {
  45. run[++count] = right;
  46. }
  47. // 需要奇数轮merge时,odd = 0
  48. // 需要偶数轮merge时,odd = 1
  49. byte odd = 0;
  50. for (int n = 1; (n <<= 1) < count; odd ^= 1);
  51. // 创建临时数组b用于merge操作
  52. int[] b; // temp array; alternates with a
  53. int ao, bo; // array offsets from 'left'
  54. int blen = right - left; // space needed for b
  55. if (work == null || workLen < blen || workBase + blen > work.length) {
  56. work = new int[blen];
  57. workBase = 0;
  58. }
  59. // 如果需要奇数轮,令b指向需要排序的原数组,a指向work
  60. if (odd == 0) {
  61. System.arraycopy(a, left, work, workBase, blen);
  62. b = a;
  63. bo = 0;
  64. a = work;
  65. ao = workBase - left;
  66. } else { // 偶数轮的话,a不动,还是指向需要排序的原数组,b指向work
  67. b = work;
  68. ao = 0;
  69. bo = workBase - left;
  70. }
  71. // 上面这个对a,b指向的处理是因为在下面每一轮merge结束后,会交换a,b的指向
  72. // 要确保最后一轮merge中,元素被赋值的数组是需要排序的原数组,即需要b指向原数组
  73. // Merging
  74. for (int last; count > 1; count = last) {
  75. // 在循环中将两个相邻的递增子序列合并
  76. for (int k = (last = 0) + 2; k <= count; k += 2) {
  77. // 两个子序列下标范围是[run[k - 2], run[k - 1]),[run[k - 1], run[k])
  78. int hi = run[k], mi = run[k - 1];
  79. // 下面这个for合并了一对相邻的子序列
  80. for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { // [ , mi), [mi, hi)
  81. // p 第一个序列中的指针,q 第二个序列中的指针 // p q
  82. if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { // 左边的序列遍历完了 或 左边序列的元素比右边的小
  83. b[i + bo] = a[p++ + ao]; // 取左边的元素
  84. } else { // 否则取右边的元素
  85. b[i + bo] = a[q++ + ao];
  86. }
  87. }
  88. // 两个序列合并成一个有序序列后,更新序列起始下标
  89. run[++last] = hi;
  90. }
  91. // 如果子序列个数是奇数,则上面的合并完后还剩一个,直接copy到b中
  92. if ((count & 1) != 0) {
  93. for (int i = right, lo = run[count - 1]; --i >= lo;
  94. b[i + bo] = a[i + ao]
  95. );
  96. run[++last] = right;
  97. }
  98. // 交换数组a, b的指向
  99. int[] t = a; a = b; b = t;
  100. int o = ao; ao = bo; bo = o;
  101. }

二. Object[]排序

对于对象数组的排序,由于要保持排序的稳定性,所以与对基本类型数组的排序采用了不同的策略

  • 数组元素个数小于32,采用二分插入排序
  • 数组元素个数大于等于32,先分成一个个子序列,对这些子序列内部采用二分插入排序,然后对这些有序子序列进行归并
    插入排序与归并排序都是稳定的排序方式
  1. // Arrays
  2. public static void sort(Object[] a) {
  3. if (LegacyMergeSort.userRequested)
  4. legacyMergeSort(a);
  5. else
  6. ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
  7. }

数组长度小于32时,采用”mini-TimSort”,二分插入排序

  1. // ComparableTimSort
  2. static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
  3. assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
  4. int nRemaining = hi - lo;
  5. if (nRemaining < 2)
  6. return; // 数组长度为0或1已经有序了
  7. // If array is small, do a "mini-TimSort" with no merges
  8. if (nRemaining < MIN_MERGE) {
  9. // 让数组以递增序列开头,并返回递增序列长度
  10. int initRunLen = countRunAndMakeAscending(a, lo, hi);
  11. binarySort(a, lo, hi, lo + initRunLen);
  12. return;
  13. }
  14. ...
  15. }

保证排序区间是以递增序列开始的,并且返回这个递增序列的长度

  1. @SuppressWarnings({"unchecked", "rawtypes"})
  2. private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
  3. assert lo < hi;
  4. int runHi = lo + 1;
  5. if (runHi == hi) // 只有一个元素
  6. return 1;
  7. // 如果是递减序列,反转成递增序列
  8. if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
  9. while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
  10. runHi++;
  11. reverseRange(a, lo, runHi);
  12. } else { // Ascending
  13. while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
  14. runHi++;
  15. }
  16. // 返回序列长度
  17. return runHi - lo;
  18. }
  19. private static void reverseRange(Object[] a, int lo, int hi) {
  20. hi--;
  21. while (lo < hi) {
  22. Object t = a[lo];
  23. a[lo++] = a[hi];
  24. a[hi--] = t;
  25. }
  26. }
  1. // +---------------------+
  2. // | 递增序列 | 乱序 |
  3. // +---------------------+
  4. // lo start hi
  5. // 二分插入排序
  6. @SuppressWarnings({"fallthrough", "rawtypes", "unchecked"})
  7. private static void binarySort(Object[] a, int lo, int hi, int start) {
  8. assert lo <= start && start <= hi;
  9. if (start == lo)
  10. start++;
  11. // [left, start) 范围内是已排好序的元素
  12. // [start, hi) 范围内是待排序元素
  13. // 从start开始,对每个待待排序元素用二分查找在前面已排好序的部分寻找插入位置
  14. for ( ; start < hi; start++) {
  15. Comparable pivot = (Comparable) a[start];
  16. int left = lo;
  17. int right = start;
  18. assert left <= right;
  19. // 二分查找插入位置
  20. while (left < right) {
  21. int mid = (left + right) >>> 1;
  22. if (pivot.compareTo(a[mid]) < 0)
  23. right = mid;
  24. else
  25. left = mid + 1;
  26. }
  27. assert left == right;
  28. // 插入位置为left,计算left 与 start之间元素数量
  29. int n = start - left; // The number of elements to move
  30. // 下标范围为[left, start)的元素需向后移动一位
  31. // 如果元素数量为2或1,直接移动,而不是调用数组拷贝,数量更多的话就直接调用拷贝方法
  32. switch (n) {
  33. case 2: a[left + 2] = a[left + 1];
  34. case 1: a[left + 1] = a[left];
  35. break;
  36. default: System.arraycopy(a, left, a, left + 1, n);
  37. }
  38. // 将待插入元素放入应该插入的位置
  39. a[left] = pivot;
  40. }
  41. }

如果数组元素数量大于等于32,采用归并排序,基本思路是将数组分成一个个小的部分,对这些小的部分进行二分插入排序,让它们形成一个个有序子序列,然后对这些子序列进行merge

  1. ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
  2. // minRun就是每一个子序列的长度,是一个[0, 31]范围的整数
  3. int minRun = minRunLength(nRemaining);
  4. do {
  5. // 对子序列二分插入排序
  6. int runLen = countRunAndMakeAscending(a, lo, hi);
  7. if (runLen < minRun) {
  8. int force = nRemaining <= minRun ? nRemaining : minRun;
  9. binarySort(a, lo, lo + force, lo + runLen);
  10. runLen = force;
  11. }
  12. // 将这个子序列的起始位置与长度记录下来
  13. ts.pushRun(lo, runLen);
  14. // 如果满足条件会合并
  15. ts.mergeCollapse();
  16. // 更新子序列起点 与 剩余元素个数
  17. lo += runLen;
  18. nRemaining -= runLen;
  19. } while (nRemaining != 0);
  20. assert lo == hi;
  21. // 合并剩下的有序子序列
  22. ts.mergeForceCollapse();
  23. assert ts.stackSize == 1;

0
1
0

添加评论

正在回复:
取消
2
0
1
0