老狗啃骨头
@Veiking
2020-10-14
老狗啃骨头之算法-快速排序
快速排序，又称分区交换排序，简称快排。它也是一种交换排序，它是一种在处理大量数据方面有优势的算法。当数据量巨大的时候，冒泡排序这种中规中矩，挨次遍历逐个对比的玩法，估计会让人抓毛的，于是据说在公元1960年，一位叫东尼·霍尔（C. A. R. Hoare）的大神，沐浴斋戒，焚香祷告…..苦思冥想，终得所创
快速排序，又称分区交换排序，简称快排。它也是一种交换排序，它是一种在处理大量数据方面有优势的算法。当数据量巨大的时候，冒泡排序这种中规中矩，挨次遍历逐个对比的玩法，估计会让人抓毛的，于是据说在公元1960年，一位叫东尼·霍尔（C. A. R. Hoare）的大神，沐浴斋戒，焚香祷告…..苦思冥想，终得所创
冒泡排序是交换排序，是一种简单直观的排序算法。冒泡的算法原理是逐次循环遍历，比较两个相邻的元素，将小的（或大的）往前调。这样，每一轮都能得到一个最小的（或最大的），剩下的重复这个操作，最后完成排序。这个算法的名字，每轮这个逐个对比置换，很像那种气泡浮起，从水底慢慢浮到上面的样子，往上越晃荡越大，故曰“冒泡”
排序，就是将一组无序的数据，按照一定规则，使其有序化排列。排序时是否根据比较来决定元素间的相对次序，还可以分为比较类排序、非比较类排序。无论什么分类，都是尝试将其算法特征进行归纳，是为了方便我们学习的，融会贯通，这些名称分类即使以后都忘了，在设计程序算法的时候，也会潜移默化的影响着我们，这才是最后真正的目的
一般说，随着数据结构复杂度和解决问题的复杂度的增长，时间复杂度也是随之增长的。在相同的资源条件下，空间复杂度和时间复杂度决定了一个算法的好坏，实际运用过程中，我们还是可能会遇到空间换时间、时间换空间的情况，实际运用，很多情况下是没有最优、只有最合适的，只有精于计算、深刻理解，才好做出最恰当的算法设计
图也是典型的非线性数据结构，相较于树，更为复杂。线性表和树在逻辑结构上都是没有回路的，图就不一样了，图任意两个元素，都可以有关系。散列表又被称为哈希表，是一种键值对应的结构。我们最熟悉的身份证，也是这样的，每人给予一个数字编号，来对应这个人，基本是一一对应，通过数字化的编号来定位具体的人，要方便快捷的多得多
树在实际应用中非常广泛，较为具体的是，我们用到的Mysql数据库的索引，就是用B+树实现的；很多Hash结构，底层也是用到了红黑树。树是一种功能强大，但相对复杂一些的数据结构，在学习的过程中，可定是要多花些时间精力去深一下，在很多算法的优化上，也可以体会到树这种数据结构在实际运用中带来的乐趣
栈和队列也是比较常见的数据结构，它们是比较特殊的线性表。相对于数组和链表，栈和队列是一种更具特性的场景应用，栈和队列都可以用数组或链表进行具体的实现。栈和队列都是比较特殊的线性结构，不同但具有典型的模型特点。栈是只有一个出入口，先进后出，后进先出；队列是两头开，一头进一头出，先进先出
数组的优点是查找快遍历快；缺点是用的时候要先初始，不支持扩容，添加删除元素比较慢。适用于频繁查询，增删操作较少，对空间要求相对节约的场景。链表的优点是用的时候不需要初始，并可以随意增删元素，也没有长度限制；缺点是额外的指针域，会占用较多的空间，遍历起来也会相对数组更为耗时。适用于数据量相对较小，增删操作相对频繁的场景
天地玄黄，宇宙洪荒……千年以前，南梁周大侍郎，用一夜白头给我们留下了包罗万象又朗朗上口的童谣，得以千年唱诵，这是古人原始纯真的智慧。但浩瀚如宇宙，细微如尘沙，世间如此繁杂，计算机是搞不懂的，计算机的一零世界努力模拟，也只能抽象抽象再抽象。抽丝剥茧，先贤们给我们总结出了八种主要的数据结构，来支撑现实世界和计算机世界的关联
我们存在的现实世界，是具象的，生活中的各种东西，是几十年反复加强的概念，锅碗瓢盆啤酒饮料矿泉水…但计算机是一个抽象世界，计算机是尝试用抽象的数据，来描述这个具象的世界，我们说，学计算机、学编程，这个东西一定要搞好，现实世界里的概念是如何在计算机里体现的，这时候，数据结构，就是这个体现最基础的东西，其重要性不言而喻
