Dart语法进阶篇（一）-- Dart源码的排序算法详解
2019-07-04 本文已影响0人
AWeiLoveAndroid
版权声明：本文为博主原创文章，未经博主允许不得转载。https://www.jianshu.com/p/44ae73a58ebc
转载请标明出处：
https://www.jianshu.com/p/44ae73a58ebc
本文出自 AWeiLoveAndroid的博客
Flutter系列博文链接 ↓：
工具安装：
Flutter基础篇：
- 谷歌Flutter1.0正式版发布
- Flutter基础篇（1）-- 跨平台开发框架和工具集锦
- Flutter基础篇（2）-- 老司机用一篇博客带你快速熟悉Dart语法
- Flutter基础篇（3）-- Flutter基础全面详解
- Flutter基础篇（4）-- Flutter填坑全面总结
- Flutter基础篇（5）-- Flutter代码模板，解放双手，提高开发效率必备
- Flutter基础篇（6）-- 水平和垂直布局详解
- Flutter基础篇（7）-- Flutter更新错误全面解决方案(图文+视频讲解)
- Flutter基础篇（8）-- Flutter for Web详细介绍
- Flutter基础篇（9）-- 手把手教你用Flutter实现Web页面编写
- Flutter1.9升级体验总结（Flutter Web 1.9最新版本填坑指南）
Flutter进阶篇：
Dart语法系列博文链接 ↓：
Dart语法基础篇：
Dart语法进阶篇：
我在搜索print源码的时候，发现了print属于part of dart._internal;，然后我继续点进去发现part 'sort.dart';，看名字我大概猜到了这是一个用于排序的算法类。点进去一看，果然是这样的。代码总共380多行，不是很多，但是很简洁。其中就用到了插入排序算法和双向快速排序算法。
首先来看看这个类的结构：
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
part of dart._internal;
/**
* Dual-Pivot Quicksort algorithm.
*
* This class implements the dual-pivot quicksort algorithm as presented in
* Vladimir Yaroslavskiy's paper.
*
* Some improvements have been copied from Android's implementation.
*/
class Sort {
// When a list has less then [:_INSERTION_SORT_THRESHOLD:] elements it will
// be sorted by an insertion sort.
static const int _INSERTION_SORT_THRESHOLD = 32;
/**
* Sorts all elements of the given list [:a:] according to the given
* [:compare:] function.
*
* The [:compare:] function takes two arguments [:x:] and [:y:] and returns
* -1 if [:x < y:],
* 0 if [:x == y:], and
* 1 if [:x > y:].
*
* The function's behavior must be consistent. It must not return different
* results for the same values.
*/
static void sort<E>(List<E> a, int compare(E a, E b)) {
_doSort(a, 0, a.length - 1, compare);
}
/**
* Sorts all elements in the range [:from:] (inclusive) to [:to:] (exclusive)
* of the given list [:a:].
*
* If the given range is invalid an "OutOfRange" error is raised.
* TODO(floitsch): do we want an error?
*
* See [:sort:] for requirements of the [:compare:] function.
*/
static void sortRange<E>(List<E> a, int from, int to, int compare(E a, E b)) {
if ((from < 0) || (to > a.length) || (to < from)) {
throw "OutOfRange";
}
_doSort(a, from, to - 1, compare);
}
/**
* Sorts the list in the interval [:left:] to [:right:] (both inclusive).
*/
static void _doSort<E>(
List<E> a, int left, int right, int compare(E a, E b)) {
if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
_insertionSort(a, left, right, compare);
} else {
_dualPivotQuicksort(a, left, right, compare);
}
}
static void _insertionSort<E>(
List<E> a, int left, int right, int compare(E a, E b)) {
for (int i = left + 1; i <= right; i++) {
var el = a[i];
int j = i;
while ((j > left) && (compare(a[j - 1], el) > 0)) {
a[j] = a[j - 1];
j--;
}
a[j] = el;
}
}
static void _dualPivotQuicksort<E>(
List<E> a, int left, int right, int compare(E a, E b)) {
assert(right - left > _INSERTION_SORT_THRESHOLD);
// Compute the two pivots by looking at 5 elements.
int sixth = (right - left + 1) ~/ 6;
int index1 = left + sixth;
int index5 = right - sixth;
int index3 = (left + right) ~/ 2; // The midpoint.
int index2 = index3 - sixth;
int index4 = index3 + sixth;
var el1 = a[index1];
var el2 = a[index2];
var el3 = a[index3];
var el4 = a[index4];
var el5 = a[index5];
// Sort the selected 5 elements using a sorting network.
if (compare(el1, el2) > 0) {
var t = el1;
el1 = el2;
el2 = t;
}
if (compare(el4, el5) > 0) {
var t = el4;
el4 = el5;
el5 = t;
}
if (compare(el1, el3) > 0) {
var t = el1;
el1 = el3;
el3 = t;
}
if (compare(el2, el3) > 0) {
var t = el2;
el2 = el3;
el3 = t;
}
if (compare(el1, el4) > 0) {
var t = el1;
el1 = el4;
el4 = t;
}
if (compare(el3, el4) > 0) {
var t = el3;
el3 = el4;
el4 = t;
}
if (compare(el2, el5) > 0) {
var t = el2;
el2 = el5;
el5 = t;
}
if (compare(el2, el3) > 0) {
var t = el2;
el2 = el3;
el3 = t;
}
if (compare(el4, el5) > 0) {
var t = el4;
el4 = el5;
el5 = t;
}
var pivot1 = el2;
var pivot2 = el4;
// el2 and el4 have been saved in the pivot variables. They will be written
// back, once the partitioning is finished.
a[index1] = el1;
a[index3] = el3;
a[index5] = el5;
a[index2] = a[left];
a[index4] = a[right];
int less = left + 1; // First element in the middle partition.
int great = right - 1; // Last element in the middle partition.
bool pivots_are_equal = (compare(pivot1, pivot2) == 0);
if (pivots_are_equal) {
var pivot = pivot1;
// Degenerated case where the partitioning becomes a Dutch national flag
// problem.
//
// [ | < pivot | == pivot | unpartitioned | > pivot | ]
// ^ ^ ^ ^ ^
// left less k great right
//
// a[left] and a[right] are undefined and are filled after the
// partitioning.
//
// Invariants:
// 1) for x in ]left, less[ : x < pivot.
// 2) for x in [less, k[ : x == pivot.
// 3) for x in ]great, right[ : x > pivot.
for (int k = less; k <= great; k++) {
var ak = a[k];
int comp = compare(ak, pivot);
if (comp == 0) continue;
if (comp < 0) {
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} else {
// comp > 0.
//
// Find the first element <= pivot in the range [k - 1, great] and
// put [:ak:] there. We know that such an element must exist:
// When k == less, then el3 (which is equal to pivot) lies in the
// interval. Otherwise a[k - 1] == pivot and the search stops at k-1.
// Note that in the latter case invariant 2 will be violated for a
// short amount of time. The invariant will be restored when the
// pivots are put into their final positions.
while (true) {
comp = compare(a[great], pivot);
if (comp > 0) {
great--;
// This is the only location in the while-loop where a new
// iteration is started.
continue;
} else if (comp < 0) {
// Triple exchange.
a[k] = a[less];
a[less++] = a[great];
a[great--] = ak;
break;
} else {
// comp == 0;
a[k] = a[great];
a[great--] = ak;
// Note: if great < k then we will exit the outer loop and fix
// invariant 2 (which we just violated).
break;
}
}
}
}
} else {
// We partition the list into three parts:
// 1. < pivot1
// 2. >= pivot1 && <= pivot2
// 3. > pivot2
//
// During the loop we have:
// [ | < pivot1 | >= pivot1 && <= pivot2 | unpartitioned | > pivot2 | ]
// ^ ^ ^ ^ ^
// left less k great right
//
// a[left] and a[right] are undefined and are filled after the
// partitioning.
//
// Invariants:
// 1. for x in ]left, less[ : x < pivot1
// 2. for x in [less, k[ : pivot1 <= x && x <= pivot2
// 3. for x in ]great, right[ : x > pivot2
for (int k = less; k <= great; k++) {
var ak = a[k];
int comp_pivot1 = compare(ak, pivot1);
if (comp_pivot1 < 0) {
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} else {
int comp_pivot2 = compare(ak, pivot2);
if (comp_pivot2 > 0) {
while (true) {
int comp = compare(a[great], pivot2);
if (comp > 0) {
great--;
if (great < k) break;
// This is the only location inside the loop where a new
// iteration is started.
continue;
} else {
// a[great] <= pivot2.
comp = compare(a[great], pivot1);
if (comp < 0) {
// Triple exchange.
a[k] = a[less];
a[less++] = a[great];
a[great--] = ak;
} else {
// a[great] >= pivot1.
a[k] = a[great];
a[great--] = ak;
}
break;
}
}
}
}
}
}
// Move pivots into their final positions.
// We shrunk the list from both sides (a[left] and a[right] have
// meaningless values in them) and now we move elements from the first
// and third partition into these locations so that we can store the
// pivots.
a[left] = a[less - 1];
a[less - 1] = pivot1;
a[right] = a[great + 1];
a[great + 1] = pivot2;
// The list is now partitioned into three partitions:
// [ < pivot1 | >= pivot1 && <= pivot2 | > pivot2 ]
// ^ ^ ^ ^
// left less great right
// Recursive descent. (Don't include the pivot values.)
_doSort(a, left, less - 2, compare);
_doSort(a, great + 2, right, compare);
if (pivots_are_equal) {
// All elements in the second partition are equal to the pivot. No
// need to sort them.
return;
}
// In theory it should be enough to call _doSort recursively on the second
// partition.
// The Android source however removes the pivot elements from the recursive
// call if the second partition is too large (more than 2/3 of the list).
if (less < index1 && great > index5) {
while (compare(a[less], pivot1) == 0) {
less++;
}
while (compare(a[great], pivot2) == 0) {
great--;
}
// Copy paste of the previous 3-way partitioning with adaptions.
//
// We partition the list into three parts:
// 1. == pivot1
// 2. > pivot1 && < pivot2
// 3. == pivot2
//
// During the loop we have:
// [ == pivot1 | > pivot1 && < pivot2 | unpartitioned | == pivot2 ]
// ^ ^ ^
// less k great
//
// Invariants:
// 1. for x in [ *, less[ : x == pivot1
// 2. for x in [less, k[ : pivot1 < x && x < pivot2
// 3. for x in ]great, * ] : x == pivot2
for (int k = less; k <= great; k++) {
var ak = a[k];
int comp_pivot1 = compare(ak, pivot1);
if (comp_pivot1 == 0) {
if (k != less) {
a[k] = a[less];
a[less] = ak;
}
less++;
} else {
int comp_pivot2 = compare(ak, pivot2);
if (comp_pivot2 == 0) {
while (true) {
int comp = compare(a[great], pivot2);
if (comp == 0) {
great--;
if (great < k) break;
// This is the only location inside the loop where a new
// iteration is started.
continue;
} else {
// a[great] < pivot2.
comp = compare(a[great], pivot1);
if (comp < 0) {
// Triple exchange.
a[k] = a[less];
a[less++] = a[great];
a[great--] = ak;
} else {
// a[great] == pivot1.
a[k] = a[great];
a[great--] = ak;
}
break;
}
}
}
}
}
// The second partition has now been cleared of pivot elements and looks
// as follows:
// [ * | > pivot1 && < pivot2 | * ]
// ^ ^
// less great
// Sort the second partition using recursive descent.
_doSort(a, less, great, compare);
} else {
// The second partition looks as follows:
// [ * | >= pivot1 && <= pivot2 | * ]
// ^ ^
// less great
// Simply sort it by recursive descent.
_doSort(a, less, great, compare);
}
}
}
