没有合适的资源?快使用搜索试试~ 我知道了~
排序算法总结——最全、最新的排序算法
需积分: 14 8 下载量 107 浏览量
2011-05-25
12:59:47
上传
评论
收藏 61KB DOC 举报
温馨提示
试读
14页
里面包括了1插入排序(Insertion Sort)、2选择排序、3冒泡排序(BubbleSort)、4快速排序(Quick Sort)、5堆排序(Heap Sort)
资源推荐
资源详情
资源评论
排序算法总结
一、插入排序(Insertion Sort)
1. 基本思想:
每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然
有序;直到待排序数据元素全部插入完为止。
2. 排序过程:
【示例】:
[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
代码:
Procedure InsertSort(Var R : FileType);
//对 R[1..N]按递增序进行插入排序, R[0]是监视哨//
##Begin
# # for I := 2 To N Do //依次插入 R[2],...,R[n]//
# # begin
# ## #R[0] := R; J := I - 1;
# ## #While R[0] < R[J] Do //查找 R 的插入位置//
# ## # begin
# ## ###R[J+1] := R[J]; //将大于 R 的元素后移//
# ## ###J := J - 1
# ## # end
# ## #R[J + 1] := R[0] ; //插入 R //
# # end
##End; //InsertSort //
二、选择排序
1. 基本思想:
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的
数列的最后,直到全部待排序的数据元素排完。
2. 排序过程:
【示例】:
初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97
代码:
Procedure SelectSort(Var R : FileType); //对 R[1..N]进行直接选择排序
//
##Begin
# # for I := 1 To N - 1 Do //做 N - 1 趟选择排序//
# ###begin
# ## #K := I;
# ## #For J := I + 1 To N Do //在当前无序区 R[I..N]中选最小的元素
R[K]//
# ## # begin
# ## ###If R[J] < R[K] Then K := J
# ## # end;
# ## #If K <> I Then //交换 R 和 R[K] //
# ## ###begin Temp := R; R := R[K]; R[K] := Temp; end;
# ###end
##End; //SelectSort //
三、冒泡排序(BubbleSort)
1. 基本思想:
两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到
没有反序的数据元素为止。
2. 排序过程:
设想被排序的数组 R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻
气泡不能在重气泡之下的原则,从下往上扫描数组 R,凡扫描到违反本原则的轻气泡,就
使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。
【示例】:
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
代码:
Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序//
Begin
##For I := 1 To N-1 Do //做 N-1 趟排序//
# #begin
# ###NoSwap := True; //置未排序的标志//
# ###For J := N - 1 DownTo 1 Do //从底部往上扫描//
# ## #begin
# ## # If R[J+1]< R[J] Then //交换元素//
# ## ###begin
# ## ## #Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;
# ## ## #NoSwap := False
# ## ###end;
# ## #end;
# ###If NoSwap Then Return//本趟排序中未发生交换,则终止算法//
# # end
End; //BubbleSort//
四、快速排序(Quick Sort)
1. 基本思想:
在当前无序区 R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为 X),用此基准
将当前无序区划分为左右两个较小的无序区:R[1..I-1]和 R[I+1..H],且左边的无序子区
中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基
准 X 则位于最终排序的位置上,即 R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H),当 R[1..I-1]
和 R[I+1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元
素均已排序为止。
2. 排序过程:
【示例】:
初始关键字 [49 38 65 97 76 13 27 49]
第一次交换后
[27 38 65 97 76 13 49 49]
第二次交换后
[27 38 49 97 76 13 65 49]
J 向左扫描,位置不变,第三次交换后
[27 38 13 97 76 49 65 49]
I 向右扫描,位置不变,第四次交换后
[27 38 13 49 76 97 65 49]
J 向左扫描
[27 38 13 49 76 97 65 49]
(一次划分过程)
初始关键字
[49 38 65 97 76 13 27 49]
一趟排序之后
[27 38 13] 49 [76 97 65 49]
二趟排序之后
[13] 27 [38] 49 [49 65]76 [97]
三趟排序之后 13 27 38 49 49 [65]76 97
剩余13页未读,继续阅读
资源评论
alizee1025
- 粉丝: 0
- 资源: 7
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功