航母抗台风吗:多种算法VB版
来源:百度文库 编辑:九乡新闻网 时间:2024/04/29 02:30:40
汽泡排序法
该算法是专门针对已部分排序的数据进行排序的一种排序算法。如果在你的数据清单中只有一两个数据是乱序的话,用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的,那么这种方法就成了最慢的算法了。因此在使用这种算法之前一定要慎重。' of the items that might still be out of order.
Sub BubbleSort()Sub BubbleSort (List() As Long, ByVal min As Integer, _
ByVal max As Integer)
Dim last_swap As Integer
Dim i As Integer
Dim j As Integer
Dim tmp As Long
' Repeat until we are done.
Do While min < max
' Bubble up.
last_swap = min - 1
' For i = min + 1 To max
i = min + 1
Do While i <= max
' Find a bubble.
If List(i - 1) > List(i) Then
' See where to drop the bubble.
tmp = List(i - 1)
j = i
Do
List(j - 1) = List(j)
j = j + 1
If j > max Then Exit Do
Loop While List(j) < tmp
List(j - 1) = tmp
last_swap = j - 1
i = j + 1
Else
i = i + 1
End If
Loop
' Update max.
max = last_swap - 1
' Bubble down.
last_swap = max + 1
' For i = max - 1 To min Step -1
i = max - 1
Do While i >= min
' Find a bubble.
If List(i + 1) < List(i) Then
' See where to drop the bubble.
tmp = List(i + 1)
j = i
Do
List(j + 1) = List(j)
j = j - 1
If j < min Then Exit Do
Loop While List(j) > tmp
List(j + 1) = tmp
last_swap = j + 1
i = j - 1
Else
i = i - 1
End If
Loop
' Update min.
min = last_swap + 1
Loop
End Sub
max As Integer)
Dim i As Integer
Dim j As Integer
Dim best_value As Long
Dim best_j As Integer
For i = min To max - 1
best_value = List(i)
best_j = i
For j = i + 1 To max
If List(j) < best_value Then
best_value = List(j)
best_j = j
End If
Next j
List(best_j) = List(i)
List(i) = best_value
Next i
End Sub
N + (N - 1) + (N - 2) + ... + 1 = N * (N + 1) / 2
快速排序法
快速排序法对于大量数据的排序特别有用。其基本原理是:首先检查数据列表中的数据数,如果小于两个,则直接退出程序。如果有超过两个以上的数据,就选择一个分割点将数据分成两个部分,小于分割点的数据放在一组,其余的放在另一组,然后分别对两组数据排序。Dim Counts() As Integer接下来,算法检查列表中的每一个项目,并增加对应该项目的数组元素的值,当这一阶段完成后,Counts(I)的数值就是就是数值为I的基础上的个数。
ReDim Counts(min_item To max_item)
For I = min To Max程序扫描Counts数组,将counts转换成被排序列表中的偏移量。
Counts(List(I)) = Counts(List(I)) + 1
Next I
next_spot = 1最后将数据进行排序
For i = min_value To max_value
this_count = counts(i)
counts(i) = next_spot
next_spot = next_spot + this_count
Next i
下面是实现该算法的VB代码
min As Integer, max As Integer, min_value As Long, _
max_value As Long)
Dim counts() As Integer
Dim i As Integer
Dim this_count As Integer
Dim next_offset As Integer
' Create the Counts array.
ReDim counts(min_value To max_value)
' Count the items.
For i = min To max
counts(List(i)) = counts(List(i)) + 1
Next i
' Convert the counts into offsets.
next_offset = min
For i = min_value To max_value
this_count = counts(i)
counts(i) = next_offset
next_offset = next_offset + this_count
Next i
' Place the items in the sorted array.
For i = min To max
sorted_list(counts(List(i))) = List(i)
counts(List(i)) = counts(List(i)) + 1
Next i
End Sub
总结
下表是各种算法的优缺点比较,正如你所见到的那样,每种算法只是在某一情况下表现得最好,下面是选择算法时的一些原则:- 如果你的数据列表中有99%数据已排过序,则用汽泡排序法。
- 如果你要排序的数据较少(100个以下),则用选择排序法。
- 如果你的数据都是整数,并且数值不大(几千以内),则用计数排序法。
- 否则的话用快速排序法法