最新北京师范大学数据结构教学资料 第9章——排序PPT课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《最新北京师范大学数据结构教学资料 第9章——排序PPT课件.ppt》由会员分享,可在线阅读,更多相关《最新北京师范大学数据结构教学资料 第9章——排序PPT课件.ppt(129页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、140-140-2 2概述概述n排序排序:将一组杂乱无章的数据按一定的规律:将一组杂乱无章的数据按一定的规律顺次排列起来。顺次排列起来。 n数据表数据表(dataList): 它是待排序数据元素的有限它是待排序数据元素的有限集合。集合。n排序码排序码(key): 通常数据元素有多个属性域通常数据元素有多个属性域, 即即多个数据成员组成多个数据成员组成, 其中有一个属性域可用来其中有一个属性域可用来区分元素区分元素, 作为排序依据。该域即为排序码。作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码,要视每个数据表用哪个属性域作为排序码,要视具体的应用需要而定。具体的应用需要而定。14
2、0-140-9 90 1 2 3 4 5i = 4i = 5i = 30 1 2 3 4 5 temp1625*0 1 2 3 4 5 temp08140-140-10100 1 2 3 4 5i = 4 时的排序过程时的排序过程完成160 1 2 3 4 5 temp490 1 2 3 4 5 tempi = 4j = 3i = 4j = 2140-140-11 11250 1 2 3 4 5 temp25*0 1 2 3 4 5i = 4j = 1i = 4j = 0i = 4j = -10 1 2 3 4 5 temp21140-140-1212直接插入排序的算法直接插入排序的算法#in
3、clude dataList.htemplate void InsertSort (dataList& L, int left, int right) /依次将元素L.Vectori按其排序码插入到有序表/L.Vectorleft,L.Vectori-1中,使得/L.Vectorleft到L.Vectori有序。 T temp; int i, j; for (i = left+1; i = right; i+) if (Li = left & temp Lj); Lj+1 = temp; 算法分析算法分析n设待排序元素个数为设待排序元素个数为currentSize = n, 则该算法则该算法的
4、主程序执行的主程序执行n-1趟。趟。n排序码比较次数和元素移动次数与元素排序码排序码比较次数和元素移动次数与元素排序码的初始排列有关。的初始排列有关。140-140-1414n最好情况下,排序前元素已按排序码从小到最好情况下,排序前元素已按排序码从小到大有序,每趟只需与前面有序元素序列的最大有序,每趟只需与前面有序元素序列的最后一个元素比较后一个元素比较1次,总的排序码比较次数为次,总的排序码比较次数为 n-1, 元素移动次数为元素移动次数为0。n最坏情况下最坏情况下, 第第 i 趟时第趟时第 i 个元素必须与前面个元素必须与前面 i 个元素都做排序码比较个元素都做排序码比较, 并且每做并且每
5、做1次比较就要次比较就要做做1次数据移动。则次数据移动。则总排序码比较次数总排序码比较次数KCN和和元素移动次数元素移动次数RMN分别为分别为111122142221nininnniRMNnnniKCN/ )()( ,/ )(22140-140-1515n平均情况下排序的时间复杂度为平均情况下排序的时间复杂度为 o(n2)。n直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。n基本思想是基本思想是 : 设在顺序表中有一设在顺序表中有一 个元素序列个元素序列 V0, V1, , Vn-1。其中。其中, V0, V1, , Vi-1 是已经排好序的元素。在插入是已经排好序的元素。
6、在插入Vi 时时, 利利用折半搜索法寻找用折半搜索法寻找Vi 的插入位置。的插入位置。折半插入排序的算法折半插入排序的算法#include dataList.h 折半插入排序折半插入排序 (Binary Insertsort)(Binary Insertsort)140-140-1616template void BinaryInsertSort (dataList& L, const int left, const int right) /利用折半搜索, 在L.Vectorleft到L.Vectori-1中/查找L.Vectori应插入的位置, 再进行插入。 T temp; int i, l
7、ow, high, middle, k; for (i = left+1; i = right; i+) temp = Li; low = left; high = i-1; while (low = high) /折半搜索插入位置 middle = (low+high)/2; /取中点140-140-1717 if (temp = low; k-) Lk+1 = Lk; /成块移动,空出插入位置 Llow = temp; /插入 算法分析算法分析n折半搜索比顺序搜索快折半搜索比顺序搜索快, 所以折半插入排序所以折半插入排序就就140-140-1818平均性能来说比直接插入排序要快。平均性能来
8、说比直接插入排序要快。n它所需的它所需的排序码比较次数与待排序元素序列的排序码比较次数与待排序元素序列的初始排列无关初始排列无关,仅依赖于元素个数。在插入第,仅依赖于元素个数。在插入第 i 个元素时,需要经过个元素时,需要经过 log2i +1 次排序码比较次排序码比较, 才能确定它应插入的位置。因此,将才能确定它应插入的位置。因此,将 n 个元素个元素(为推导方便为推导方便, 设为设为 n=2k ) 用折半插入排序所进用折半插入排序所进行的排序码比较次数为:行的排序码比较次数为:n折半插入排序是一个稳定的排序方法。折半插入排序是一个稳定的排序方法。 1122log1logninni140-1
9、40-1919n当当 n 较大时,总排序码比较次数比直接插入排较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。序的最坏情况要好得多,但比其最好情况要差。n在元素的初始排列已经按排序码排好序或接近在元素的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的有序时,直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的元素移排序码比较次数要少。折半插入排序的元素移动次数与直接插入排序相同,依赖于元素的初动次数与直接插入排序相同,依赖于元素的初始排列。始排列。140-140-2020n希尔排序方法又称为缩小增量排序。该希尔排序方法又称为缩
10、小增量排序。该方法的基本思想是方法的基本思想是 : 设待排序元素序列有设待排序元素序列有 n 个元素个元素, 首先取一个整数首先取一个整数 gap n 作为作为间隔,将全部元素分为间隔,将全部元素分为 gap 个子序列,个子序列,所有距离为所有距离为 gap 的元素放在同一个子序的元素放在同一个子序列中,在每一个子序列中分别列中,在每一个子序列中分别希尔排序希尔排序 (Shell Sort)(Shell Sort)140-140-2121施行直接插入排序。然后缩小间隔施行直接插入排序。然后缩小间隔 gap, 例如例如取取 gap = gap/2 ,重复上述的子序列划分和,重复上述的子序列划分和
11、排序工作。直到最后取排序工作。直到最后取 gap = 1,将所有元,将所有元素放在同一个序列中排序为止。素放在同一个序列中排序为止。n开始时开始时 gap 的值较大,子序列中的元素较少,的值较大,子序列中的元素较少,排序速度较快排序速度较快; 随着排序进展,随着排序进展,gap 值逐渐变值逐渐变小小, 子序列中元素个数逐渐变多,由于前面工子序列中元素个数逐渐变多,由于前面工作的基础,大多数元素已基本有序,所以排作的基础,大多数元素已基本有序,所以排序速度仍然很快。序速度仍然很快。140-140-22220 1 2 3 4 5i = 1Gap = 3492516084925*0821252125
12、*16140-140-23230 1 2 3 4 5i = 2Gap = 2491625*082125140-140-24240 1 2 3 4 5i = 3Gap = 1dataList.h 希尔排序的算法希尔排序的算法140-140-2525void Shellsort (dataList& L, const int left, const int right) int i, j, gap = right-left+1;/增量的初始值T temp; do gap = gap/3+1;/求下一增量值 for (i = left+gap; i = right; i+) if (Li = lef
13、t & temp 1);算法分析算法分析nGap的取法有多种。最初的取法有多种。最初 shell 提出取提出取 gap = n/2 ,gap = gap/2 ,直到,直到gap = 1。knuth 提提出取出取 gap = gap/3 +1。还有人提出都取奇数。还有人提出都取奇数为好,也有人提出各为好,也有人提出各 gap 互质为好。互质为好。n对特定的待排序元素序列,可以准确地估算排对特定的待排序元素序列,可以准确地估算排序码的比较次数和元素移动次数。序码的比较次数和元素移动次数。140-140-2727n想要弄清排序码比较次数和元素移动次数与想要弄清排序码比较次数和元素移动次数与增量选择之
14、间的依赖关系,并给出完整的数增量选择之间的依赖关系,并给出完整的数学分析,还没有人能够做到。学分析,还没有人能够做到。 nKnuth利用大量实验统计资料得出利用大量实验统计资料得出 : 当当 n 很很大时,大时,排序码平均比较次数和元素平均移动排序码平均比较次数和元素平均移动次数大约在次数大约在 n1.25 到到 1.6n1.25 的范围内的范围内。这是。这是在利用直接插入排序作为子序列排序方法的在利用直接插入排序作为子序列排序方法的情况下得到的。情况下得到的。n希尔排序是一种不稳定的排序方法。希尔排序是一种不稳定的排序方法。140-140-2828交换排序交换排序 ( Exchange So
15、rt )( Exchange Sort )n基本思想是两两比较待排序元素的排序码,如基本思想是两两比较待排序元素的排序码,如果发生逆序果发生逆序(即排列顺序与排序后的次序正好相即排列顺序与排序后的次序正好相反反),则交换之。直到所有元素都排好序为止。,则交换之。直到所有元素都排好序为止。n基本方法是:设待排序元素序列中的元素个数基本方法是:设待排序元素序列中的元素个数为为 n。最多作。最多作 n- -1 趟,趟,i = 1, 2, , n- -1。在第。在第 i 趟中从后向前趟中从后向前,j = n- -1, n- -2, , i,顺次两两顺次两两比比较较Vj- -1.key和和Vj.key。
16、如果发生逆序,则交如果发生逆序,则交换换Vj- -1和和Vj。起泡排序起泡排序 (Bubble Sort)(Bubble Sort)140-140-29290 1 2 3 4 5140-140-30300 1 2 3 4 5起泡排序的算法起泡排序的算法template void BubbleSort (dataList& L, const int left, const int right) int pass = left+1, exchange = 1; while (pass = pass; j-) 140-140-3131 if (Lj-1 Lj) /逆序 Swap (Lj-1, Lj)
17、; /交换 exchange = 1; /标志置为1,有交换 pass+; 算法分析算法分析n第第i趟对待排序元素序列趟对待排序元素序列Vi-1,Vi,Vright进行排进行排序,序,结果将该序列中排序码最小的元素交换到序列的结果将该序列中排序码最小的元素交换到序列的第一个位置第一个位置(i- -1)。140-140-3232n最多做最多做n-1趟起泡就能把所有元素排好序。趟起泡就能把所有元素排好序。n在元素的初始排列已经按排序码从小到大排好在元素的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做序时,此算法只执行一趟起泡,做n-1次排序次排序码比较,不移动元素。这是最好的情形。
18、码比较,不移动元素。这是最好的情形。n最坏的情形是算法执行最坏的情形是算法执行n- -1趟起泡趟起泡,第第i趟趟 (1 i n) 做做n-i次排序码比较次排序码比较, 执行执行n-i次元素交换。次元素交换。在最坏情形下总的排序码比较次数在最坏情形下总的排序码比较次数KCN和元素和元素移动次数移动次数RMN为:为:11111233121nininninRMNnninKCN)()()()(140-140-3333n起泡排序需要一个附加元素以实现元素值的对起泡排序需要一个附加元素以实现元素值的对换。起泡排序是一个稳定的排序方法。换。起泡排序是一个稳定的排序方法。n基本思想是任取待排序元素序列中的某个
19、元素基本思想是任取待排序元素序列中的某个元素 (例如取第一个元素例如取第一个元素) 作为基准,按照该元素的作为基准,按照该元素的排序码大小,将整个元素序列划分为左右两个排序码大小,将整个元素序列划分为左右两个子序列:子序列:u左侧子序列中所有元素的排序码都小于或等左侧子序列中所有元素的排序码都小于或等于基准元素的排序码于基准元素的排序码 快速排序快速排序 (Quick Sort)(Quick Sort)140-140-3434u右侧子序列中所有元素的排序码都大于基准右侧子序列中所有元素的排序码都大于基准元素的排序码元素的排序码n基准元素则排在这两个子序列中间基准元素则排在这两个子序列中间(这也
20、是该这也是该元素最终应安放的位置元素最终应安放的位置)。n然后分别对这两个子序列重复施行上述方法,然后分别对这两个子序列重复施行上述方法,直到所有的元素都排在相应位置上为止。直到所有的元素都排在相应位置上为止。140-140-3535QuickSort ( List ) if ( List的长度大于的长度大于1) 将序列将序列List划分为两个子序列划分为两个子序列 LeftList 和和 RightList; QuickSort ( LeftList ); QuickSort ( RightList ); 将两个子序列将两个子序列 LeftList 和和 RightList 合并为一个序列合
21、并为一个序列List; 算法描述算法描述140-140-36360 1 2 3 4 5140-140-37370 1 2 3 4 5140-140-3838快速排序的算法快速排序的算法#include dataList.htemplate void QuickSort (dataList& L, const int left, const int right) /对元素Vectorleft, ., Vectorright进行排序, /pivot=L.Vectorleft是基准元素, 排序结束后它的/位置在pivotPos, 把参加排序的序列分成两部分, /左边元素的排序码都小于或等于它, 右边
22、都大于它 if (left right) /元素序列长度大于1时 int pivotpos = L.Partition (left, right); /划分 QuickSort (L, left, pivotpos-1);140-140-3939 QuickSort (L, pivotpos+1, right);template int dataList:Partition (const int low, const int high) /数据表类的共有函数 int pivotpos = low; T pivot = Vectorlow; /基准元素for (int i = low+1; i
23、= high; i+) /检测整个序列, 进行划分140-140-4040 if (Vectori pivot) pivotpos+; if (pivotpos != i) Swap(Vectorpivotpos,Vectori); /小于基准的交换到左侧去 Vectorlow = Vectorpivotpos; Vectorpivotpos = pivot;/将基准元素就位 return pivotpos;/返回基准元素位置算法分析算法分析140-140-4141 n算法算法quicksort是一个是一个递归的算法递归的算法, 其递归树如其递归树如图所示。图所示。n算法算法partition
24、利用序列第一个元素作为基准,利用序列第一个元素作为基准,将整个序列划分为左右两个子序列。算法中执将整个序列划分为左右两个子序列。算法中执行了一个循环,只要是排序码小于基准元素排行了一个循环,只要是排序码小于基准元素排序码的元素都移到序列左侧,最后基准元素安序码的元素都移到序列左侧,最后基准元素安140-140-4242到位到位, 函数返回其位置。函数返回其位置。n从快速排序算法的递归树可知,快速排序的从快速排序算法的递归树可知,快速排序的趟趟数取决于递归树的高度数取决于递归树的高度。n如果每次划分对一个元素定位后,该元素的左如果每次划分对一个元素定位后,该元素的左侧子序列与右侧子序列的长度相同
25、,则下侧子序列与右侧子序列的长度相同,则下 一步一步将是对两个长度减半的子序列进行排序,这是将是对两个长度减半的子序列进行排序,这是最理想的情况。最理想的情况。n在在 n个元素的序列中,对一个元素定位所需时个元素的序列中,对一个元素定位所需时间为间为 O(n)。若设。若设 t (n) 是对是对 n 个元素的序列进行个元素的序列进行排序所需的时间,且每次对一个元素正确定位排序所需的时间,且每次对一个元素正确定位后,正好把序列分为长度相等的两个子序列,后,正好把序列分为长度相等的两个子序列,140-140-4343n此时此时, 总的计算时间为:总的计算时间为:T(n) cn + 2T(n/2 )
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新北京师范大学数据结构教学资料 第9章排序PPT课件 最新 北京师范大学 数据结构 教学 资料 排序 PPT 课件
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内