发表于 | 分类于
字数统计: 604 | 阅读时长 ≈ 2
引言前面介绍了很多的排序算法，他们都是基于比较的思想的排序算法。基于比较的排序算法的理论的时间复杂度下限为$O(NlogN)$。 计数排序是一种非基于比较的排序算法，对一定范围内的整数排序时，它的复杂度为$Ο(n+k)$（其中$k$是整数的范围）。当然这是空间换时间得到的。 算法思想计数排序的算法思 ...
阅读全文 »

发表于 | 分类于
字数统计: 592 | 阅读时长 ≈ 3
引论Merge是左堆那里引入的一个概念，意思是把两个堆合并成一个堆。这里我们把归并的思想引入到排序中，通过把两个已排序的数据表合并来对数据进行排序。 堆排序利用了递归的思想，它的最坏时间复杂度为$O(NlogN)$。如下图所示， 由上图可知，归并排序需要3个游标，每个游标指向数组的起始位置，通过比 ...
阅读全文 »

发表于 | 分类于
字数统计: 924 | 阅读时长 ≈ 4
引论人如其名，快速排序之所以称之为快速排序就是因为在实践中，这个算法是最快的排序算法。它的平均运行时间为O(NlogN)。最坏的时间复杂度为O(N^2)。虽然像堆排序，归并排序的时间复杂度比较低，但是他们的实际运行时间并不比快速排序快，反而由于有一些拷贝的进程，使运行时间变得很慢。快速排序也是一种d ...
阅读全文 »

发表于 | 分类于
字数统计: 1,611 | 阅读时长 ≈ 6
引论不相交集（Disjoint Set Union）是解决等价问题的一种有效的数据结构，之所以称之为有效是因为，这个数据结构简单（几行代码，一个简单数组就可以搞定），快速（每个操作基本上可以在常数平均时间内搞定）。 首先我们要明白什么叫做等价关系，而在这个之前要先有一个关系（relation）的定义 ...
阅读全文 »

发表于 | 分类于
字数统计: 526 | 阅读时长 ≈ 2
引论堆我们很熟悉，它有个很好的性质： 树的最小值在根节点上，对于子树依旧成立 因此堆排序的思想也就明确了： 把数据以堆的方式存储，然后依次输出根节点。这样就可以把数据按照从小到大的顺序排列出来了。如果需要从大到小排列，则只需要在构建堆的时候，使树的根节点为最大值就可以了。 由堆的性质我们可以得出，堆 ...
阅读全文 »

发表于 | 分类于
字数统计: 648 | 阅读时长 ≈ 2
引论前面讲了插入排序，算法很简单，但是效率很糟糕。因为每次要将一个新的值插入到他的位置时，需要挪动很多的元素，这个效率就很差了，因此为了改进插入排序的效率，Donald Shell于1959年发明的一种改进插入排序的排序算法，也就是希尔排序。 对于插入排序我们知道，要想打破插入排序的时间界，那么必须 ...
阅读全文 »

发表于 | 分类于
字数统计: 318 | 阅读时长 ≈ 1
引论选择排序也是一种非常简单的排序算法，它的思想是：依次找出无序数组中的最小值，然后把它放到已排序的数据的后面。 算法的时间复杂度为O(N^2)。另外选择排序是不稳定的。排序算法的不稳定是指，当待排序的数组中有相等元素时，当运行排序算法后，这组相等元素的位置发生改变，则称算法为不稳定的。当然稳不稳定 ...
阅读全文 »

发表于 | 分类于
字数统计: 985 | 阅读时长 ≈ 4
引论下面的几篇要集中整理一下排序算法。排序算法有很多种，思想各不相同，时间复杂度也不一样。这里先对要排序的数据做一些约束： 待排序的数据存放在数组中，且索引为从0开始 待排序的数据均为整数 之所以有这两个约束是为了简化算法，非整数数据只需做些许改动即可应用。下面介绍一种相当简单的排序——插入 ...
阅读全文 »

发表于 | 分类于
字数统计: 382 | 阅读时长 ≈ 1
引论这里来介绍一个应该算是最简单的排序算法—冒泡排序。冒泡排序的思想就是一次比较两个元素，如果元素的顺序错误，就交换着两个元素的位置，重复这一步骤直到没有错误的顺序为止。因为冒泡排序会使值比较小的元素从底部一步步的向上，知道顶部，就像小气泡从水中向上冒一样，因此取名冒泡排序。 算法流程 比较相邻的两 ...
阅读全文 »

发表于 | 分类于
字数统计: 1,193 | 阅读时长 ≈ 5
引论左堆的合并，插入，删除最小的时间复杂度为O(logN)。二项队列就是为了对这些结果进一步提高的一种数据结构。利用二项队列，这三种操作的最坏时间复杂度为O(logN)，但是插入的平均时间复杂度为O(1)。 二项队列二项队列不是一棵树，它是一个森林，由一组堆序的树组成的深林，叫做二项队列。 二项队列 ...
阅读全文 »