数据结构之算法排序与查询

当我们面临一堆数据时，我们就会想到如何对数据进行规范化的处理。首先肯定要将数据进行排序，一堆杂乱无章的数据肯定是不利于进行数据操作的，那么只有将数据进行科学、适当地进行排序，才能使数据在后续操作中更加快捷、方便和高效。

PS：本主题报告只在于告诉小白如何懂得算法排序与查询的简单原理，对于具体实现不加以过多的赘述。

接下来我将简单介绍八大排序算法

1.插入排序：简单插入排序、希尔排序

2.交换排序：冒泡排序、快速排序

3.选择排序：简单选择排序、堆排序

4.归并排序

5.基数排序

一、插入排序之简单插入排序

简单插入排序在往期的博客中本人介绍过，类似于大家斗地主，将混乱的手牌大到小或小到大理清楚。

基本原理：插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

二、希尔排序

希尔排序可以认为是一种升级版的快速排序。它引入了一个增量的概念。在简单插入排序中发现我们有些数据是不用进行扫描。因为每次进行简单插入排序时，都要从后往前进行扫描，这必然时间复杂度就会变大。

希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

那么希尔排序就是为了减少时间复杂度，具体如何操作呢请看如下：

我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 来表示。

三、交换排序之冒泡排序

冒泡排序顾名思义就跟它的名字一样，就像吐泡泡一样，从大到小，一个一个往上冒。

算法步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

PS：如果从头到尾的数据都没有进行交换，那么可以认为这个数据是有序的

 四、交换排序之快速排序

快速排序是冒泡排序的分而治之加递归的版本。它的排序速度是在所有排序中最快的。

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。——《算法艺术与信息学竞赛》

那具体是如何实现的呢？

算法步骤:

从数列中挑出一个元素，称为 "基准"（pivot）;（一般选最左边的为基准元素）

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

重复操作以上步骤，将子序列进行123的步骤

最难的是一次划分。

怎么将基准数左边的小于基准数，右边大于基准数

以一个数组作为示例，取区间第一个数为基准数。

以此数组为例

L为左指针（小于基准数时往右移，直到找到大于基准数的数字停止）

R为右指针 （大于基准数时往左移，直到找到小于基准数的数字停止）

假如72是我们的基准数，我们将72拿出来这时a[0]为空。

首先移动右指针，85大于72，R指针往左移，这时a[8]=48是小于72的那么将48这个值放到a[0]的位置上，也就是原来72拿出来的位置。注意这个时候a[8]已经为空

既然右边找到了一个，那么左边开始行动，左指针L向右移，发现直到a[3]=88才大于72，将88这个值放到a[8]的位置，这时a[8]=88,肯定a[3]为空,重复上面操作。。。

最后完成的第一次划分：

接下来采用分而治之的方法，将基准数72左边的子集和右边的子集也采用快速排序的方法。 

五、选择排序之简单选择排序 

 选择排序就很简单了，直接将算法步骤在下面展示：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

六、选择排序之堆排序

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

PS：在练习的过程中最容易考察的就是大顶堆、小顶堆如何构建或者堆排序算法的升序排列

（以下是大根堆的建立）

注意必须从非叶子结点开始，比如这里是22.

过程就是结点跟它的叶子结点进行比较，如果大于叶子结点，不进行更换，如果小于叶子结点，进行调换。直到根节点为最大数字，叶节点，为最小数字。

（大根堆最终实现）

七、归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

这个示意图就很直观的表现了归并排序的算法流程。

八、基数排序

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
② 从最低位开始，依次进行一次排序。
③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

 八大算法已经简单介绍完成，通过对网络各种较好的排序算法讲解加以介绍。

排序完成了那么，肯定需要进行查询，因为我们最终目的不是排序，肯定是查询这堆数据，加以利用。那么数据结构中有那几中查询呢？

当当当！查询算法一共有七种。

1. 顺序查找
2. 二分查找
3 .插值查找
4 .斐波那契查找
5 .树表查找
6 .分块查找
7 .哈希查找

一、顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

二、二分查找

元素必须是有序的，如果是无序的则要先进行排序操作。

基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

三、插值查找

在查找过程中为啥我们总是按照二分查找了，为什么我不能像翻字典一样，随机查找呢？我想从哪里查找就从哪里查找，于是引入我们的插值查找。

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

PS：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

四、斐波那契查找

大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中

基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

五、二叉树查找

基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
　　1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
　　2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
　　3）任意节点的左、右子树也分别为二叉查找树。

六、分块查找

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……

算法流程：
step1 先选取各块中的最大关键字构成一个索引表；
step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

七、哈希查找

算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

哈希函数：哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。可以通过一元二次函数进行理解，元素就是X，哈希值就是一般的Y。

算法流程：

1）用给定的哈希函数构造哈希表；
2）根据选择的冲突处理方法解决地址冲突；
常见的解决冲突的方法：拉链法和线性探测法。详细的介绍可以参见：浅谈算法和数据结构: 十一 哈希表。
3）在哈希表的基础上执行哈希查找。