1.5 排序算法

1.5.1 快速排序

快速排序采用分治法的思想，首先把一个数值序列分为两个子序列，然后对两个子序列再进行分治法的思想。计算过程如下：

1、从熟知队列中选择一个基准元素。

2、将队列中的其他元素与基准元素比较，比基准元素小的元素放在基准元素的左边，比基准元素大的元素放在右边（降序排列则相反），则队列被基准元素划分为左右两个区间。

3、对两个区间的值分别递归步骤2，使其最终形成有序的序列。当区间小于等于1时，则会直接返回。

快速排序方法的时间复杂度及空间复杂度分析如下：

1、时间复杂度：最坏时间复杂度：O()，最优的时间复杂度：O(nlg n)，平均时间复杂度：O(nlg n)。

2、空间复杂度：快速排序的空间复杂度相对而言依然与具体的实现有关。

1.5.2 归并排序

归并排序时指两个已经有序的序列合并成一个有序序列的排序方式。归并排序可以采用迭代的方式进行排序。

假如有两组数值序列A、B，采用归并排序进行升序排列，则排列步骤如下：

1、申请存放最终合并后的数值序列存放空间，空间大小为数值序列A、B的空间之和。

2、初始化两个指针对应的值，分别指向数值序列A、B的首元素地址。

3、比较两个指针对应的值，将较小的值放入到最终存放空间，并移动较小值指针到序列的下一位置。

4、重复步骤3，直到某个指针已经指到序列的队尾，且没有元素可以和另一个序列进行比较。

5、将另一个序列的剩余元素直接复制到最终序列存放空间的末尾。

归并排序方法的时间复杂度及空间复杂度分析如下：

1、时间复杂度：最差时间复杂度：O(nlg n )，最优的时间复杂度：O(n)，平均时间复杂度：O(nlg n)。

2、空间复杂度：归并排序的空间复杂度与具体的实现相关，最差空间复杂度不应高于O(n)。

1.5.3 堆排序

堆排序时基于堆的数据结构实现的排序算法，分为小根堆和大根堆，最小堆的第0个元素是整个堆中的最小值，最大堆的第0个元素是整个堆中的最大堆。

由于堆的堆顶元素是最大值或最小值，所以可以利用此特性，每次从数组中直接选取出最大值或者最小值，使每次排序变得相对简单。堆排序的实现步骤可分为以下四步：

堆排序方法的时间复杂度及空间复杂度分析如下：

1、时间复杂度：最坏时间复杂度：O(nlg n )，最优的时间复杂度：O(nlg n )，平均时间复杂度：O(nlg n)。

2、空间复杂度：最差空间复杂度为O(n)。

1.5.4 基数排序

基数排序的原理是将数值按照位数切分为不同数字，然后对每位数分别进行比较，从而达到排序的目的，可以通过以下四个步骤完成。

基数排序方法的时间复杂度及空间复杂度分析如下：

1、时间复杂度：最差时间复杂度：O( )；

2、空间复杂度：最差空间复杂度为O()，n是元素个数，k是数值的位数，k值决定了需要进行多少轮处理。

以上四个排序为内排序，内排序是指能够在内存中完成的排序。

1.5.5 外排序

当计算机内存小于数据本身大小时，无法一次性将数据加载到内存，这个时候则需要采用外排序的方式。

外排序主要时针对大文件的排序，将需要排序的数据文件存放到存储器中，每次加载部分数据到内存，不断进行内存和外部存储器之间的数据交换，最终保证文件中的每个数据都完成排序。