索引堆的实现与优化

在之前文章中记述了堆的实现（插入方式建堆、heapify方式建堆以及堆排序）《 堆的实现及其应用 》。今天来看看索引堆是个什么东西，对于我们所关心的这个数组而言，数组中的元素位置发生了改变。正是因为这些元素的位置发生了改变，我们才能将其构建为最大堆。 如果元素十分复杂的话，比如像每个位置上存的是一篇
作者：Administrator

堆的实现及其应用

本篇文章记述的是堆排序，这个名字看起来好像又要介绍一个排序算法，但是排序算法是次要的，主要的是一个数据结构——堆。堆排序问题就是堆这种数据结构所衍生出来的一个应用，我们先了解一下优先队列的概念。普通的队列就是满足先进先出、后进后出的一个结构。那么优先级队列呢？出队顺序和入队顺序无关，和优先级相关，这
作者：Administrator

关于快排和归并的思考

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此它也没有快排应用广泛。快速排序算法虽然最坏
作者：Administrator

快速排序及其优化

快速排序(Quick Sort)被称为20世纪对世界影响最大的算法之一，现在我们来看快速排序算法，习惯性把它简称为快排，快排利用的也是分治思想。乍看起来，它有点像归并排序，但是思路其实完全不一样。现在，我们先来看下快排的核心思想，最后将讲述快速排序的两个优化方案，其实还有一种三路快排的优化方案也是可
作者：Administrator

O(nLogn)的归并排序

之前几篇文章我介绍了三种O(n²)的排序算法《O(n²)的三个排序算法》（选择排序、插入排序和冒泡排序）以及它们的优化，然后顺便还写了一篇希尔排序的文章《插入排序的优化之希尔排序》，但是其实用的比较多的还是直接插入排序，它们比较适合于小规模数据的排序 。下面我将记录时间复杂度为nlog(n)的几种排
作者：Administrator

插入排序的优化之希尔排序

希尔排序是插入排序的一种，又称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，可以说它是插入排序的高级版。我们可以先回顾一下直接插入排序的过程： 排序前将第一个元素看成有序的数列 第1趟排序后：得到一个长度为2的有序数列 第2趟排序后：得到一个长度为3的有序数列 第
作者：Administrator

O(n²)的三个排序算法

今天复习下最简单的三个排序算法，一个是选择排序，一个是插入排序，一个是冒泡排序，三者时间复杂度都是O(n²)，通过分析来发现三者的优劣，以及对最好的情况和最坏的情况进行分析。 另外，这三中排序算法都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交
作者：Administrator

深入理解HashMap

一、什么是HashMap HashMap肯定是一个Java开发者经常用到的一个容器，不妨吧HashMap看成是Hash + Map Hash：散列讲一个任意的长度通过某种算法（哈希算法）转换为一个固定值 Map：这个Map被翻译过来是地图，地图是一种很明显的K-V模型，地图上的每一个点对应真实存在的
作者：Administrator

KMP其实也没那么难

Knuth-Morris-Pratt 字符串查找算法，简称为 KMP算法，KMP是我们经常听到的一种字符串匹配算法。KMP算法听起来很难，但是如果真正明白它的匹配过程其实不难，接下来看看KMP究竟是如何匹配字符串的？ 假设现在有如图所示两个字符串， 图表所列的是匹配串的所有子串，这个不难理解 <!-
作者：Administrator

常见排序的总结

插入排序 基本思想 每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，直到元素全部插完为止 <!-- more --> <!--more--> 直接插入排序 代码实现 //插入排序 void InsertSort(int *arr, int n) {
作者：Administrator
共 13 篇文章
页