数据结构-快速和堆排序

交换类排序和选择类排序起泡排序快速排序小结和作业交换类排序选择排序的基本思想简单选择排序堆选择排序基数排序交换类排序交换排序的基本思想：依次两两比较相邻关键字，并交换不满足排序要求的关键字，直至全部有序。主要应用：

1）起泡排序(BubbleSort)2）快速排序

(QuickSort)起泡排序假设在排序过程中，记录序列R[1..n]的状态为：第i趟起泡排序无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上起泡排序3065977613273801234567494938jj+19776971397279730jj+1jj+1jj+1jj+1jj+1jj+1第一趟起泡排序过程976576132730490123456738第一趟起泡排序后的结果起泡排序97657613273049012345673897657613273049012345673813762776307676第二趟976513273030490123456738136565307676第三趟276565971327303030490123456738494949307676第四趟6565134927起泡排序971327303030490123456738494949307676第四趟65651349279727301301234567384976第五趟65133827383830389730302701234567134976第六趟65383830起泡排序1.

每一趟起泡排序都是将待排序序列中最大的关键字移动到最后一个记录的位置上。2.

起泡排序的结束条件为，

最后一趟没有进行“交换记录”。3.一般情况下，每经过一趟“起泡”，“i减一”，但并不是每趟都如此。起泡排序例如:2553157989i=7i=613i=2起泡排序voidBubbleSort(ElemR[],intn){

i=n;//从1…i中找最大的，结果放到i

while(i>1){

lastExchangeIndex=1;

for(j=1;j<i;j++)//每趟需要比较的元素对的个数

if(R[j+1].key<R[j].key)

{

Swap(R[j],R[j+1]);

lastExchangeIndex=j;//进行交换的记录位置

}

//if

i=lastExchangeIndex;//本趟进行过交换的

//最后一个记录的位置

}

//while}//BubbleSort起泡排序-性能分析比较次数移动次数最好情况最坏情况0关键字在记录序列中顺序有序）：只需进行一趟起泡关键字在记录序列中逆序有序）：需进行n-1趟起泡O(n2)时间复杂度：稳定性：是一种稳定的排序方法n-1快速排序-基本思想

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。快速排序-基本思想首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。1436525861492397807501234567891052枢轴再进行快速排序再进行快速排序快速排序-划分目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且

R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)

枢轴

(i+1≤j≤t)。快速排序-划分80361458614952972375012345678910stR[0]=52lowhighhigh23lowlow80highhigh14lowlow52highhigh一趟快速排序过程：快速排序-划分1.(初始化)设置两个指针low和high

，它们的初值分别为区间的下界和上界；2.选取无序区的第一个记录R[low].key作为基准记录，并将它保存在变量pivotkey中；3.令high起向左扫描，直到找到第1个关键字小于pivotkey的记录R[high]，将R[high])移至low所指的位置上，这相当于R[high].key和基准R[0].key(即pivotkey)进行了交换，使关键字小于基准关键字pivotkey的记录移到了基准的左边，交换后R[high]中相当于是pivotkey

；

快速排序-划分4.然后，令low指针自low+1位置开始向右扫描，直至找到第1个关键字大于pivotkey的记录R[low]，将R[low]移到high所指的位置上，这相当于交换了R[low]和基准R[high]，使关键字大于基准关键字的记录移到了基准的右边，交换后R[low]中又相当于存放了pivotkey

5.接着令指针high自位置high-1开始向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至low==high时，low便是基准pivotkey最终的位置，将pivotkey放在此位置上就完成了一次划分。

快速排序-划分练习3865977613274901234567快速排序-划分intPartition(RedTypeR[],intlow,inthigh){}//PartitionR[0]=R[low];//枢轴pivotkey=R[low].key;

while(low<high){}while(low<high&&R[high].key>=R[0])--high;//从右向左搜索R[low]=R[high];while(low<high&&R[low].key<=R[0])++low;//从左向右搜索R[high]=R[low];R[low]=R[0];

returnlow;快速排序-算法void

QSort(RedType&R[],ints,intt)

{//对记录序列R[s..t]进行快速排序

if(s<t){//长度大于1

}}//QSortpivotloc=Partition(R,s,t);

//对R[s..t]进行一次划分QSort(R,s,pivotloc-1);//对低子序列递归排序，pivotloc是枢轴位置

QSort(R,pivotloc+1,t);//对高子序列递归排序快速排序-算法voidQuickSort(SqList&L){//对顺序表进行快速排序

QSort(L.r,1,L.length);}//QuickSort第一次调用函数Qsort

时，待排序记录序列的上、下界分别为1和L.length。快速排序-性能分析假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间：其中Tpass(n)为对n个记录进行一次划分所需时间，和记录数n成正比，可用cn表示。T(n)=Tpass(n)+T(k-1)+T(n-k)若待排序列中记录的关键字是随机分布的，则k

取1至n

中任意一值的可能性相同。快速排序-性能分析设Tavg(1)≤b则可得结果：结论:在所有同数量级O(nlogn)的排序方法中快速排序平均性能最好。由此可得快速排序所需时间的平均值为：快速排序-性能分析若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。为避免出现这种情况，需在进行一次划分之前，进行“予处理”：先对R(s).key,R(t).key和R[(s+t)/2].key，进行相互比较，然后取关键字为“三者之中”的记录为枢轴记录。或者，随机取一个作为枢轴快速排序-性能分析快速排序是一种不稳定的排序方法。快速排序需要的辅助存储空间为：R[0]执行栈,栈的大小？如果每次先对短的区间进行快速排序，则2log2n选择排序的基本思想选择排序的基本思想：每一趟从待排序的n-i+1（i=1,2,3,…,n-1）个记录中选出关键字最小的记录，作为有序序列中第i个记录，直到全部记录排序完毕。1.直接选择排序2.堆选择排序简单选择排序-基本思想假设排序过程中，待排记录序列的状态为：有序序列R[1..i-1]无序序列R[i..n]第i趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+1..n]简单选择排序-基本思想第i趟排序过程：1）第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]；2）该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第i个记录R[i]交换3）使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区

4913简单选择排序-例子6597761327381234567kjkjjjjkj49第一趟i=113i13简单选择排序-例子6597764927381234567kj第二趟：i=2jjjjk273827i13简单选择排序-例子65977649381234567第三趟：i=3j2765kjjj38k381365977649651234567第四趟：i=42738974949iik简单选择排序-例子136597769765

1234567第五趟：i=52738384976651365977697761234567第六趟：i=6273838497665971365977697971234567排序结果：27383849766597ii简单选择排序-算法voidSelectSort(ElemR[],intn){//对记录序列R[1..n]作简单选择排序。

for(i=1;i<n;++i){//排序的趟数

}}//SelectSortk=SelectMinKey(R,i);

//在R[i..n]中选择关键字最小的记录if(i!=k)R[i]←→R[k];//与第i个记录交换简单选择排序-性能分析1.对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为：2.移动记录的次数，当待排序列为正序数为最小，最小值为0。3.简单选择排序是一种不稳定的排序方法???待排序列为逆序数为最大，最大值为3(n-1)

。简单选择排序-讨论例：关键字序列T=（21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。原始序列：

21，25，49，25*，16，08第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16,

49，25*，25，2108，16,21，25*，25，4908，16,21，25*，25，4908，16,21，25*，25，49最小值08与r[1]交换位置交换，不稳定的简单选择排序-讨论例：关键字序列T=（21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。原始序列：

21，25，49，25*，16，08第1趟第2趟第3趟第4趟第5趟08，21，25，49，25*，1608，16,

21，25，49，25*

08，16,21，25,49,25*08，16,21，25，49,25*08，16,21，25,25*，49移动，稳定的堆的定义（13，38，27，50，76，65，49，97）1338275076654997（96，83，27，38，11，9）小顶堆96832738119大顶堆堆的定义堆是满足下列性质的数列{r1,r2,…，rn}：或(小顶堆)(大顶堆)若将此序列所存储的一维数组R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：

树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。堆的定义小顶堆：

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。大顶堆：

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。注意：

①堆中任一子树亦是堆。

②以上讨论的堆实际上是二叉堆(BinaryHeap)，类似地可定义k叉堆。堆排序可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值堆排序过程—以大顶堆为例1）将无序序列建成一个堆，得到关键字最大的记录；2）输出堆顶的最大值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次最大值3）重复执行，得到一个有序序列，这个过程叫堆排序堆排序堆排序需解决的两个问题：1.如何由一个无序序列建成一个堆？2.如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？堆排序—筛选第二个问题解决方法——筛选方法：1.输出堆顶元素之后，以堆中最后一个元素替代之；2.然后将根结点值与左、右子树的根结点值进行比较，并与其中大者进行交换；3.重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”13977665495027381397堆排序—筛选（97，76，65，49，50，27，38，13）65495027387697137613501365503849132797977627275049堆排序—筛选139765491327385076382738766565492738137697766513135038堆排序—筛选5049382713279797761313134927655049堆排序—筛选382713137697766513135049273827131313769776655049382713堆排序—筛选13131313769776655049382713堆排序—建立堆过程方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选将含8个元素的无序序列（49，38，65，97，76，13，27，50）调整成大顶堆。49386597761327501.先将无序序列建立完全二叉树堆排序—建立堆过程49386597761327502.按照上述算法过程，将下列序列调整成大顶堆。9750384997384976堆排序-课堂练习1、判断下列序列是否是堆，如果不是，请调整为堆a.100，85，98，77，80，60，82，40，20，10，66b.100，98，85，82，80，77，66，60，40，20，10c.100，85，40，77，80，60，66，98，82，10，20d.10，20，40，60，66，77，80，82，85，98，100堆排序—堆排序算法voidHeapSort(HeapType

&H){//对顺序表H进行堆排序}//HeapSortfor(i=H.length/2;i>0;--i)

HeapAdjust(H.r,i,H.length);//建大顶堆for(i=H.length;i>1;--i){H.r[1]←→H.r[i];//将堆顶记录和当前未经排序子序列

//H.r[1..i]中最后一个记录相互交换

HeapAdjust(H.r,1,i-1);//对H.r[1]进行筛选}堆排序—堆筛选算法void

HeapAdjust(RcdType

&R[],int

s,int

m){//已知R[s..m]中记录的关键字除R[s]之外均

//满足堆的特征，本函数自上而下调整R[s]的

//关键字，使R[s..m]也成为一个大顶堆}//HeapAdjustrc=R[s];//暂存R[s]for

(j=2*s;j<=m;j*=2)

{//j初值指向左孩子自上而下的筛选过程;}R[s]=rc;

//将调整前的堆顶记录插入到s位置堆排序—堆筛选算法if

(rc.key>=R[j].key)

break;//再作“根”和“子树根”之间的比较，

//若“>=”成立，则说明已找到rc

的插

//入位置

s，不需要继续往下调整R[s]=R[j];s=j;

//否则记录上移，尚需继续往下调整if

(j<m&&R[j].key<R[j+1].key)++j;//左/右“子树根”之间先进行相互比较

//令j指示关键字较大记录的位置堆排序-性能分析1.对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；2.对n个关键字，建成深度为h(=log2n+1)的堆，

所需进行的关键字比较的次数至多4n；堆排序-性能分析3.

调整“堆顶”n-1

次，总共进行的关键字比较的次数不超过

2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)

因此，堆排序的时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。辅助空间为O(1)

4.堆排序是一个不稳定的排序方法。堆排序-课堂练习2、请回答下列关于堆的问题堆的存储表示是顺序的还是链式的？设有一个大顶堆，即堆中任意结点的关键字都大于它的左右子女的关键字。其具有最大值的元素可能在什么地方对n个元素进行初始见堆的过程中，最多做多少次数据比较。基数排序基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。1.多关键字的排序2.链式基数排序多关键字排序n

个记录的序列{R1,R2,…，Rn}对关键字(Ki0,Ki1,…,Kid-1)

有序是指：对于序列中任意两个记录

Ri

和Rj(1≤i<j≤n)都满足下列(词典)有序关系：

(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中:K0

被称为“最主”位关键字Kd-1

被称为“最次”位关键字多关键字排序1.最高位优先MSD法先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，...…，依次类推，直至最后对最次位关键字排序完成为止。多关键字排序2.最低位优先LSD法先对Kd-1进行排序，然后对Kd-2

进行排序，依次类推，直至对最主位关键字K0排序完成为止。多关键字排序学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:

无序序列对K2排序对K1排序对K0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。链式基数排序例如：对下列这组关键字

{209,386,768,185,247,606,230,834,539}1.首先按其“个位数”取值分别为0,1,…,9

“分配”成10组，之后按从0至9的顺序将它们“收集”在一起；链式基数排序初始状态：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e