按键精灵2014
算法原理:冒泡排序(BubbleSort) 冒泡排序是最慢的排序算法,但也是新手最容易上手的一个排序方法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。它是O(n^2)的算法。
算法的复杂度 有没有同学问,O(n^2)的算法是什么呢?这是其实是衡量算法速度快慢的一个指标,我们称之为算法的时间复杂度。时间复杂越大,算法的执行效率越低。 当然,并不是越快的算法,一定越好。算法还有另一个指标,叫空间复杂度,即算法占用多少空间,这个和内存息息相关。一个算法可能很快,但是它占用的内存多,不一定耗得起。 所以呢在不同的场合,我们需要根据不同的要求,会选择最合适的算法。
如何计算时间复杂度时间复杂度,其实就是算法中某一语句循环执行的次数。例如:冒泡排序法的原理For i = 1 To n For j = 1 To n 冒泡排序 NextNext 这个算法的时间复杂度,即“冒泡排序”这个语句的执行次数。当i=1的时候,For j = 1 To n:冒泡排序:Next,“冒泡排序”这个语句被执行了n次。当i=2的时候,For j = 1To n:冒泡排序:Next,“冒泡排序”这个语句又被执行了n次。当i=3的时候,For j = 1To n:冒泡排序:Next,“冒泡排序”这个语句又被执行了n次。……当i=n的时候,For j = 1To n:冒泡排序:Next,“冒泡排序”这个语句又被执行了n次。 综上,“冒泡排序”这个语句被执行了n个n次,即n*n=n^2次。所以冒泡排序的时间复杂度即为n^2,我们记为O(n^2) 注:1.如果算法中语句执行次数为一个常数,则时间复杂度为O(1)。 2.若一个算法的时间复杂度为O(n)=n^2+3n+4,我们只取算式中最高次方,即O(n^2)。
算法的实现
算法讲解:'冒泡排序 //经过n-1趟子排序完成的,它的时间复杂度为O(n^2) //优点:1.代码简单易懂;2.具有稳定性1.获取到物品价格,存入数组su2.获取到数组的个数,即物品的总数,记为M3.循环开始4.获取到数组su(0)的数值5.su(0)与数组中剩余的数值对比(su(1)-su(M)),若数值大于su(0),则相互调换6.Su(0)存储数组中最大的值7.循环到数组最后一个数值su(M)8.结束第一次循环,数组的第一个元素su(0)为数组中最大值9.从su(1) 到su(M),重复5-8步骤,实现su数组最后为从大到小的降序排列。
代码具体实现:Dim i,j su= '105875|502150|411400|63525|111925|90750' //获取到的物品价格su=Split(su, '|')M = UBound(su) //升序排序 For i = 0 To UBound(su)-1 //i=0 的时候 j循环是从 1循环到数组最小不 第一轮循环,su(0)和su (1)-su(5)进行比较 选择6个数中最小的数放到su(0) 第二轮循环 su(1)和su(2)-su(5)比较 For j = i+1 to UBound (su) If int(su(i)) > int (su(j)) Then // 数组是字符串的 所以需要用int改为数值型 否则会出现错误 tran = su(j) su(j) = su(i) su(i) = tran //如果前一个数比后一个数大,就交换位置 End If Next Next// 降序排序 For i = 0 To UBound(su)-1 For j = i+1 to UBound (su) If int(su(i))
代码的每一次实现原数组: '105875|502150|411400|63525|111925|90750'第一次循环: 取su(0)的值105875,与su(1)对比。su(1)>su(0),则相互交换: '502150|105875|411400|63525|111925|90750' 然后拿su(0)的值502150,与su(2)-su(5)对比,没有比su(0)更大的值,不再交换,结束。第一次循环结束:'502150|105875|411400|63525|111925|90750'第二次循环: 取su(1)的值105875,与su(2)的值411400对比,su(2)>su(1),则相互交换:'502150|411400|105875|63525|111925|90750'然后拿su(1)的值411400,与su(3)-su(5)对比,没有比su(1)更大的值,不再交换,结束。第二次循环结束:'502150|411400|105875|63525|111925|90750'第三次循环: 取su(2)的值105875,与su(3)的值63525对比,su(3)
知识拓展 按数量级递增排列,常见的时间复杂度有: 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。