第4章 常用算法――排序

零基础学算法第4章：常用算法——排序课程安排•4.1排序概述•4.2冒泡排序法•4.3快速排序法•4.4简单选择排序法•4.5堆排序法•4.6直接插入排序法•4.7希尔(shell)排序法•4.8合并排序法•4.9排序算法的选择4.1排序概述•内部排序•外部排序内部排序插入排序选择排序交换排序归并排序直接插入排序希尔排序直接选择排序堆排序快速排序冒泡排序4.2冒泡排序法冒泡排序法的基本思想是：对待排序记录关键字从后往前（逆序）进行多遍扫描，当发现相邻两个关键字的次序与排序要求的规则不符时，就将这两个记录进行交换。这样，关键字较小的记录将逐渐从后面向前面移动，就象气泡在水中向上浮一样，所以该算法也称为气泡排序法。从下向上扫描数据A[n]A[n-1]?交换A[n]和A[n-1]否是69237906569第1遍9237906569692906569376929069653769290696537692906965376第2遍第3遍第4遍第5遍4.2.1冒泡排序法4.2冒泡排序法为了提升冒泡排序法的效率，可对BubbleSort函数进行改进，当在某一遍扫描时，发现数据都已经按顺序排列了，就不再进行后继的扫描，而结束排序过程。4.2.2改进的冒泡排序法4.3快速排序法快速排序使用分治策略来把待排序数据序列分为两个子序列，具体步骤为：（1）从数列中挑出一个元素，称该元素为“基准”。（2）扫描一遍数列，将所有比“基准”小的元素排在基准前面，所有比“基准”大的元素排在基准后面。（3）通过递归，将各子序列划分为更小的序列，直到把小于基准值元素的子数列和大于基准值元素的子数列排序。696590379262854leftrightbase546569379262890rightbaseleft6969(a)(b)4.4简单选择排序法选择排序（SelectionSort）的基本思想：对n个记录进行扫描，选择最小的记录，将其输出，接着在剩下的n-1个记录中扫描，选择最小的记录将其输出，……不断重复这个过程，直到只剩一个记录为止。665903792692854628903792696554第1遍第2遍696590379262854原数据628379092696554第3遍628375492696590第4遍628375465699290第5遍628375465699290第6遍628375465699092第7遍4.5堆排序法堆是一个完全二叉树，树中每个结点对应于原始数据的一个记录，并且每个结点应满足以下条件：非叶结点的数据大于或等于其左、右孩子结点的数据（若是按从大到小的顺序排序，则要求非叶结点的数据小于或等于其左、右孩子结点的数据）。由堆的定义可看出，其根结点为最大值，堆排序就是利用这一特点进行的。堆排序过程包括两个阶段：（1）将无序的数据构成堆（即用无序数据生成满足堆定义的完全二叉树）。（2）利用堆排序（即用上一步生成的堆输出有序的数据）。69,65,90,37,92,6,28,544.5堆排序法696590379262854(a)696590549262837(b)696590549262837(c)699290546562837(d)926990546562837(e)123456781234567812345678123456781234567869,65,90,37,92,6,28,544.5堆排序法926990546562837(a)123456786990546562837(b)1234567926937546562890(c)123456792693754656(d)123456929028(e)(f)2861239290696554372829290696554376输出:输出:输出:输出:输出:14.6直接插入排序法插入排序（InsertionSort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后移动，为最新元素提供插入空间。696590379262854原数据：656990379262854第1次：656990379262854第2次：376569909262854第3次：376569909262854第4次：637656990922854第5次：628376569909254第6次：628375465699092第7次：4.7希尔排序法希尔排序又称为缩小增量排序，也属于插入排序类的算法，是对直接插入排序的一种改进。基本思想就是：将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使用需要排序的数列基本有序，最后再使用一次直接插入排序。这样，首先对数量较小的序列进行直接插入排序可提高效率，最后对基本有序的序列进行直拦插入排序，也可提高效率，从而使整个排序过程的效率得到提升。696590379262854原数据：增量为4696283792659054第1遍：增量为2286693790549265第2遍：增量为16283754656990924.8合并排序法合并排序（MergeSort）就是将两个或多个有序表合并成一个有序表。696590379262854原数据：656937906922854第1遍：376569906285492第2遍：343434628375465699092第3遍：34628375465699092第4遍：344.9排序算法的选择•1.选择基准–计算的复杂度–系统资源的使用–稳定度•2.各种排序算法的优缺点性格决定命运,专注成就人生