所以我有一個任務讓我做一個冒泡排序，我這樣做了：
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 中怎么樣？
uj5u.com熱心網友回復：
如果通過優化，您的意思是它在有序陣列上停止，而不是：
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;
}
而且現在才使用氣泡...
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/512878.html
標籤：算法镖排序冒泡排序