发信人: pack27(pack27.net)
整理人: winsy(2003-03-05 16:32:51), 站内信件
|
排序算法
--------------------------------------------------------------------------------
为什么有这么多的排序算法?
首先，在计算机编程中排序是一个经常遇到的问题。数据只有经过排序后，才更有意义。其次，排序算法说明了许多重要的算法的技术，例如二进制细分，递归和线性添加。最后要说明的一点是不同的算法有不同的优缺点，没有一种算法在任何情况下都是最好的算法。
●汽泡排序法
该算法是专门针对已部分排序的数据进行排序的一种排序算法。如果在你的数据清单中只有一两个数据是乱序的话，用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的，那么这种方法就成了最慢的算法了。因此在使用这种算法之前一定要慎重。
这种算法的核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。
图1是对这种算法的说明。在该例中，数字1的未按顺序排好。第一次扫描清单时，程序找到4和1是两个相邻的乱序项目，于是交换它们的位置。以此类推，直到将所有的项目按1234排好。数字1就象上升的汽泡一样，这就是这一算法名称的由来。
2 2 2 1
3 3 1 2
4 1 3 3
1 4 4 4
图1.
你可以改进该算法，让程序自下而上开始扫描，这样只须一次就能排好顺序了。
下面是用VB代码实现这一算法的例子：
' min and max are the minimum and maximum indexes
' of the items that might still be out of order.
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
●选择排序法
选择排序法是一个很简单的算法。其原理是首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。下面是VB代码实现该算法。
Sub Selectionsort (List() As Long, min As Integer, _
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
当寻找第I小的数据时，你必须检查N-I个项目，所以这一算法所用的步骤可用下面这个公式求得。
N + (N - 1) + (N - 2) + ... + 1 = N * (N + 1) / 2
选择排序法适用于较少数据的排序。此外由于算法较简单，因此他的代码也比较简单，这就为我们维护代码带来了方便。实际上如果你的数据相当少的话，这种算法的速度快过其它更复杂的算法。
●快速排序法
快速排序法对于大量数据的排序特别有用。其基本原理是：首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。
通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多，该算法所需的步骤就是N * log(N) 步。对于使用比较法进行排序的算法来讲这是最快的方法。下面是用VB代码实现这一算法的例子。
Sub Quicksort (List() As Long, min As Integer, max As Integer)
Dim med_value As Long
Dim hi As Integer
Dim lo As Integer
Dim i As Integer
' If the list has no more than 1 element, it's sorted.
If min >= max Then Exit Sub
' Pick a dividing item.
i = Int((max - min + 1) * Rnd + min)
med_value = List(i)
' Swap it to the front so we can find it easily.
List(i) = List(min)
' Move the items smaller than this into the left
' half of the list. Move the others into the right.
lo = min
hi = max
Do
' Look down from hi for a value < med_value.
Do While List(hi) >= med_value
hi = hi - 1
If hi <= lo Then Exit Do
Loop
If hi <= lo Then
List(lo) = med_value
Exit Do
End If
' Swap the lo and hi values.
List(lo) = List(hi)
' Look up from lo for a value >= med_value.
lo = lo + 1
Do While List(lo) < med_value
lo = lo + 1
If lo >= hi Then Exit Do
Loop
If lo >= hi Then
lo = hi
List(hi) = med_value
Exit Do
End If
' Swap the lo and hi values.
List(hi) = List(lo)
Loop
' Sort the two sublists
Quicksort List(), min, lo - 1
Quicksort List(), lo + 1, max
End Sub
●计数排序法
前面提到过，对于使用比较法作为算法基础的算法来说，最快需N * log(N)步才能完成排序。计数排序法不作用比较，所以它不受此限制。实际上该算法是如此之快，以致于你会认为是使用了魔术，而不是数学运算来排序。
另一方面，计数排序法只能用于特殊的情况。首先，所有的要进行排序的数据必须是整数，不能对字符使用该算法；其次，数据的范围有限，如果你的数据是在1到1000之内，用这种算法的效果就非常好，但如果你的数据是在1到30000之间，该算法就根本不能用。
首先该算法创建一个整数类型的临时数组，该数组的上下标分别是要排序的数据的最大最小值。如果数据列表的最大最小值从min_item到max_item, 该算法就将数组创建成下面这样：
Dim Counts() As Integer
ReDim Counts(min_item To max_item)
接下来，算法检查列表中的每一个项目，并增加对应该项目的数组元素的值，当这一阶段完成后，Counts(I)的数值就是就是数值为I的基础上的个数。
For I = min To Max
Counts(List(I)) = Counts(List(I)) + 1
Next I
程序扫描Counts数组，将counts转换成被排序列表中的偏移量。
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代码
Sub Countingsort (List() As Long, sorted_list() As Long, _
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个以下)，则用选择排序法。
如果你的数据都是整数，并且数值不大(几千以内)，则用计数排序法。
否则的话用快速排序法法
●算法 优点 缺点
汽泡排序法：对以初步排序的数据来说这种方法的速度很快；在其它情况下运行速度较慢。
选择排序法：非常简单、容易明白、对于少量数据的排序来说速度很快；对大量数据的排序速度很慢。
快速排序法：对大量数据的排序来说速度很快；如果有大量重复的数据就比较麻烦。
计数排序法：当数据数值较小(1-1000之间)时，速度非常快；当数据数值较大时，速度较慢、需额外的内存、只能对整数类型的数据排序。
为进一步说明以上算法，请点此下载示例程序。点击此处可下载包含七种排序算法的示例工程，可将里面的模块添加到你的工程中直接使用。
下载示例程序：http://202.103.176.81/erun/adamyl/vbbooks/download/tut1.zip
包含七种排序算法的示例工程：http://202.103.176.81/erun/adamyl/vbtools/sort.zip 排序算法
--------------------------------------------------------------------------------
为什么有这么多的排序算法?
首先，在计算机编程中排序是一个经常遇到的问题。数据只有经过排序后，才更有意义。其次，排序算法说明了许多重要的算法的技术，例如二进制细分，递归和线性添加。最后要说明的一点是不同的算法有不同的优缺点，没有一种算法在任何情况下都是最好的算法。
●汽泡排序法
该算法是专门针对已部分排序的数据进行排序的一种排序算法。如果在你的数据清单中只有一两个数据是乱序的话，用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的，那么这种方法就成了最慢的算法了。因此在使用这种算法之前一定要慎重。
这种算法的核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。
图1是对这种算法的说明。在该例中，数字1的未按顺序排好。第一次扫描清单时，程序找到4和1是两个相邻的乱序项目，于是交换它们的位置。以此类推，直到将所有的项目按1234排好。数字1就象上升的汽泡一样，这就是这一算法名称的由来。
2 2 2 1
3 3 1 2
4 1 3 3
1 4 4 4
图1.
你可以改进该算法，让程序自下而上开始扫描，这样只须一次就能排好顺序了。
下面是用VB代码实现这一算法的例子：
' min and max are the minimum and maximum indexes
' of the items that might still be out of order.
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
●选择排序法
选择排序法是一个很简单的算法。其原理是首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。下面是VB代码实现该算法。
Sub Selectionsort (List() As Long, min As Integer, _
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
当寻找第I小的数据时，你必须检查N-I个项目，所以这一算法所用的步骤可用下面这个公式求得。
N + (N - 1) + (N - 2) + ... + 1 = N * (N + 1) / 2
选择排序法适用于较少数据的排序。此外由于算法较简单，因此他的代码也比较简单，这就为我们维护代码带来了方便。实际上如果你的数据相当少的话，这种算法的速度快过其它更复杂的算法。
●快速排序法
快速排序法对于大量数据的排序特别有用。其基本原理是：首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。
通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多，该算法所需的步骤就是N * log(N) 步。对于使用比较法进行排序的算法来讲这是最快的方法。下面是用VB代码实现这一算法的例子。
Sub Quicksort (List() As Long, min As Integer, max As Integer)
Dim med_value As Long
Dim hi As Integer
Dim lo As Integer
Dim i As Integer
' If the list has no more than 1 element, it's sorted.
If min >= max Then Exit Sub
' Pick a dividing item.
i = Int((max - min + 1) * Rnd + min)
med_value = List(i)
' Swap it to the front so we can find it easily.
List(i) = List(min)
' Move the items smaller than this into the left
' half of the list. Move the others into the right.
lo = min
hi = max
Do
' Look down from hi for a value < med_value.
Do While List(hi) >= med_value
hi = hi - 1
If hi <= lo Then Exit Do
Loop
If hi <= lo Then
List(lo) = med_value
Exit Do
End If
' Swap the lo and hi values.
List(lo) = List(hi)
' Look up from lo for a value >= med_value.
lo = lo + 1
Do While List(lo) < med_value
lo = lo + 1
If lo >= hi Then Exit Do
Loop
If lo >= hi Then
lo = hi
List(hi) = med_value
Exit Do
End If
' Swap the lo and hi values.
List(hi) = List(lo)
Loop
' Sort the two sublists
Quicksort List(), min, lo - 1
Quicksort List(), lo + 1, max
End Sub
●计数排序法
前面提到过，对于使用比较法作为算法基础的算法来说，最快需N * log(N)步才能完成排序。计数排序法不作用比较，所以它不受此限制。实际上该算法是如此之快，以致于你会认为是使用了魔术，而不是数学运算来排序。
另一方面，计数排序法只能用于特殊的情况。首先，所有的要进行排序的数据必须是整数，不能对字符使用该算法；其次，数据的范围有限，如果你的数据是在1到1000之内，用这种算法的效果就非常好，但如果你的数据是在1到30000之间，该算法就根本不能用。
首先该算法创建一个整数类型的临时数组，该数组的上下标分别是要排序的数据的最大最小值。如果数据列表的最大最小值从min_item到max_item, 该算法就将数组创建成下面这样：
Dim Counts() As Integer
ReDim Counts(min_item To max_item)
接下来，算法检查列表中的每一个项目，并增加对应该项目的数组元素的值，当这一阶段完成后，Counts(I)的数值就是就是数值为I的基础上的个数。
For I = min To Max
Counts(List(I)) = Counts(List(I)) + 1
Next I
程序扫描Counts数组，将counts转换成被排序列表中的偏移量。
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代码
Sub Countingsort (List() As Long, sorted_list() As Long, _
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个以下)，则用选择排序法。
如果你的数据都是整数，并且数值不大(几千以内)，则用计数排序法。
否则的话用快速排序法法
●算法 优点 缺点
汽泡排序法：对以初步排序的数据来说这种方法的速度很快；在其它情况下运行速度较慢。
选择排序法：非常简单、容易明白、对于少量数据的排序来说速度很快；对大量数据的排序速度很慢。
快速排序法：对大量数据的排序来说速度很快；如果有大量重复的数据就比较麻烦。
计数排序法：当数据数值较小(1-1000之间)时，速度非常快；当数据数值较大时，速度较慢、需额外的内存、只能对整数类型的数据排序。
为进一步说明以上算法，请点此下载示例程序。点击此处可下载包含七种排序算法的示例工程，可将里面的模块添加到你的工程中直接使用。
下载示例程序：http://202.103.176.81/erun/adamyl/vbbooks/download/tut1.zip
包含七种排序算法的示例工程：http://202.103.176.81/erun/adamyl/vbtools/sort.zip |
|