排序与汉诺塔算法的设计与实现

排序与汉诺塔算法的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与实现 一、 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的提出 我们生活中处处都需要排序,例如最普通的排队问题、排列小游戏等。汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智游戏。上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定：在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘，最后把这些圆盘放在第三根柱子上，并且从下往上是圆盘大小依次减小的。当所有的圆盘都从第一根柱子移到第三根柱子上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 二、 算法设计 1、汉诺塔排序的实现利用了一个中间帮助柱子B，将A柱子上的五个盘按照游戏规则移动到C柱子上。其中利用了函数的递归调用，图片的移动事件，鼠标事件，以及图片的载入、控件数组等相关知识。 （1）用户可以随时点击“重新开始”按钮重新开始这个游戏； （2）用户可以随时点击“退出”按钮退出这个游戏。 2、VB排序主要运用了冒泡排序法、插入排序法、Bucket排序法、选择排序法、Shell排序法、快速排序法、Heap排序法等排序 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 。 1冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。 2插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 3Bucket排序法即桶排序，它的有效性需假定输入数据是由一个完全随机过程产生，即要求桶排序的输入数据呈均匀分布。桶排序思想如下：1）把区间[0, 1)分解为n个大小相等的桶；2）将n个输入数据按照其取值不同分配到n个桶里面；3）对每个桶里面的数据进行排序；4）然后将桶里面的数据按顺序收集。 4选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。 5希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。 6快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。快速排序可以由下面四步组成。（1） 如果不多于1个数据，直接返回。（2） 一般选择序列最左边的值作为支点数据。（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。（4） 对两边利用递归排序数列。 7Heap排序法即堆排序法，堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大或者最小,这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。 三、 算法实现 1. VB汉诺塔 程序代码：Dim num(3) As Byte Dim centre(3) As Integer Private Sub Initialize(numOfPlate As Integer) num(1) = numOfPlate num(2) = 0 num(3) = 0 '7个盘的可见性 For i = 1 To 7 plate(i).Visible = True If (i > numOfPlate) Then plate(i).Visible = False End If Next i '7个盘的纵坐标位置 plate(1).Top = -240 * numOfPlate + 3600 For i = 2 To 7 plate(i).Top = plate(i - 1).Top + 240 Next  '7个盘的横坐标位置 For i = 1 To 7 plate(i).Left = centre(1) - plate(i).Width / 2 Next i End Sub Private Sub position(obj As Shape, place As Integer) obj.Top = -240 * num(place) + 3600 obj.Left = centre(place) - obj.Width / 2 End Sub Private Sub movePlate(N As Integer, F As Integer, T As Integer) num(F) = num(F) - 1 num(T) = num(T) + 1 For i = 1 To 1000 For j = 1 To 1000 For k = 1 To 20 Next k Next j Next i Call position(plate(N), T) End Sub Private Sub Hanoi(N As Integer, A As Integer, B As Integer, C As Integer) If N = 1 Then Call movePlate(N, A, C) Else Call Hanoi(N - 1, A, C, B) Call movePlate(N, A, C) Call Hanoi(N - 1, B, A, C) End If End Sub Private Sub Command1_Click() Call Hanoi(scl.Value, 1, 2, 3) Print "完成！" End Sub Private Sub Form_Load() Form1.Show centre(1) = 1627 centre(2) = 3667 centre(3) = 5707 Initialize (7) End Sub Private Sub Label1_Click() End Sub Private Sub scl_Change() lblNum.Caption = scl.Value Call Initialize(scl.Value) End Sub 2. VB排序 程序代码：Option Explicit Dim mArray() 'Download by Private Sub cmbSorts_Click() If cmbSorts.ListIndex > 4 Then cmbOrder.Enabled = False Else cmbOrder.Enabled = True End If End Sub Private Sub Command1_Click() Dim I Dim J If Len(Trim$(txtSize)) = 0 Then txtSize = "0" ReDim mArray(CDbl(txtSize) - 1) Randomize lstUnsorted.Clear For I = 0 To CDbl(txtSize) - 1 J = Int((32767 - (-32768) + 1) * Rnd + (-32768)) lstUnsorted.AddItem Str$(J) mArray(I) = J Next Command2.Enabled = True End Sub Private Sub Command2_Click() Dim I MousePointer = 11 lstSorted.Clear I = Timer lblBegin = "开始时间: " & I gIterations = 0 Select Case cmbSorts.ListIndex Case 0 Call BubbleSort(mArray(), cmbOrder.ListIndex) Case 1 Call Insertion(mArray(), cmbOrder.ListIndex) Case 2 Call Bucket(mArray(), cmbOrder.ListIndex)