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

本文为简书作者郑永欣原创,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很大,元素的关键字位数较少且可以分解时,采用基数排序较好。

原文链接:http://www.jianshu.com/p/3471b2dfa2b4

原文发布于微信公众号 - CDA数据分析师(cdacdacda)

原文发表时间:2016-09-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-367-Valid Perfect Square

2494
来自专栏Danny的专栏

HashMap实现原理及源码分析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

2.9K2
来自专栏Coding迪斯尼

面试算法:在未知长度的排序数组中进行快速查找

1132
来自专栏前端吧啦吧啦

涨薪必备Javascript,快点放进小口袋!

3137
来自专栏函数式编程语言及工具

Scalaz(12)- Monad:再述述flatMap,顺便了解MonadPlus

  在前面的几篇讨论里我们初步对FP有了些少了解:FP嘛,不就是F[A]吗?也是,FP就是在F[]壳子(context)内对程序的状态进行更改,也就是在F壳子(...

1957
来自专栏LanceToBigData

JavaSE(八)之集合概述

前几天其实一直在学习关于linux的内容和kvm虚拟化的知识。今天有时间来回顾一下集合相关的知识,接下来我将带大家一起来回顾一起集合关联的知识。 不要辜负自己花...

1875
来自专栏和蔼的张星的图像处理专栏

408. 二进制求和

给定两个二进制字符串,返回他们的和(用二进制表示) 样例 a = 11 b = 1 返回 100 非常惭愧还不是自己想来的算法,注意到几点: 1.数...

1732
来自专栏互联网开发者交流社区

Java逻辑

1464
来自专栏java初学

13.2 具体的集合

2769
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4425

扫码关注云+社区

领取腾讯云代金券