算法设计实例教程 第3章 排序算法.ppt

【例3.7】快速排序时间限制：1000ms内存限制：32MB问题描述用递归法实现快速排序算法，并将乱序数列变成升序。输入说明第一行输入数据元素的个数，第二行为待排序的数据元素，输入的数据之间空一格，最后一个回车。输出说明打印输出的时候空一格，尾数后没有空格。输入样例108536236729641195078输出样例21923364150677885963.6.2快速排序算法实现举例算法分析定义两个变量i和j为数组的下标，最开始时i=0，j=n-1，取出待排序序列中的第一个元素a[0]作为“基准”，即pivot=a[0]，然后从数组的最后一个元素开始依次与pivot比较，直到找到比pivot小的元素并且交换位置，同时i++，这时从数组元素a[i]开始依次与pivot依次比较，直到找到比pivot大的元素并且交换位置，如此交替进行直到i==j。第一轮快速排序结束，得到序列是以pivot为基准，左边的元素都比pivot小，右边的元素都比pivot大的序列。以此为基础，进一步对pivot的左右两侧的子序列进行重复的操作直至整个序列保持有序。时间复杂度：最坏情况时，每?次选取的基准元素都是最?或最?的，复杂度为O(n2)，最好情况时，每?次选取的基准元素都能平分整个序列，由于快排涉及到递归调?，所以时间复杂度为O(nlog2n)。平均情况下复杂度也是O(nlog2n)。空间复杂度：快速排序使?的辅助空间是O(1)，?消耗空间较大的是在递归调?的时候了，因为每次递归就要保留?些数据，每?次都平分数组的情况下空间复杂度为O(logn)，最差的情况下空间复杂度为O(n)，快速排序是不稳定排序。3.6.3快速排序算法分析排序算法通常可以分为比较类排序和非比较类排序，冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序都属于比较类排序，而计数排序、基数排序和桶排序都属于非比较类排序。每一种排序算法都有特定的使用情形，一般来说，选择合适的排序算法既取决于当前输入数据的规模，也取决于当前输入数据的状态。对于基本有序且规模较小的输入列表，使用高级算法会给代码带来不必要的复杂度，而性能的提升可以忽略不计。例如，对于较小的数据集，一般不使用归并排序，冒泡排序更容易理解和实现。如果数据已经被部分排好序了，则可以使用插入排序。对于较大的数据集，归并排序算法是最好的选择。表3-1为常见排序算法的时间复杂度和空间复杂度以及稳定性情况。3.7排序算法的性能比较3.7排序算法的性能比较排序方法时间复杂度（平均）时间复杂度（最坏）时间复杂度（最好）空间复杂度稳定性冒泡排序O(n2)O(n2)O(n)O(1)稳定选择排序O(n2)O(n2)O(n2)O(1)不稳定插入排序O(n2)O(n2)O(n)O(1)稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不稳定基数排序O(n*k)O(n*k)O(n*k)O(n+k)稳定希尔排序O(n1.3-2)O(n2)O(n)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定桶排序O(n+k)O(n2)O(n)O(n+k)稳定表3-1常见排序算法性能情况3.8本章小结排序是算法设计中一种重要的操作，其主要功能就是对一个待排序序列进行重新排列成按照数据元素某个属性值有序的序列。实现排序的两个基本操作：（1）比较。“比较”待排序序列中两个关键字的大小；（2）移动。“移动”记录。正如本章节开始所介绍的常见的排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。每种排序算法都有自己特点和适用场景，那么如何选择一种排序算法呢？一般来说：当待排序列中元素很少的时候，适合选用插入排序；当待排序列中所有的元素几乎有序，也比较适合选用插入排序；而如果着重考虑排序算法最坏情况，适合选用堆排序；当希望排序算法的平均性能比较好时，选用快速排序比较合适；当待排序列中元素从一个密集几何中抽取出的时候，适合选用桶排序；如果期望编写的代码尽可能简练，选择插入排序比较合适3.8本章小结**排序算法排序算法排序算法算法设计实例教程教学分析目录CONCENTS第3章排序算法第1章数据结构基础第2章基