文档介绍：排序与汉诺塔算法的设计与实现
一、问题的提出
我们生活中处处都需要排序,例如最普通的排队问题、排列小游戏等。汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智游戏。上帝创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘,最后把这些圆盘放在第三根柱子上,并且从下往上是圆盘大小依次减小的。当所有的圆盘都从第一根柱子移到第三根柱子上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
二、算法设计
1、汉诺塔排序的实现利用了一个中间帮助柱子B,将A柱子上的五个盘按照游戏规则移动到C柱子上。其中利用了函数的递归调用,图片的移动事件,鼠标事件,以及图片的载入、控件数组等相关知识。
(1)用户可以随时点击“重新开始”按钮重新开始这个游戏;
(2)用户可以随时点击“退出”按钮退出这个游戏。
2、VB排序主要运用了冒泡排序法、插入排序法、Bucket排序法、选择排序法、Shell排序法、快速排序法、Heap排序法等排序方法。
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。