[toc]
Top 10 Classic sort comparisons
Bubbling, select, insert, merge, fast, Hill, and heap Sorting is Comparison Sorting
Algorithms for static web sites 2. Visualization
Stability of sorting algorithm
If the relative positions of two elements, which are equal, remain the same before and after sorting, then this is a stable sorting algorithm
- Before: 5,1,3 (a),4,7,3(b)
- Stable order: 1,3 (a), 3(b), 4,5,7
- Unstable order: 1,3 (b), 3(a), 4,5,7
When sorting custom objects, stability affects the final sorting result
| algorithm | Stability or not |
|---|---|
| Bubble sort | is |
In situ algorithm
- Not dependent on additional resources or on a few additional resources, relying only on the output to override the input
- All tasks with space complexity of O(1) can implement in-situ algorithm
The non-in-place algorithm, called not-in-Placke or out-of-placle, is in place as shown in the figure above
Advance preparation class
An abstract class
import '.. /tools/date_utl.dart';
///
/// Author: liyanjun
/// /// Date: 2020-11-01 10:41:34
/// FilePath: /algorithm/sort/sort.dart
/// Description: Sorted superclass
///
abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> {
// abstract class Sort
> {
List<T> list;
int cmpCount = 0; // The number of comparisons
int swapCount = 0; // The number of swaps
int time; // Take time
setList(List<T> list) {
this.list = list;
}
sortPrint() {
if (list == null || list.length < 2) return;
int begin = DateUtil.getNowDateMs();
sort();
int end = DateUtil.getNowDateMs();
time = end - begin;
}
sort();
///
/// Author: liyanjun
/// description:
/// List [i1] == list[i2]
/// List [i1] < list[i2]
/// List [i1] > list[i2]
///
///
int cmpWithIndex(int i1, int i2) {
cmpCount += 1;
return list[i1].compareTo(list[i2]);
}
///
/// Author: liyanjun
/// description:
// 返回值等于0，代表 v1 == v2
/// If the return value is less than 0, v1 is less than v2
/// If the return value is greater than 0, v1 > v2
int cmpElement(T v1, T v2) {
cmpCount += 1;
return v1.compareTo(v2);
}
///
/// Author: liyanjun
/// Description: Swap two index positions
///
void swap(int i1, int i2) {
swapCount += 1;
T tmp = list[i1];
list[i1] = list[i2];
list[i2] = tmp;
}
///
/// Author: liyanjun
/// Description: formatting
///
String _numberString(int number) {
if (number < 10000) return "$number";
if (number < 100000000) return "${(number / 10000.0).toStringAsFixed(2)}Wan";
return "${(number / 100000000.0).toStringAsFixed(2)}Hundred million";
}
// ///
// /// Author: liyanjun
// /// description: Checks whether it is stable
// ///
// bool get _isStable {
// if (this is RadixSort) return true;
// if (this is CountingSort) return true;
// if (this is ShellSort) return false;
// if (this is SelectionSort) return false;
// return true;
/ /}
///
/// Author: liyanjun
/// Description: Sort by time. If the time is equal, compare the number of comparisons. If the time is equal, compare the number of interactions
///
@override
int compareTo(Sort o) {
int result = (time - o.time);
if(result ! =0) return result;
result = cmpCount - o.cmpCount;
if(result ! =0) return result;
return swapCount - o.swapCount;
}
@override
String toString() {
// TODO: implement toString
String timeStr = "Time consuming:${time / 1000.0}s (${time}ms)";
String compareCountStr = "Comparison:${_numberString(cmpCount)}";
String swapCountStr = "Exchange:${_numberString(swapCount)}";
// String stableStr = "stableStr:" + isStable();
return "【" +
this.runtimeType.toString() +
"】 \ n"
// + stableStr + " \t"
+
timeStr +
" \t" +
compareCountStr +
"\t " +
swapCountStr +
"\n" +
"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --";
// return super.toString();}}Copy the codeClasses that operate on arrays
import 'dart:math';
class IntergerTools {
///
/// Author: liyanjun
/// Description: Generates a random number
///
static List<int> random(int count, int min, int max) {
if (count <= 0 || min > max) return null;
List<int> array = List<int>(count);
int delta = max - min + 1;
for (int i = 0; i < count; i++) {
array[i] = min + Random().nextInt(delta);
}
return array;
}
///
/// Author: liyanjun
/// Description: Merges two lists
///
static List combine(List array1, List array2) {
if (array1 == null || array2 == null) return null;
List array = [];
for (int i = 0; i < array1.length; i++) {
array[i] = array1[i];
}
for (int i = 0; i < array2.length; i++) {
array[i + array1.length] = array2[i];
}
return array;
}
///
/// Author: liyanjun
/// description:
///
static List same(int count, int unsameCount) {
if (count <= 0 || unsameCount > count) return null;
List array = [];
for (int i = 0; i < unsameCount; i++) {
array[i] = unsameCount - i;
}
for (int i = unsameCount; i < count; i++) {
array[i] = unsameCount + 1;
}
return array;
}
static List<int> headTailAscOrder(int min, int max, int disorderCount) {
List<int> array = ascOrder(min, max);
if (disorderCount > array.length) return array;
int begin = (array.length - disorderCount) >> 1;
reverse(array, begin, begin + disorderCount);
return array;
}
static List<int> centerAscOrder(int min, int max, int disorderCount) {
List<int> array = ascOrder(min, max);
if (disorderCount > array.length) return array;
int left = disorderCount >> 1;
reverse(array, 0, left);
int right = disorderCount - left;
reverse(array, array.length - right, array.length);
return array;
}
static List<int> headAscOrder(int min, int max, int disorderCount) {
List<int> array = ascOrder(min, max);
if (disorderCount > array.length) return array;
reverse(array, array.length - disorderCount, array.length);
return array;
}
static List<int> tailAscOrder(int min, int max, int disorderCount) {
List<int> array = ascOrder(min, max);
if (disorderCount > array.length) return array;
reverse(array, 0, disorderCount);
return array;
}
static List<int> ascOrder(int min, int max) {
if (min > max) return null;
List<int> array = List<int>(max - min + 1);
for (int i = 0; i < array.length; i++) {
array[i] = min++;
}
return array;
}
static List<int> descOrder(int min, int max) {
if (min > max) return null;
List<int> array = List<int>(max - min + 1);
for (int i = 0; i < array.length; i++) {
array[i] = max--;
}
return array;
}
/**
* Inverts an array with an index range of [begin, end) */
static void reverse(List<int> array, int begin, int end) {
int count = (end - begin) >> 1;
int sum = begin + end - 1;
for (int i = begin; i < begin + count; i++) {
int j = sum - i;
inttmp = array[i]; array[i] = array[j]; array[j] = tmp; }}static bool isAscOrder(List<int> array) {
if (array == null || array.length == 0) return false;
for (int i = 1; i < array.length; i++) {
if (array[i - 1] > array[i]) return false;
}
return true; }}Copy the codeTime for class
import 'date_utl.dart';
///
/// Date: 2020-10-31 22:51:08
/// FilePath: /sort/tools/times_tools.dart
/// Description: Utility class for testing time
///
class TimesTools {
static final DateFormat _fmt = DateFormat.DEFAULT;
static void test(String title, Function task) {
if (task == null) return;
title = (title == null)?"" : ("【" + title + "】");
print(title);
print("Start:${DateUtil.getDateStrByDateTime(DateTime.now(),format: _fmt)}");
int begin = DateUtil.getNowDateMs();
task();
int end = DateUtil.getNowDateMs();
print("The end of the${DateUtil.getDateStrByDateTime(DateTime.now(),format: _fmt)}");
double delta = (end - begin) / 1000.0;
print("Time consuming:$deltaSEC. "");
print("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --"); }}Copy the codePredicate judgment class
///
/// Author: liyanjun
/// Date: 2020-11-01 10:10:37
/// FilePath: /algorithm/tools/assert.dart
/// Description: Determines the result using an assertion
///
class Asserts {
static void test(bool value ){
try {
if (value == false) {
throw Exception("Failed the test."); }}catch (e) {
print('abnormal:$e');
rethrow; }}}Copy the codeComparison of sorting algorithms
main(List<String> args) {
List<int> list = IntergerTools.random(10000.1.20000); // Generate 10000 numbers, minimum is 1, maximum is 20000
// List
list = IntergerTools.random(10, 1, 20); // Generate 10000 numbers, minimum is 1, maximum is 20000
List<Sort> sortList = [
HeapSort<num>(),
SelectSort<num>(),
BubbleSort2<num>(),
BubbleSort1<num>(),
BubbleSort<num>(),
InsertSort<num>(),
InsertSort1<num>(),
InsertSort2<num>(),
MergeSort<num> ()]; testSorts(list, sortList); }void testSorts(List<int> list, List<Sort> sorts) {
// print(' before sort: $list');
for (Sort sort in sorts) {
List<int> newList = List.from(list);
sort.setList(newList);
sort.sortPrint();
Asserts.test(IntergerTools.isAscOrder(sort.list));
// print(' sort: ${sort.list}');
}
sorts.sort(); / / to compare
for (Sort sort in sorts) {
print(sort); }}Copy the codeThe results of
[MergeSort<num>] Time: 0.004s (4ms) Comparison: 124,400 exchange: 0 ----------------- [HeapSort<num>] Time: 0.007s (7ms) Comparison: 235,500 exchange: 9999 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 【 InsertSort2 < num > 】 take: 0.091 s (91 ms) comparison: 119000 exchange: 0 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 【 InsertSort1 < num > 】 take: ----------------- 【SelectSort<num>】 Time: 0.145s (145ms) Comparison: 499.9500 exchange: 0 9999 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 【 InsertSort < num > 】 take: 0.211 s (211 ms) comparison: 25.0904 million exchange: 25.0804 million -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 【 BubbleSort1 < num > 】 take: 0.523 s (523 ms) comparison: 49.9893 million exchange: 25.0804 million -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 【 BubbleSort2 < num > 】 take: 0.524 s (524 ms) comparison: 49.9419 million exchange: 25.0804 million -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 【 the BubbleSort < num > 】 take: 0.633 s (633 ms) comparison: 49.995 million exchange: 25.0804 million -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --Copy the code