Java编程

学堂在线数据结构视频

高级篇算法,包括 快速排序和希尔排序。首先介绍快速排序。

1. quicksort,C.A.R.Hoare (1934~)Turing Award,1980

2. 分治策略,分而治之

学堂在线数据结构视频

quicksort VS. mergesort

(1) 将序列分为两个子序列:S = S1 + S2 规模缩小,彼此独立(max(S1) = min(S2))

(2) 在子序列分别[递归地]排序之后,原序列自然有序 sorted(S) = sorted(S1) + sorted(S2)

(3) 递归基:只剩单个元素时,本身就是解

(4)mergesort的计算难点在于[合],quicksort的难点在于[分]

好我们来看看quicksort具体实现:

(1) 轴点pivot

左边的元素均不比它大;右边的元素均不比它小

(2)[划分] [lo, hi – 1] = [lo, mi – 1] + [mi] + [mi + 1, hi – 1];

算法构架如下

1 template typename T 2 void Vector T ::quicksort(Rank lo, Rank hi) 3 { 4 if (hi – lo 2) // only one element 5 { 6 return; 7 } 8 Rank mi = partition(lo, hi-1) // construct pivot 9 quicksort(lo, mi);10 quicksort(mi+1, hi);11 }

可见,最重要的是partition这一步

轴点:(1) 有可能不存在;

(2) 轴点本身必然是就位的。就位是说,它的左边的元素都不比它大,它右边的元素都不比它小

(3) 有序的序列中,所有元素均为轴点;反之亦然

因此,快速排序就是将数组中的每个元素逐个转化为轴点的过程

(4)通过适当的交换,可使任意元素转换为轴点

学堂在线数据结构视频

示意图如上。

排序算法(高级篇,整理自学堂在线邓俊辉老师《数据结构》课程)

标签:实现 nbsp ima 序列 .com con uic min 分享图片

原文:http://www.cnblogs.com/xiaoyajiang/p/7859318.html

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注