算法和数据结构—— 查找和排序

CDA数据分析师

发布于 2018-02-24 17:25:43

1.4K0

发布于 2018-02-24 17:25:43

本文为简书作者郑永欣原创，CDA数据分析师已获得授权

查找和排序都是程序设计中经常用到的算法。查找相对而言较为简单，不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找。排序常见的有插入排序、冒泡排序、归并排序和快速排序。其中我们应该重点掌握二分查找、归并排序和快速排序，保证能随时正确、完整地写出它们的代码。同时对其他的查找和排序必须能准确说出它们的特点、对其平均时间复杂度、最差时间复杂度、额外空间消耗和稳定性烂熟于胸。

1、内排序：

插入排序：直接插入排序(InsertSort)、希尔排序（ShellSort）
交换排序：冒泡排序(BubbleSort)、快速排序(QuickSort)
选择排序：直接选择排序(SelectSort)、堆排序(HeapSort)
归并排序(MergeSort)
基数排序(RadixSort)

2、外排序：

磁盘排序
磁带排序

3、查找：

线性表的查找：顺序查找、折半查找（二分查找）、索引存储结构和分块查找
树表的查找：二叉排序树、平衡二叉树、B-树、B+树
哈希表查找

快速排序(QuickSort)

平均/最好时间复杂度：O(nlogn)

最差时间复杂度：O(n^2)

平均空间复杂度：O(logn)

最差空间复杂度：O(n)

稳定性：不稳定

时间复杂度分析：

快速排序总体的平均效果是最好的，当如果数组本身已经排好序或几乎有序的情况下，每轮排序又都是以最后一个数字作为比较的标准，那么排序的效率就只有O(n^2)。

空间复杂度分析：

快速排序通过递归来实现，递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

稳定性分析：

由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

排序思想：

快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

经典实现：

归并排序(MergeSort)

平均/最好/最差时间复杂度：O(nlogn)

平均空间复杂度：O(n)

稳定性：稳定

复杂度分析：

归并排序比较占用内存，但却是一种效率高且稳定的算法。

代码实现：

二分查找

平均/最差时间复杂度：O(logn)

平均查找长度ASL：log2(n+1) - 1

空间复杂度：O(1)

算法分析：折半查找要求线性表是有序表。另外，由于折半查找需要确定查找的区间，所以只适用于顺序存储结构，不适用于链式存储结构。为保持顺序表的有序，表的插入和删除操作都需要移动大量元素，所以折半查找特别适用于一旦建立就很少改动，又经常需要进行查找的线性表。

实现代码

索引存储结构和分块查找

索引存储结构

索引存储结构是在存储数据的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的结构一般形式为（关键字，地址）。

关键字唯一标识一个节点，地址是指向该关键字对应节点的指针，也可以是相对地址。

索引存储结构的优缺点

优点：线性结构采用索引存储后，可以对节点进行随机访问。在进行插入、删除运算时，由于只需要修改索引表中相关节点的存储地址，而不必移动存储在节点表中的节点，所以仍可保存较高的运算效率。

缺点：为了建立索引表需要增加时间和空间的开销。

分块查找

分块查找又称索引顺序查找，它是一种性能介于顺序查找和二分查找之间的查找方法。

分块查找需要按照如下的索引方式建立存储线性表：将表R[0.. n-1]均分为b块，前b-1块中元素个数为s=？n/b？，最后一块即第b块的元素个数等于或小于s；每一块的关键字不一定有序，但是前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是“分块有序”的。

分块查找的基本思路是：首先查找索引表，因为索引表是有序表，故可以用折半查找或顺序查找，以确定待查的元素在哪一块；然后在已确定的块中进行顺序查找（因块内元素无序，只能用顺序查找）。

采用折半查找来确定块元素所在块的平均查找长度ASL：log2(b+1) + s/2，s越小，即每块长度越小越好

采用顺序查找来确定块元素所在块的平均查找长度ASL：(b+s)/2 + 1，s=√￣n时，ASL取极小值√￣n+1，即采用顺序查找确定块时，各块元素个数取√￣n最佳。

分块查找的缺点：增加一个索引表的存储空间和建立索引表的时间。

冒泡排序（BubbleSort）

平均/最差时间复杂度：O(n^2)

最好时间复杂度：O(n)

平均空间复杂度：O(1)

稳定性：稳定

算法思想：

从最下面的元素开始，对每两个相邻的元素的关键字进行比较，且使关键字小的元素换至关键字大的元素之上，使得一趟排序后，关键字最小的元素到达最上端。

代码实现：

选择排序（SelectSort）

平均/最好/最差时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

性能分析：适用于从大量元素中选择一部分排序元素，例如从1w个元素中找出前10个元素

排序思路：

第i趟排序开始时，R[0 .. i-1]是有序区，而R[i .. n-1]是无序区。该趟排序是从当前无序区中选出关键字最小的元素R[k]，将它和无序区的第一个元素R[i]交换，使得R[0.. i]和R[i+1 .. n-1]变成新的有序区和新的无序区。

代码实现：

堆排序（heapSort）

平均/最好/最差时间复杂度：O(nlogn)

空间复杂度：O(1)

稳定性：不稳定

性能分析：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

排序思路：

堆排序是一种树形选择排序方法，在排序过程中，将data[1 .. n]看成一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。

代码实现：

void heapSort(int[] data, int length) { // 为了与二叉树的顺序存储结构一致，堆排序的数据序列的下标从1开始 if (data == null || length <= 0) throw new RuntimeException("Invalid Paramemers"); for (int i = length/2; i >= 1; i--) //初始化堆 sift(data, i, length); for (int i = length; i >=2; i--) { //进行n-1趟堆排序，每一趟堆排序的元素个数减1 swap(data, i, 1); //将最后一个元素同当前区间内data[1]对换 sift(data, 1, i-1); //筛选data[1]节点，得到i-1个节点的堆 } } void sift(int[] data, int low, int high) { int i = low, j = 2 * i; //data[j]是data[i]的左孩子 int tmp = data[i]; while (j <= high) { if (j < high && data[j] < data[j + 1]) //若右孩子较大，把j指向右孩子 j++; if (tmp < data[j]) { data[i] = data[j]; //将data[j]调整到双亲节点位置上 i = j; //修改i和j值，以便继续向下筛选 j = 2 * i; } else break; //筛选结束 } data[i] = tmp; //被筛选节点的值放入最终位置 }

插入排序（InsertSort）

平均/最差时间复杂度：O(n^2)

最好时间复杂度：O(n)

空间复杂度：O(1)

稳定性：稳定

算法思想：

每次将一个待排序元素，按其关键字大小插入到已经排好序的子表中的恰当位置，知道全部元素插入完成为止。

实现代码：

void insertSort(int[] data, int length) {    if (data == null || length <= 0) 
        throw new RuntimeException("Invalid Paramemers");    for (int i = 1; i < length; i++) {        int tmp = data[i];        int j = i-1;                      //从右向左在有序区data[0 .. i-1]中找data[i]的插入位置
        while (j >= 0 && data[j] > tmp) {
            data[j+1] = data[j];          //将大于data[i]的元素后移
            j--;
        }
        data[j+1] = tmp;
    }
}

希尔排序（ShellSort）

平均时间复杂度：O(n^1.3)

空间复杂度：O(1)

稳定性：不稳定

算法分析：希尔排序和插入排序基本一致，为什么希尔排序的时间性能会比插入排序优呢？直接插入排序在表初态为正序时所需时间最少，实际上，当表初态基本有序时直接插入排序所需的比较和移动次数都比较少。另一方面，当n值较小时，n和n^2的差别也比较小，即直接插入排序的最好时间复杂度O(n)和最差时间复杂度O(n^2)差别也不大。在希尔排序开始时，增量d1较大，分组较多，每组的元素数目少，故各组内直接插入排序较快，后来增量di逐渐缩小，分组数逐渐减少，而各组内的元素数目逐渐增多，但由于已经按di-1作为增量排过序，使表教接近有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。

代码实现：

基数排序（RadixSort）

平均/最好/最差时间复杂度：O(d(n+r))

空间复杂度：O(r)

稳定性：稳定

实现代码：

各种内排序方法的比较和总结

按平均时间复杂度将排序分为3类：

平方阶O(n^2)排序，一般称为简单排序，例如直接插入排序，直接选择排序和冒泡排序
线性对数阶O(nlogn)排序，如快速排序、堆排序和归并排序
线性阶O(n)排序，如基数排序（假定数据的位数d和进制r为常量时）

各种排序方法的性能

因为不同排序方法适应于不同的应用环境和要求，所以选择适合的排序方法应综合考虑下列因素：

待排序的元素数目n（问题规模）；
元素的大小（每个元素的规模）；
关键字的结构及其初始状态；
对稳定性的要求；
语言工具的条件；
存储结构；
时间和空间复杂度等。

没有一种排序方法是绝对好的。每一种排序方法都各有其优缺点，适用于不同的环境。因此，在实际应用中，应根据具体情况做选择。首先考虑排序对稳定性的要求，若要求稳定，则只能在稳定方法中选取，否则可以在所有方法中选取；其次要考虑待排序节点数n的大小，若n较大，则可在改进方法中选取，否则在简单方法中选取；然后在考虑其他因素。综合考虑以上几点可以得出的大致结论：

若n较小（如n<=50），可采用直接插入排序或直接选择排序。当元素规模较小时，直接插入排序较好；否则因为直接选择排序移动的元素少于直接插入排序，应选直接选择排序。
若文件初始状态基本有序（指正序），则应选用直接插入、冒泡或随机的快速排序。
若n较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序中较好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短；但堆排序所需的辅助空间比快速排序少，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的，若要求稳定，则可选用归并排序。
若要将两个有序表合并成一个新的有序表，最好的方法是归并排序。
在基于比较的排序方法中，至少是需要O(nlogn)的时间。而基数排序只需要一步就会引起r种可能的转移，即把一个元素装入r个队列之一，因此一般情况下，基数排序可能在O(n)时间内完成对n个元素的排序。但遗憾的是，基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合（例如实数型关键字）时，无法使用基数排序，这时只有借助于“比较”的方法来排序。由此可知，若n很大，元素的关键字位数较少且可以分解时，采用基数排序较好。