论文部分内容阅读
摘要：现实生活中常常需要从大量信息中查找需要的信息。为使查找更加有效和便捷，需要按特定次序对信息预先排序后存储，如按字母排列、分门别类存放图书文献。排序广泛应用于数据处理、情报检索、商业金融等领域。排序是程序设计中处理数据最基本的算法之一。本文就常用排序方法讨论其基本思想、实现过程，对排序的稳定性以及时间复杂度和空间复杂度进行了分析。
关键词：排序算法；提高效率；复杂度
一、几种排序算法的比较
插入排序：每次把一个待排序的记录插入到已排序的序列中，直到所有的记录都插入为止。主要有直接插入排序和希尔排序，希尔排序的执行时间取决于增量序列。
交换排序：两两比较待排序的关键字，如果次序是反序的就交换，直到没有反序的记录为止。主要有冒泡排序和快速排序。
选择排序：每一次從待排序的记录中找出一个最小值放最前面，直到所有的记录都排好。
通过实例操作验证，在大数据下，排序时间从多到少的次序依次为：冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序。
二、排序的稳定性分析
如果排序前两个相同的数字间的位置关系与排序后的位置相同，那么这种排序算法是稳定的，反之是不稳定的。冒泡排序和直接插入排序属于稳定排序；直接选择排序、快速排序和希尔排序属于不稳定排序。
若排序码是关键码，则对任意待排序序列经排序后得到的结果是唯一的；若关键码不是主关键码，可能具有相同关键码的多个记录。
排序一般希望算法比较简单，占用辅助空间较小，运行时间短。每一种算法都有自己的优缺点，适合在某些特定的环境下使用。
三、时间复杂度和空间复杂度
评价一种排序方法的好坏，主要通过时间代价和空间代价衡量。排序过程中基本操作是关键码和记录的移动，所以时间代价是以关键码的比较次数和记录的移动次数衡量的，记录的数量和大小、排序表的大小、原始序列的排序状态都会影响排序时间。
直接插入排序，空间复杂度为O（1），时间复杂度为O（n2）；折半插入排序空间复杂度为O（1），定位一个关键码的位置需要比较次数至多为log2（n+1）次，时间复杂度为O（nlog2n）。折半插入排序只能减少关键字间的比较次数，而移动记录的次数和直接插入排序相同，故时间复杂度仍为O（n2）。这也是一种稳定排序方法，只适合顺序存储的排序表。交换排序的基本思想：通过排序表中两个记录关键码的比较，若与排序要求相逆，则将两者交换，直到没有反序的记录为止。
尽管快速排序的最坏时间为O（n2），但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快的，也因此称为快速排序，它的平均时间复杂度为O（nlgn）。
四、排序方法的选择
从算法实现来看，各种排序算法各有优缺点，没有绝对最优的。使用时要根据不同情况选用，还可以将多种方法结合使用。需要考虑的因素有：待排序的记录个数、每个记录的大小、关键字的结构和初始状态、对排序稳定性的要求、存储结构。
待排序记录个数n较小时，n2和nlog2n区别不大，可选用简单的排序方法。排序方法的选择主要根据以下情况来考虑：
第一，最适用于n值很大而关键字较小的序列，使用条件比较严格，需要知道各级关键字的取值范围，只适合整数和字符这类有明显特征的关键字。
第二，当排序按记录的主关键字进行时，排序方法是否稳定无关紧要；若排序按记录的次关键字进行，则必须采用稳定的排序方法。
第三，大多数排序方法采用顺序表来实现，若记录本身信息量较大，为避免移动记录耗费大量时间，可采用链式存储结构。
对常规排序方法适当改进可以提高效率，比如：鸡尾酒排序，是对冒泡排序的改进，效率有所提高，也叫定向冒泡排序。此算法与冒泡排序的不同处是先从低到高，再从高到低，最差时间复杂度O（n2），最优时间复杂度O（n），平均时间复杂度O（n2），所需辅助空间O（1），属于稳定排序。而冒泡排序仅从低到高逐个比较序列中的元素。
五、结语
排序主要是用来检索、选择、评估数据，把无序的数据或记录序列重新组织成按关键字排列的有序序列。影响排序速度的因素有多种，待排元素的应用领域、初始状态、数据的多少和大小等。根据不同情况灵活选择排序算法，才能提高排序速度、程序执行效率。随着对排序算法研究的深入，一定会有更多的优秀算法及理论被应用于实际工作中。
参考文献：
[1]张小莉，等.数据结构与算法（第3版）[M].北京：机械工业出版社，2014.
[2]严蔚敏，等.数据结构（C语言版）[M].北京：清华大学出版社，2011.
[3]连顺金.快速排序的一种改进算法[J].三明学院学报，2009，26（4）.
[4]陈琳琳，等.数据结构与算法（C语言版）（第3版）[M].北京：清华大学出版社，2015.
关键词：排序算法；提高效率；复杂度
一、几种排序算法的比较
插入排序：每次把一个待排序的记录插入到已排序的序列中，直到所有的记录都插入为止。主要有直接插入排序和希尔排序，希尔排序的执行时间取决于增量序列。
交换排序：两两比较待排序的关键字，如果次序是反序的就交换，直到没有反序的记录为止。主要有冒泡排序和快速排序。
选择排序：每一次從待排序的记录中找出一个最小值放最前面，直到所有的记录都排好。
通过实例操作验证，在大数据下，排序时间从多到少的次序依次为：冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序。
二、排序的稳定性分析
如果排序前两个相同的数字间的位置关系与排序后的位置相同，那么这种排序算法是稳定的，反之是不稳定的。冒泡排序和直接插入排序属于稳定排序；直接选择排序、快速排序和希尔排序属于不稳定排序。
若排序码是关键码，则对任意待排序序列经排序后得到的结果是唯一的；若关键码不是主关键码，可能具有相同关键码的多个记录。
排序一般希望算法比较简单，占用辅助空间较小，运行时间短。每一种算法都有自己的优缺点，适合在某些特定的环境下使用。
三、时间复杂度和空间复杂度
评价一种排序方法的好坏，主要通过时间代价和空间代价衡量。排序过程中基本操作是关键码和记录的移动，所以时间代价是以关键码的比较次数和记录的移动次数衡量的，记录的数量和大小、排序表的大小、原始序列的排序状态都会影响排序时间。
直接插入排序，空间复杂度为O（1），时间复杂度为O（n2）；折半插入排序空间复杂度为O（1），定位一个关键码的位置需要比较次数至多为log2（n+1）次，时间复杂度为O（nlog2n）。折半插入排序只能减少关键字间的比较次数，而移动记录的次数和直接插入排序相同，故时间复杂度仍为O（n2）。这也是一种稳定排序方法，只适合顺序存储的排序表。交换排序的基本思想：通过排序表中两个记录关键码的比较，若与排序要求相逆，则将两者交换，直到没有反序的记录为止。
尽管快速排序的最坏时间为O（n2），但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快的，也因此称为快速排序，它的平均时间复杂度为O（nlgn）。
四、排序方法的选择
从算法实现来看，各种排序算法各有优缺点，没有绝对最优的。使用时要根据不同情况选用，还可以将多种方法结合使用。需要考虑的因素有：待排序的记录个数、每个记录的大小、关键字的结构和初始状态、对排序稳定性的要求、存储结构。
待排序记录个数n较小时，n2和nlog2n区别不大，可选用简单的排序方法。排序方法的选择主要根据以下情况来考虑：
第一，最适用于n值很大而关键字较小的序列，使用条件比较严格，需要知道各级关键字的取值范围，只适合整数和字符这类有明显特征的关键字。
第二，当排序按记录的主关键字进行时，排序方法是否稳定无关紧要；若排序按记录的次关键字进行，则必须采用稳定的排序方法。
第三，大多数排序方法采用顺序表来实现，若记录本身信息量较大，为避免移动记录耗费大量时间，可采用链式存储结构。
对常规排序方法适当改进可以提高效率，比如：鸡尾酒排序，是对冒泡排序的改进，效率有所提高，也叫定向冒泡排序。此算法与冒泡排序的不同处是先从低到高，再从高到低，最差时间复杂度O（n2），最优时间复杂度O（n），平均时间复杂度O（n2），所需辅助空间O（1），属于稳定排序。而冒泡排序仅从低到高逐个比较序列中的元素。
五、结语
排序主要是用来检索、选择、评估数据，把无序的数据或记录序列重新组织成按关键字排列的有序序列。影响排序速度的因素有多种，待排元素的应用领域、初始状态、数据的多少和大小等。根据不同情况灵活选择排序算法，才能提高排序速度、程序执行效率。随着对排序算法研究的深入，一定会有更多的优秀算法及理论被应用于实际工作中。
参考文献：
[1]张小莉，等.数据结构与算法（第3版）[M].北京：机械工业出版社，2014.
[2]严蔚敏，等.数据结构（C语言版）[M].北京：清华大学出版社，2011.
[3]连顺金.快速排序的一种改进算法[J].三明学院学报，2009，26（4）.
[4]陈琳琳，等.数据结构与算法（C语言版）（第3版）[M].北京：清华大学出版社，2015.