优化的泡泡飞镖排序

Question

所以我有一个任务让我做了一个冒泡启动，我做到了：

bubbleSort(List<int> list) {
for (int i = 0; i < list.length; i++) {
for (int j = 0; j < list.length - 1; j++) {
if (list[j] > list[j + 1]) {
int num = list[j];
list[j] = list[j + 1];
list[j + 1] = num;
}
}
}
print(list);
}
void main() {
List<int> list = [2, 5, 3, 15, 20, 5, 2, 7, 9];
bubbleSort(list);
}

现在它想让我做一个优化的泡泡排序，Dart怎么样？

Answer 1

如果您所说的优化是指它在有序数组上停止，而不是：

bubbleSort(List<int> list) { int i,j,e;
for (e=1,i=0; (i < list.length)&&(e); i++) {
for (e=0,j=0; j < list.length - 1; j++) {
if (list[j] > list[j + 1]) { e=1;
int num = list[j];
list[j] = list[j + 1];
list[j + 1] = num;
}
}
}
print(list);
}
void main() {
List<int> list = [2, 5, 3, 15, 20, 5, 2, 7, 9];
bubbleSort(list);
}

我只是添加了e，它设置在任何交换上，这意味着一旦迭代内部循环而不交换，排序就会停止。。

这仍然是O(n^2)，但在半排序数据上(在同一方向上(要快得多。。。

另一个优化选项是检测数组的排序量以及排序顺序是asc还是desc。一旦检测到相反的顺序(相对于使用的排序(，在使用气泡之前反转数组。。。

对于检测，你可以做这样的事情：

for (e=0,i=1;i<list.length;i++) 
if (list[i]>list[i-1]) e++; 
else e--;

现在，e越正，数组的asc排序越多，负得越多，数组的desc排序越多…

因此您可以添加例如(用于asc排序(：

if (e<-list.length/4) // for asc sorting
//if (e>+list.length/4) // for desc sorting
for (i=0,j=list.length-1;i<j;i++,j--) 
{
int num = list[i];
list[i] = list[j];
list[j] = num;
}

现在才使用bubble。。。