专业课参考-数据结构

11设：R1，R2，R3，…，Rn是n递增：ki递减：ki非递减：ki非递增：ki2排序分

3排序分

4排序分

简单的排序方法先进的排序方法排序基本5KjKi＝KjRi仍领先于Rj，称所用方法是稳定的。13,27,38,49,49,65,76,97稳定排序的 委托队列（反映委托提交的时间先后按价格排((06,10.5),(09,10),(051,10),(033,9.8))#defineMAXSIZE20顺序表的最大长度typedefintKeyType；//定义关键字类型typedefstruct{KeyType}

otherinfo;//typedef RedTyper[MAXSIZE+1r[0int8}8 直 排 第i（i＞1）个记录时，前面的i-1个 „

ri-

„ 有序序 无序序 „

r'i-

„ 直 [初始关键

（49）38

97761327

97761327

（65）（38

761327

（97）（3849

1327

（76）（3849

76

27

（13）（1338

657697）27

（27）（132738496576（49）（13274849496576 StatusInsertSort(SqList&L{for(i=2;i<=L.length;++iif(LT(L.r[i].key,L.r[i-1].key)L.r[0].key //设置for(j=i-1;LT(L.r[0].key,L.r[j].key);--L.r[j+1]=L.r[j+1]=}

//记录 到正确位直排直排序算法是稳定 直 最好的情况（正序序列n“比较”次数=1n-的情况（逆序序列n“比较”次数=in

(n+2)(n-2n

“移动”次数2+(i-1)=( 平均复杂

如何改进直 在第i（i＞1）个记录时，前面i-1个记录已经排好序，在寻找位置时，可折 例 … …s

668585858585 m

85) 排序基本接排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接排序。 具体实现 然后取d2<d1，重复上述分组和排序操作；di=1，即所有记录放进一个组中排序 一趟排序结果 由于两趟的排序中，记录的关键字是 交换排序的基本反），则交换它们的位置。 反序

≤……≤rn-

1≤j≤i-

有序已经位于最终位初始第一趟排序第二趟排序后第三趟排序后第四趟排序第五趟排序第六趟排序后逐步减少减少总的比较次数和移动次较小记录从后面直接移动到 由此，以该“界点i为分界线，基本R[s..t被分割成两部分：R[s..i-1]无无序序无序子序列无序子序列快速排 无序子序列无序子序列将 到r[0]中，从high所指的位置lowlow所指位置起向后搜pivotkey的记录，到intPartition(SqList&L,intlow,inthigh{L.r[0]=pivotkey=while(low<high{while(low<high&&L.r[high].key>=pivotkey--L.r[low]=while(low<high&&L.r[&&].key<=pivotkey++low;L.r[high]=L.r[low];}L.r[low]L.r[0];returnlow;}//

枢轴返回枢轴pivotkey= 第一次交

8第二次交

pivotkey= 第四次交

第一趟完

子序列

low 子序列初始{}一趟快速排序{}{}分别进行快速{}{}结结{}{}{结}结有序序{}整个快速排序递归进QSort(SqList&L,intlow,inthigh//对表LL.r[low„high快速if(lowhigh 度大于{pivotloc=Partition(L,low,highL.r[low„high]一分为QSort(L,low,pivotloc-1//对低子表递归排序，pivotloc是界点位QSortLpivotloc+1high高子}}voidQuickSortSqList&L//对顺序表L QSort(L,1,} 快速排序特结构：顺时间复杂度为Onlog2n空间复杂度为O(log2n)情况：每次划分选择枢轴是最小或最大元 最好情况（每次划分折半 49 选择排序基本思有序序

无序序 „

ri-

交最小 „

ri-

ri+1

一趟简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换。voidSelectSort(SqList&L for(i=1;i<L.length;++i{j=SelectMinKey(L,i);if(i!=j)L.r[i]<=>}}对于n个关n-1选择排序。例： 初始：[

27j

一趟

[27 38]j [38[65[65[76[97排序结束简单选择排序算法的性能分移动次比较次

n-

1n(n-1)2

稳定性：是一种稳定的排序算法 改进的着眼点：如何减少关键码之间的比次数减少减少关键码间的比查找查找最小值的同时n元素的{k1，k2，……，kn}，当仅当满足以下关系时，称之为堆ki

ki

大根ki

ki>=

堆是什么东

i=1，2，……，n/2与二叉树的性质5增加了限制条件的完采用一维数大根堆的根结点所有结点的最大较大结

点，但不绝对

采用顺 采用顺 将堆用顺 结构 ，则堆对应一组序列。堆排⑴如何由一个无序序列建成一个堆（即初始建堆⑶如何调整剩余记录，成为一个新堆（即重建堆 1

用堆中最后 进

个元素替代

筛8 2

76 继 筛

76 继 输 76

76

76

输出

输出：13输出：13

输出：输出：1327输出：13 输出：输出：1327输出：132738输出：132738

输出：13输出：1327384950输出：13273849输出：13273849

输出：13输出：1327384950输出：132738495065 输出：输出：13273849506576后一个非终端结点是第n/2」个元素，由此筛选只需从第n/2」个元素开始。录，则可看成n有序的子序列，每个子两两合并n/2个长度21的有序子序再两两合如此重复，直至得到一个长度为n的有序序列为止。例初始关键一趟归并二趟归并后： 三趟归并后： 基数排

借助多关键字排序的方法对单关键字排包含多kk1,k2,…,kd的单关键字 最低位优例：对52 牌排<梅花,2><梅花,3>…<梅花<方块,2><方块,3>…<方块<红桃,2><红桃,3>…<红桃<黑桃,2><黑桃,3>…<黑桃排序方先按花色分类，再按面值分先按面值分类，再按花色分最优按花色（最）分梅花：13方块：13张红桃：13张黑桃：13每一堆按面值从小<梅花,2><梅花,3><梅花<方块,2><方块,3><方块<红桃,2><红桃,3><红桃<黑桃,2><黑桃,3>…<黑桃 最低位分配（按面值<梅花,2>梅花,3<梅花<方块,2>方块,3<方块<红桃,2>红桃,3><红桃<黑桃,2>黑桃,3><黑桃收集（按面值有序2：4张，3：4张，4：4张…A：4分配（按花色Initiallist：4691(按个) )收集：91319222((按) )收集：15223135468591

typedefsturctintnext;}

key[MAX_NUM_KEYtypedefsturctSLCellr[MAXSIZEintbitnum; intrednum;//记录个数}typedefintArrType[RADIX 基数排序的特间复O(d(n+r))稳排序算法小直直接排

平均时 最 辅助空间稳定 稳 稳 不稳 不稳归并基数

O(log