排序算法比较与分析

一、常用排序算法简述

下面主要从排序算法的基本概念、原理出发,分别从算法的时间复杂度、空间复杂度、算法的稳定性和速度等方面进行分析比较。依据待排序的问题大小(记录数量  n)的不同，排序过程中需要的存储器空间也不同，由此将排序算法分为两大类：【内排序】、【外排序】。

内排序：指排序时数据元素全部存放在计算机的随机存储器RAM中。

外排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中还需要对外存进行访问的排序过程。

先了解一下常见排序算法的分类关系(见图1-1)

图1-1 常见排序算法

二、内排序相关算法

2.1 插入排序

核心思想：将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置，使数据元素依然有序，直到待排序数据元素全部插入完为止。

2.1.1 直接插入排序

核心思想：将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2 、i-3、 …  数据元素的值进行顺序比较，通过这种线性搜索的方法找到第i个数据元素的插入位置 ，并且原来位置 的数据元素顺序后移，直到全部排好顺序。

直接插入排序中，关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的，时间复杂度的最坏值为平方阶O(n2)，空间复杂度为常数阶O(l)。

2.1.2 希尔排序

核心思想：是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序时间复杂度会比O(n2)好一些，然而，多次插入排序中，第一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。

2.2 选择排序

核心思想：每一趟扫描时，从待排序的数据元素中选出关键码最小或最大的一个元素，顺序放在已经排好顺序序列的最后，直到全部待排序的数据元素排完为止。

2.2.1 直接选择排序

核心思想：给每个位置选择关键码最小的数据元素，即：选择最小的元素与第一个位置的元素交换，然后在剩下的元素中再选择最小的与第二个位置的元素交换，直到倒数第二个元素和最后一个元素比较为止。

根据其基本思想，每当扫描一趟时，如果当前元素比一个元素小，而且这个小元素又出现在一个和当前元素相等的元素后面，则它们的位置发生了交换，所以直接选择排序时不稳定的，其时间复杂度为平方阶O(n2)，空间复杂度为O(l)。

2.2.2 堆排序

堆排序时对直接选择排序的一种有效改进。

核心思想：将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶的数据元素和序列的最后一个元素交换;接着重建堆、交换数据，依次下去，从而实现对所有的数据元素的排序。完成堆排序需要执行两个动作：建堆和堆的调整，如此反复进行。

堆排序有可能会使得两个相同值的元素位置发生互换，所以是不稳定的，其平均时间复杂度为0(nlog2n)，空间复杂度为O(l)。

2.3交换排序

核心思想：顾名思义，就是一组待排序的数据元素中，按照位置的先后顺序相互比较各自的关键码，如果是逆序，则交换这两个数据元素，直到该序列数据元素有序为止。

2.3.1 冒泡排序

核心思想：对于待排序的一组数据元素，把每个数据元素看作有重量的气泡，按照轻气泡不能在重气泡之下的原则，将未排好顺序的全部元素自上而下的对相邻两个元素依次进行比较和调整，让较重的元素往下沉，较轻的往上冒。

根据基本思想，只有在两个元素的顺序与排序要求相反时才将调换它们的位置，否则保持不变，所以冒泡排序时稳定的。时间复杂度为平方阶O(n2)，空间复杂度为O(l)。

2.3.2 快速排序

快速排序是对冒泡排序本质上的改进。

核心思想：是一个就地排序，分而治之，大规模递归的算法。即：通过一趟扫描后确保基准点的这个数据元素的左边元素都比它小、右边元素都比它大，接着又以递归方法处理左右两边的元素，直到基准点的左右只有一个元素为止。

快速排序时一个不稳定的算法，其最坏值的时间复杂度为平方阶O(n2)，空间复杂度为O(log2n)。

2.4归并排序

核心思想：把数据序列递归地分成短序列，即把1分成2、2分成4、依次分解，当分解到只有1个一组的时候排序这些分组，然后依次合并回原来的序列，不断合并直到原序列全部排好顺序。

合并过程中可以确保两个相等的当前元素中，把处在前面的元素保存在结果序列的前面，因此归并排序是稳定的，其时间复杂度为O(nlog2n)，空间复杂度为O(n)。

2.5 基数排序

核心思想：首先是低位排序，然后收集;其次是高位排序，然后再收集;依次类推，直到最高位。

三、排序算法实测

图3-1 常用排序算法测试统计

四、排序算法对比与分析

表4-1各个排序算法比较

[直接插入排序]是对冒泡排序的改进，比冒泡排序快，但是只适用于数据量较小(1000 ) 的排序

[希尔排序]比较简单，适用于小数据量(5000以下)的排序，比直接插入排序快、冒泡排序快，因此，希尔排序适用于小数据量的、排序速度要求不高的排序。

[直接选择排序]和冒泡排序算法一样，适用于n值较小的场合，而且是排序算法发展的初级阶段，在实际应用中采用的几率较小。

[堆排序]比较适用于数据量达到百万及其以上的排序，在这种情况下，使用递归设计的快速排序和归并排序可能会发生堆栈溢出的现象。

[冒泡排序]是最慢的排序算法，是排序算法发展的初级阶段，实际应用中采用该算法的几率比较小。

[快速排序]是递归的、速度最快的排序算法，但是在内存有限的情况下不是一个好的选择;而且，对于基本有序的数据序列排序，快速排序反而变得比较慢。

[归并排序]比堆排序要快，但是需要的存储空间增加一倍。

[基数排序]适用于规模n值很大的场合，但是只适用于整数的排序，如果对浮点数进行基数排序，则必须明确浮点数的存储格式，然后通过某种方式将其映射到整数上，最后再映射回去，过程复杂。