算法设计与分析第2章排序算法

《算法设计与分析第2章排序算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章排序算法主学习要点一、偏序集二、排序的一般方法三、堆排序四、快速排序五、线性时间排序六、中数排序主要内容2.1排序2.2堆排序2.3快速排序2.4线性时间排序2.5中数排序2.1排序2.1.1排序问题排序(Sorting)是最常见的一种典型非数值计算。排序问题的输入一个线性表，要求对该线性表的元素重排，是得表中的元素递增（或递减）排列1.偏序集设R是非空集合A上的二元关系，x,y,z∈R,如果R满足：1自反性（∨x∈A,(x,x)∈R)2反对称性((x,y)∈R∧(y,x)∈Rx=y)3传递性((x,y)∈R∧(y,

2、z)∈R(x,z)∈R)则称R为A上的偏序关系，记作≤2.原地置换排序算法排序算法利用输入的线性表在原地重排其中的元素，且没有额外的内存开销3.稳定排序算法排序后表中相同原始的相对位置没有发生改变4.内外排序根据排序是是否访问外存2.1.2冒泡排序第一轮109871097810798710987109871089781097810978910交换3次，循环3次第二轮第三轮交换2次，循环2次交换1次，循环1次Bubble_Sort(A)1fori1tolength[A]-12forjntoI3if(A[j]

3、)4swap(A[j],A[j-1]);5jj-16ii+1循环次数是1/2×(n-1)×n算法的复杂度O(n2)2.1.3交换排序交换排序的思路是每次用当前的元素同其后元素一一比较交换2.1.3交换排序第一轮109879108781097710987109879108781097810978910交换3次，循环3次第二轮第三轮交换2次，循环2次交换1次，循环1次Exchange_Sort(A)1fori0tolength[A]-12forjj=i+1tolength[A]3if(A[j]

4、j],A[i])5jj+16ij+1循环次数是1/2×(n-1)×n算法的复杂度O(n2)2.1.4选择排序选择排序是指先从数据中选择最小的同第一个值交换，再从剩下的部分中选择最小的与第二个值交换，如此反复直至所有的数据均有序。2.1.4选择排序第一轮109871098710987798107981079810789107810978910交换1次，循环3次第二轮第三轮交换1次，循环2次交换0次，循环1次Select_Sort(A)1intiTemp2intiPos;3fori0tolength[A]-14iTemp

5、A[i]5iPosI;6forji+1tolength[A]7ifA[j]

6、gth[A]-12dokeyA[j]3ij-14whilei>0andA[j]>key5doA[i+1]A[i]6ii-1;7A[i+1]key;2.2堆排序堆排序在最坏和平均情况下的时间复杂度都为O(nlogn)，而且它是一种原地置换的算法，即在任何时候，数组中仅有固定数目的元素存在数组外。2.2.1堆堆是一种数组对象，其定义如下：n个元素的序列{k1,k2,…,kn}当前仅当满足以下关系时，则称之为堆。(a)ki≥k2i(b)ki≤k2iki≥k2i+1ki≤k2i+1(a)是大顶堆(b)是小定堆2.2.2建堆

7、HEAPIFY是对堆进行操作的重要过程，其输入为一个数组A和小标i.当HEAPIFY被调用时，假定以LEFT(i)和RIGHT(i)为根的两棵子树都已是堆，A[i]可能小于其子女，这与堆得定义不符。只需要自上而下进行调整，将A[i]放到合适的位置，得到一个新的堆，称这种自堆顶至叶子的调整过程为“筛选”HEAPIFY(A,i,length)1lLEFT(i)2rRIGHT(i)3ifl<=lengthandA[l]>A[i]4thenlargestl;5elselargesi;6ifl<=lengthandA[r]>A

8、[largest]thenlargestr;8iflargest<>ithenswap(A[i],A[largest];HEAPIFY(A,largest,length);205101497318212345678910Build_Heap(A)1fori[length[A]/2]to