各种排序方法比较 ........................................................................................................................... 1

影响排序效果的因素 ....................................................................................................................... 1

排序方法的选择 ............................................................................................................................... 1

排序稳定........................................................................................................................................... 2

时间复杂度....................................................................................................................................... 2

各种排序方法比较

简单排序中直接插入最好，快速排序最快，当排序序列为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：

①待排序的记录数目n；

②记录的大小(规模)；

③关键字的结构及其初始状态；

④对稳定性的要求；

⑤语言工具的条件；

⑥存储结构；

⑦时间和辅助空间复杂度等。

排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若排序序列初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

(3)若n较大则用：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

若要求排序稳定，则可选用归并排序。但从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是

稳定的。

排序稳定

稳定的概念:

在待排序的数据中，重复的数据位置经过排序位置不变

稳定排序的有：直接插入排序;冒泡排序;归并排序

不稳定的有:希尔排序，快速排序，直接（简单）选择排序，堆排序

时间复杂度

时间复杂度的关系有：

c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!

时间复杂度越小则算法越好，比如：

例1：交换i和j的内容。

temp=i; i=j; j=temp;

以上三条语句的频度均为1，该程序的执行时间是与问题规模n无关的常数，因此算法的时间复杂度为常数阶，记作T（n）=O（1）

例2：冒泡排序。

for(i=1;i!=6;i++)

{

for(j=0;j!=6-i;j++)

{

if(a[j]>a[j+1])

{

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

}

}

时间复杂度为T(n)=O(n2)

例3：而快速排序则为O(nlog2n)

插入的话题：

2的3次方＝8

以2为底，8为指数的对数为3

如果考虑最差的情况 [8,7,6,5,4,3,2,1] 进行快速排序。 排序过程简述如下：

[ 3 2

[ 1 2

[ 1 2 1] 3] 3] 4 [8 7 6 5] 4 [[5] 6 [8 7]] 4 [[5] 6 [7 8]]

主体大概递归log2(n)次，而个子区的排序算法如下： for (; r <= nHigh - 1; r++)

{

if (a[r] <= nPivot)

{

l++;

Swap(a[r], a[l]);

}

}

约为O(n) ，所以总的时间复杂度为 O(nlog2n)

各种排序算法的时间复杂度如下：

冒泡法： 复杂度为O(n^2)

直接插入排序：O(n^2)

选择排序：O(n^2)

快速排序： log2(n)*n

归并排序：log2(n)*n

堆排序：log2(n)*n

希尔排序：n的1.2次幂

 

第二篇：vb算法总结(第三版)

计算机等级考试VB常用算法总结 一、求累加和

书中P77页例4-12 二、求阶乘

书中P78例4-14、P96习题 第8题， P132例6-11

三、随机数的产生 书中P51页

四、判一个数能否被另一个数整除 书中P77例4-13、P96第三题 五、数据交换 书中P66页例4-2

六、求素数、同构数、水仙花数、完数 素数：书中P84例4-22?X152例7=5 同构数例子：

编写一个程序,在装载窗体时,可将10—999之间的畴数添加到组合框中。由用户选择或由用户输入一个两位数或三位数整数，程序能判断出其是否为同构数。(2位同构数n应满足的条件是：n=n^2 mod 100；3位同构数n应满足的条件是：n=n^3 mod 1000)。 Private Sub Command1_Click() n = Val(Combo1.Text)

If n = n ^ 2 Mod 100 Or n = n ^ 2 Mod 1000 Then

Label1.Caption = "该数是同构数，因为：" + Str(n)+ "平方为" + Str(n ^ 2) Else

Label1.Caption = "该数不是同构数" End If End Sub

Private Sub Form_Load() For i = 10 To 999 Combo1.AddItem i Next i End Sub

水仙花数：P84例4-21； 完数：P96第11题。 七、比较数的大小 书中P68例4-4 八、数据的排序

选择排序：书中P101例5-2； 冒泡排序：书中P102例5-3

九、方程求解

书中P82例4-20为百元买百鸡问题；

P96第6题为猴子吃桃问题。 十、分段函数

书中P68例4-5；P70例4-6；P95第2题。 十一、斐波那契数列

书中P139第5题为递归方式做的； 用for循环做的方式为：

Private Sub Command1_Click() Dim a(30), b As Integer N = Int(Text1.Text) a(1) = 1 a(2) = 1

For i = 3 To N

a(i) = a(i - 1) + a(i - 2) Next i

For i = 1 To N b = b + a(i) Next i

Text2.Text = b End Sub

十二、最大公约数和最小公倍数 书中P80例4-16；P131例6-10

十三、利用数组求最大值、最小值和平均数 书中P99中5.2.3小节：一维数组的基本操作和5.2.4小节：一维数组的应用。 十四、复利计算

书中P81例4-17，注意公式P=P*（1+r）n 十五、数组参数传递 书中P142第6题 十六、输出打印问题

1、 杨辉三角：书中P105例5-4 2、 九九乘法表：书中P85例4-24 3、 打印数字金字塔：书中P96第9题 4、 打印矩形数列并查找行列最大： 书中P105例5-5

5、 打印*形三角形：书中P82例4-19

Gurr

20xx.5.17

1