Posts Tagged 排序算法
随机无序整数序列的逆序对数均值
Posted by kingsamchen in MATHEMATICS on 2011 年 09 月 22 日
首先需要了解逆序对的概念：如果在一个序列/数列中，满足
则ax和ay称为一对逆序对。
现在考虑一个问题：
对一个大小为N（即有N个元素）元素随机无序且唯一的整数序列中，平均有多少个逆序对？
一个构造证明的方法如下：
设一个随机无序且元素唯一的整数序列为
我们令Lr为L的反向序列，即
然后在Lr中任取两个数，设为ai和ak，且i<k，那么(ai,ak)组成的数对要么在Lr中是逆序对，要么在L中是逆序对
所以，Lr和L中的逆序对总数为
所以，L中逆序对的均值为
也就是说，N个元素的随机数列中逆序对数是O(N2)。那么这又有什么意义呢？
考虑排序问题，在通常升序排列的规定下，违反有序性质的元素都是某个逆序对的一部分。而基于邻位交换的排序算法的目的之一就是消除序列中的逆序对。
这意味着序列中基于邻位交换排序算法的时间复杂度和逆序对的数量是成正比的。
这也从另一个角度证明了基于邻位交换的排序算法的期望时间复杂度是平方级别的，典型的比如插入排序和冒泡排序。
非常规排序问题
Posted by kingsamchen in PROGRAMMING on 2011 年 04 月 08 日
让问题飞一会儿1
考虑如下问题：
描述：假设有一个包含最多n个正整数的文件，每个数均小于n，此处n=10^7.且每个数字至多只出现一次。
目标：设计一个算法，将文件中的正整数按升序排列输出。
条件：RAM大约在1MB，最大占用不超过1.5MB2，运行时间在10S内，无磁盘空间约束。
这个问题抽象自某个数据库系统对美国800免费电话的排序问题：
当时美国免费电话由区号800加7位数字构成。系统在某些时候需要对这些号码进行排序。
对这个问题认真思考后，我们来考虑一些由这个原问题得到的扩展问题。
扩展问题
Q1：为了解决原问题，需要相应测试数据。我们需要一个算法，该算法能够产生[0,n)间不重复的含有K个（0<K<=n）元素的整数序列.
Q2：原问题中，RAM最大的空间是1.5MB，若提供的空间严格的只有1MB，对应的算法应该怎样修改？
Q3：如果数字允许最多重复出现10次，算法又该如何改进？
Q4：现在美国免费电话的区号有：800、877和888。而且还有不断增加的趋势，如何用1MB内存对上述号码进行排序？
Q5：在Q4的条件下（不包含1MB内存约束条件），如何将这些号码保存在一个集合中，实现对给定号码的快速查找？
Q6：在大空间中，初始化需要消耗大量时间。设计算法避免初始化。新算法的访问时间复杂度应该是O(1)，且额外空间大小正比于排序数据大小。
原题分析
1.如果不考虑内存约束条件，即可以将10^7个整数全部读到内存中，在进行排序（比如QuickSort）。但是这个需要10^7 / 1024 / 1024 × 4 = 38MB。这个和允许的内存空间差距太大了。（感谢LittleHorse的debug 
）
2.如果采用基于磁盘文件的归并排序，则可以有效降低内存占用。
我们设一次排序K个数，那么有 K * 4 / 20^20 = 1.5 => K = 393216
我们可以一次读入35W个数据进行排序（内存中可以用QuickSort），得到输出文件后再利用MergeSort进行合并。
但是很不幸的，我们需要N = 10^7 / K = 29次文件I/O。
是否有算法既能降低内存要求又能避免大量的磁盘I/O？
3.回忆线性排序中的计数排序（CountSort），结合实际情况，我们考虑采用位向量（bitset）来表示数据。
bitset表示法即：假设v是一个位向量，用于表示非负整数。那么若第K个数存在，则v[k]为true，否则为false。
易知，1000W个数需要1000W bits = 1.2MB3，内存符合要求。
Read the rest of this entry »
比较排序法的极限和几种线性排序法
Posted by kingsamchen in PROGRAMMING on 2010 年 09 月 28 日
一、比较排序法的最优下界
比较排序法可能是我们接触的最频繁的排序算法类型了，典型代表有：插入排序，归并排序，堆排序和快速排序等等。
而这些排序算法的时间复杂度的最优情况是O(nlogn)。那么是否存在更优下界的比价排序法呢？答案是不存在的，因为比较排序法的最优下界便是O(nlogn)
我们可以通过建立“决策树”模型来进行分析
首先，一棵决策树是一棵满二叉树，用以表示对输入元素的比较情况，而忽略控制结构和数据移动
以插入排序
排序算法执行对应遍历一条从树的根到叶子的路径
因为任何正确的排序算法都必须能产生其输入元素的任何一种排列，所以n个元素的n!种排列都作为决策树的一个叶子
决策树中，决策树的高度和比较算法的最坏情况比较次数相等，即：决策树的高度的下界也是比较排序算法的下界
设一棵决策树高为h，有l个叶子，且这棵决策树对应n个输入元素，则
由斯特林近似公式可知：
Read the rest of this entry »
快速排序法补遗
Posted by kingsamchen in PROGRAMMING on 2010 年 09 月 10 日
KC之前写过有关快排的文章，但是那仅仅是基本的介绍，缺乏对快排更深入的了解。
而这个补遗在原有的基础之上对快排的一些有趣的问题进行了探讨和研究
PS：如果你没有看过之前的文章或者对快排并不熟悉，可以参见这里：http://blog.kingsamchen.com/archives/302
1、如何降序排列
其实这个不算一个问题- -||
对比排序的升降序通常只要改变比较的方式即可
比如在QS中，要将数组按照降序排列，只需要
if (nLow + 1 == nHigh)
{
if (Arr[nLow] < Arr[nHigh])
{
swap(Arr[nLow], Arr[nHigh]);
}
return;
}
for (int i = nLow; i < nHigh; ++i)
{
if (Arr[i] > nPivot)
{
++nVer;
swap(Arr[nVer], Arr[i]);
}
}
2、快排时间复杂度的极端情况分析
很容易知道，理想情况下QS是对半划分（即Pivot刚好是数组元素的中位数），那么它的递归表达式是
T(n)=2T(n/2)+Omega(n)
Read the rest of this entry »
堆与堆排序
Posted by kingsamchen in PROGRAMMING on 2010 年 08 月 21 日
1.什么是堆
这里的堆（二叉堆），指得不是堆栈的那个堆，而是一种数据结构。
堆可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。
如下图，是一个堆和数组的相互关系
二叉堆一般分为两种：最大堆和最小堆。两种堆内部的数据都要满足自己的特点。
比如最大堆的特点是，每个父节点的元素值都不小于其孩子结点（如果存在）的元素值，因此，最大堆的最大元素值出现在根结点（堆顶）
最小堆的性质与最大堆恰好相反
由于堆排序算法使用的是最大堆，所以我们这里以最大堆为例，最小堆情况类似，可以自己推导
对于给定的某个结点的下标i，可以很容易的计算出这个结点的父结点、孩子结点的下标，而且计算公式很漂亮很简约
但是这里有一个很大的问题：目前主流的编程语言中，数组都是Zero-based，这就意味着我们的堆数据结构模型要发生改变
Read the rest of this entry »
归并排序法概述
Posted by kingsamchen in PROGRAMMING on 2009 年 11 月 21 日
归并排序法（Merge Sort，以下简称MS）是分治法思想运用的一个典范。其主要算法操作可以分为以下步骤：
Step 1：将n个元素分成两个含n/2元素的子序列
Step 2：用MS将两个子序列递归排序（最后可以将整个原序列分解成n个子序列）
Step 3：合并两个已排序好的序列
易知，MS的关键在于Merge过程。对于这一过程的理解，算法导论中给出了一个形象的模型。
即假设桌面上有两堆已排序好的的牌，且每一堆都正面朝下放置。然后我们分别从两堆牌中选取顶上的一张牌（选取之后，堆顶端又会露出新的顶牌），选取较小的一张，放入输出堆，另一张放回。
重复这一步骤，最后直到一堆牌为空。由于两堆牌都是已排序，所以可知，只要将剩下的那堆牌盖到输出堆即完成整个排序过程。
小插曲：算法导论为了简化伪代码，在此处用了两张值为∞的哨兵牌。这样，除非两堆都露出哨兵牌，否则所取的两张牌中必有最小值。这一设想避免了检查每一个堆是否是空的，但是由于无法在程序中表示哨兵牌（或许可以，只是我不知道罢了），我们只能在实际算法中放弃这一设想。
对于A=<5，2，4，7，1，3，4，6>数组，MS的大致操作流程如下图：
[5] [2] [4] [7] [1] [3] [2] [6]
\ / \ / \ / \ /
[2 5] [4 7] [1 3] [2 6]
\ / \ /
[2 4 5 7] [1 2 3 6]
\ /
[1 2 2 3 4 5 6 7]
在递归的合并过程中，我们需要动态的创建一个缓存区，作为上面较小牌的输出堆。一次合并完毕之后，用缓存区的数据覆盖原始相应数组的数据。
Read the rest of this entry »
Something about the Merge Sort
Posted by kingsamchen in PROGRAMMING on 2009 年 11 月 15 日
由于昨天心情极端郁闷，恰好今天有点时间，就翻了下算法导论，在《算法深度分析》一章中出现了一个归并排序（MergeSort），于是看了下书上的伪代码，然后自己动手写了个。
不过由于书上的代码太过理想化，使用了一个哨兵牌，并赋予∞的值，而我又不知道这个东西在C++里怎么模仿，就干脆直接换用另一种方式。
于是硬着头皮，代码写完了，Debug的时候一直Stack Overflow，很郁闷，东改改，西改改，才最终搞定。
Read the rest of this entry »
快速排序法简述
Posted by kingsamchen in PROGRAMMING on 2009 年 08 月 20 日
RT，这两天写的，和上次那个三种常见排序遥相呼应~
快速排序法（Quick Sort）可以看做一种改进的冒泡排序法，由C. A. R. Hoare提出并发展而来。对于排序n个元素，QS的时间复杂度的期望值是[tex]O\left(nlog_{2}^{n} \right)[/tex],而且QS在实际中，一般比其他[tex]O\left(nlog_{2}^{n} \right)[/tex]的的算法还要快。虽然QS在排序一些比较有序或完全有序的元素时，会退化成冒泡排序，时间复杂度跃升至 [tex]O\left(n^{2} \right)[/tex]，但是这种情况是极少出现的。（要知道，在某些情况下，Insertion Sort的时间复杂度可以达到[tex]O\left(n \right)[/tex]！）
QS采用分治法（Divide and conquer）的策略逐一的把一个序列划分成两个子序列。其步骤可以概括为：
1.从序列中挑出一个元素，成为“基准”（Pivot），设下标为p。
2.遍历序列，使得小于p的元素放到一边，大于p的放到另一边（相等的可以放置到任意一边），将这个序列化分成两个子序列，这个操作成为“分割 ”（Partition）。即将数组A[L..H]分割成A[L...p-1]和A[p+1...H]，使得A[L..H]任意元素都小于等于A[p]，且小于等于A[p+1...H]。
3.递归此操作，将小于基准值的子序列和大于基准值的子序列排序。
Read the rest of this entry »
三种基础的排序算法
Posted by kingsamchen in PROGRAMMING on 2009 年 07 月 12 日
厄，KC的离开之作~昨晚写的~
先说下各排序法的思路：
冒泡排序法：
从第一个元素开始，逐次比较相邻量元素的大小，将大(小的)的弄到指定的一边。这样，一次处理完毕之后，必然有一个最值到了数组的一端。类似一个一个小气泡中，重的（或轻的）会飘到一端
重复这样的步骤即可将序列排序完整。不过冒泡存在正序和逆序两种写法。不同之处在于，处理思维是选择重数下沉还是轻数上浮
算法的时间复杂度是O(n2)
选择排序法：
选择排序法似乎是最容易想到的排序方法，其算法描述如下：
从一个含有n个元素的数组中，找到一个最小的元素（通过遍历比较），将它与第一个元素位置互换。再从剩下的那堆数组中找到最小的，将它与第二个元素位置互换。
重复以上步骤，即可将数组排序。
同样的，选择排序法的时间复杂度也是O(n2)
Read the rest of this entry »
LICENCE
COMMENTS