文档介绍：计算机数据结构
-排序
总目录
教学目标
排序的基本概念
选择排序
直接选择排序
堆排序
交换排序
气泡排序
快速排序
归并排序
各种内排序方法的比较
学习目标
本章主要介绍数据处理中各种排序方法。通过本章学习,要求同学们:
;
掌握每一种排序方法的机理,能够写出对已知一组数据的采用每一种排序方法的具体排序过程,能够画出建立初始堆所对应的完全二叉树和快速排序过程所对应的二叉搜索树;
掌握每一种排序方法所对应的具体算法描述,即能够理解和编写出来。
排序是把一组记录(元素)按照某个域的直的递增(即由大到小)或递减(即由小到大)的次序重新排列的过程。用于排序的域称为排序域或排序项,把该域中的每一个值(它与一个记录相对应)称为排序码。
若采用的排序方法使用排序后记录的相对次序不变,则称此排序方法是稳定的,否则称为不稳定的。
一组记录安排序码的递增或递减次序排列得到的结果称之为有序表。把排序前的状态称为无序表。
排序的基本概念
按照排序过程中所使用的内、外存情况不同,把排序分为内存排序和外存排序。
内排序:排序过程全部在内存中进行;分为:插入排序,选择排序,交换排序,归并排序,分配排序
外排序:排序过程需要不断的进行内存和外设之间的数据交换。
区别:
外排序速度比内排序速度要慢得多。对于一些较大的数据文件,由于内存容量的限制,不能一次装入内存进行内排序,只得采用外排序来完成。
选择排序
1直接选择排序
2堆排序
直接选择排序
直接选择排序是一种简单的排序方法。
它每次从待排序的区间中选择出具有最小排序的元素,把该元素与该区间的第一个元素交换位置。
第一次(即开始)待排序区间包含所有元素A[0]~A[n-1],经过选择和交换后,A[0]为具有最小排序码的元素;
第二次待排序区间为A[1]~A[n-1],经过选择和交换后,A[1]为仅次于A[0]的具有最小排序码的元素;
第三次待排序区间为A[2]~A[n-1],经过选择和交换后,A[2]为仅次于A[0]和A[1]的具有最小排序码的元素;
依次类推,经过n-1次选择和交换后, A[0]~A[n-1]就成为了有序表,整个排序过程结束。
总比较次数
总移动次数(最大值)
例如:假定n=8,数组A中8个元素的排序码为:
(36, 25, 48, 12, 65, 43,20, 58)
左图是进行每次选择并交换后各排序码位置的变动情况。
堆排序
堆排序是利用堆(大根堆)的特性进行排序的过程。
堆排序包括构成初始堆和利用堆排序这两个阶段。
构成初始堆就是把待排序的元素序列{R0 , R1 , R2 , …,Rn-1 } 按照堆的定义调整为堆{R0`, R1` , R2 `, …,Rn-1` },其中对应的排序码Si` >=S2i+1`和Si` >=S2i+2`,0<=i<=「n/2」-1 。为此需从对应的完全二叉树中编号最大的分支结点(即编号为「n/2」-1 的结点)起,至整个树根结点(即编号为0 的结点)止,依次对每个分支结点进行“筛”运算,以便形成以每个分支结点为根的堆。当最后对树根结点进行筛运算后,整个树就构成了一个堆。