数据结构-内部排序解读.ppt

1. 基本思想 快速排序是对冒泡排序的一种改进。通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对两部分记录继续进行快速排序，达到整个序列有序，是一种分治方法。 二、快速排序 10.3 快 速 排 序 2．算法 设待排序记录序列为：{L.r[s],L.r[s+1],…L.r[t]}。 (1)任意选取一个记录(通常可选第一个记录Lr[s])作为枢轴(或支点)(pivot)。 (2)将所有关键字较它小的记录都安置在枢轴之前，将所有关键字较它大的记录都安置在枢轴之后，在这个过程中存在两个记录的“交换”。 (3)以该“枢轴”记录最后所在的位置i作为分界线，位置i前的序列为{L.r[s],…,L.r[i-1]}，位置i后的序列为L.r[i+1],…,L.r[t]}。 (4)继续在两个序列上进行(1) ～(3)的操作。 二、快速排序 10.3 快 速 排 序 3．具体操作 (1)一趟快速排序 附设两个指针low和high，它们的初值分别指向序列的第1个记录和最后一个记录，设枢轴记录的关键字为pivotkey(pivotkey=L.r[low].key)。 a. 从high所指位置起向前有哪些信誉好的足球投注网站找到第一个关键字小于pivotkey的记录和枢轴记录互相交换； b. 从low所指位置起向后有哪些信誉好的足球投注网站，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换。 c. 重复这两步直至low=high为止。 二、快速排序 10.3 快 速 排 序 一趟排序结束，以枢轴为分界点将序列分为两部分，枢轴前的记录关键字小于枢轴记录的关键字，枢轴后记录的关键字大于枢轴记录的关键字。 (2)按照(1)的方法继续对所分两部分快速排序。 整过快速排序是一个递归过程。 初始关键字 49 38 65 97 76 13 27 49 4927 i(low) j(high) j 一次交换 27 38 65 97 76 13 49 49 4965 i i j 二次交换 27 38 49 97 76 13 65 49 4913 j j i 三次交换 27 38 13 97 76 49 65 49 4997 四次交换 27 38 13 49 76 97 65 49 i=j 完成一趟排序 27 38 13 49 76 97 65 49 i i j i j j 二、快速排序 10.3 快 速 排 序 1．算法描述 int Partition(Sqlist L,int low,int high) { pivotkey=L.r[low].key;L.r[0]=L.r[low]; while(lowhigh) {while(lowhighL.r[high].key=pivotkey) --high; L.r[low] ←→L.r[high]; L.r[low] =L.r[high]; While(lowhighL.r[low].key=pivotkey) ++low; L.r[low] ←→L.r[high]; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; } 二、快速排序 10.3 快 速 排 序 递归的快速排序算法： void Qsort(Sqlist L,int low,int high) {if(lowhigh) {pivotloc=Partition(L,low,high); //确定枢轴位置 QSort(L,low,pivotloc-1); Qsort(L,pivotloc+1,high); } } 二、快速排序 10.3 快 速 排 序 5. 算法分析 (1)稳定性 快速排序是不稳定的排序方法。 (2)时间复杂度 快速排序的时间复杂度为O(nlogn)数量级。 (3)空间复杂度 由于快速