c语言学习之排序 数据结构 链表 堆排序 希尔排序 快速排序 递归排序
5星 · 超过95%的资源 需积分: 50 53 浏览量
2010-06-23
11:43:30
上传
评论 1
收藏 105KB DOC 举报 
四、快速排序（）
基本思想：
在当前无序区 中任取一个数据元素作为比较的基准不妨记为 ，用此基准将当前无序区
划分为左右两个较小的无序区：和 ，且左边的无序子区中数据元素均小于等于基
准元素，右边的无序子区中数据元素均大于等于基准元素，而基准 则位于最终排序的位置上，即
，当 和 均非空时，分别对它们进行
上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
排序过程：
【示例】：
初始关键字 !"##!#］
第一次交换后［# !"##!］
第二次交换后［# ##!!"］
$ 向左扫描，位置不变，第三次交换后［# ##!!"］
向右扫描，位置不变，第四次交换后［# #!#!"］
$ 向左扫描［# #!#!"］
（一次划分过程）
初始关键字［ !"##!#］
一趟排序之后［# ］［#!#!"］
二趟排序之后［］#［ ］［!"］#!［#］
三趟排序之后# ［!"］#!#%%
最后的排序结果# !"#!#%%
各趟排序之后的状态
&'()'(&(*(+,(-.,(/0/
1
()23(+-.4
./--.5/0/
1
%./--.5/0/66(+/0/7)2
%1
%/0/4
%8
%(+-.3(+/0/4
%./--.5/0/66(+-.53)2
%1
%-.4
%8
%(+/0/3(+-.4
8
(+-.3)24
(-.4
8
&'29:&(*(+,(-.,(/0/
1
()2'04
剩余15页未读，继续阅读
评论5
最新资源