Binary-Search-Tree

我们都知道在一定程度上，程序 = 算法 + 数据结构。抛开数据结构说算法；抛开算法说数据结构，都是不太妥当的。而衡量一种数据结构的优略，一是看具体的问题需求，二是看其插入，删除排序等各个方面的性能。 在二分查找中我们使用的经典的数组实现，在查询的效率上直接达到了 lgN 对数级别的效率。但是数组这种 …

Binary-Search

二分查找也称为折半查找（Binary Search），是一种效率较高的查找方法。它的一般查找过程为：首先，需要将待查的线性表按关键字排序，然后将表中间位置的元素的关键字与查找关键字比较。如果二者相等，则查找成功。如果不相等，则使用表的中间位置元素将表分为左右两个子表，查找关键字大于中间位置元素的关键 …

Heap-Sort

1. 优先队列 学习堆排序前，需要先了解优先队列是什么东西，引出数据结构：堆，最后学习堆排序。优先队列和普通的队列一样是一种数据结构，普通队列遵循的原则就是先进先出（FIFO）。而优先队列则是无论入队顺序，当前队列中优先级最高的元素先出。谈到优先级就有两种确定优先级的策略，一是值小的优先级高，二是值 …

Quick-Sort

快速排序算法可能是应用最为广泛的算法，它的实现较为简单而且排序效率比大多数算法都要高。仅需要一个辅助栈就可以实现在原数组上原地排序。但是快速排序算法稳定性不高，如果使用不当经常可能使算法的时间复杂度提升至 O(n^2) 级别。如何正确使用和优化快速排序是使用它之前必须研究的问题。 1. 基本实现 快 …

Merge-Sort

顾名思义，并归排序是排序算法的一种，它的主要特点及思想就是体现在 “并归” 二字。并归排序中的并归的含义是指，将两个有序的数组并归组合成一个更大的有序数组。 而并归排序的思想就是将一个待排序数组（递归的）平均分割成两个子数组，然后分别给左右两个子数组排序，最后将排序结果并归起来，完成数组的排序。 …