文档介绍：课程安排
排序概述
冒泡排序法
快速排序法
简单选择排序法
堆排序法
直接插入排序法
希尔(shell)排序法
合并排序法
排序算法的选择
排序概述
内部排序
外部排序
冒泡排序法
冒泡排序法的基本思想是:对待排序记录关键字从后往前(逆序)进行多遍扫描,当发现相邻两个关键字的次序与排序要求的规则不符时,就将这两个记录进行交换。这样,关键字较小的记录将逐渐从后面向前面移动,就象气泡在水中向上浮一样,所以该算法也称为气泡排序法。
冒泡排序法
冒泡排序法
为了提升冒泡排序法的效率,可对BubbleSort函数进行改进,当在某一遍扫描时,发现数据都已经按顺序排列了,就不再进行后继的扫描,而结束排序过程。
改进的冒泡排序法
快速排序法
快速排序使用分治策略来把待排序数据序列分为两个子序列,具体步骤为:
(1)从数列中挑出一个元素,称该元素为“基准”。
(2)扫描一遍数列,将所有比“基准”小的元素排在基准前面,所有比“基准”大的元素排在基准后面。
(3)通过递归,将各子序列划分为更小的序列,直到把小于基准值元素的子数列和大于基准值元素的子数列排序。
简单选择排序法
选择排序(Selection Sort)的基本思想:对n个记录进行扫描,选择最小的记录,将其输出,接着在剩下的n-1个记录中扫描,选择最小的记录将其输出,……不断重复这个过程,直到只剩一个记录为止。
堆排序法
堆是一个完全二叉树,树中每个结点对应于原始数据的一个记录,并且每个结点应满足以下条件:非叶结点的数据大于或等于其左、右孩子结点的数据(若是按从大到小的顺序排序,则要求非叶结点的数据小于或等于其左、右孩子结点的数据)。
由堆的定义可看出,其根结点为最大值,堆排序就是利用这一特点进行的。堆排序过程包括两个阶段:
(1)将无序的数据构成堆(即用无序数据生成满足堆定义的完全二叉树)。
(2)利用堆排序(即用上一步生成的堆输出有序的数据)。
堆排序法
堆排序法
直接插入排序法
插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后移动,为最新元素提供插入空间。