版权所有,转载请注明出处,谢谢!
一个线性时间下的原地置换排序算法
排序算法
现有的线性时间排序(时间复杂度为ο(n)算法,比如计数排序,基数排序,桶排序等,虽然在时间复杂度上都能保持线性,但不能进行原地置换排序,需要额外的辅助空间.一个算法能否同时做到时间复杂度为ο(n),空间复杂度为Ω(1)呢?
我们知道,在现有的常规线性算法(计数排序,桶排序,基数排序等)当中,计数排序和桶排序因为不是原地置换排序,因此都需要额外的辅助空间来完成排序,因此无法达到上述目的,而基数算法本身是一个复合算法,如果能保证其位排序的算法能做到空间复杂度为Ω(1)和时间复杂度ο(n),那显然可以达到上述要求的算法目标.对于基数排序中的位排序要求必须具有稳定性.既要满足线性时间,常量空间,并且稳定的算法,在现有常用算法中还没有这种算法可以达到这种要求。
我们选基数排序作为实现这个算法目标的基本算法,由于我们进行的是整数排序,基数排序的位就是整数二进制表示里的位,而对于整数的二进制形式,每位上的数就只有0和1(这是个很有利的因素),而对0和1序列排序做到线性时间,只需要利用0作为基元,做一次快排划分即可,快排划分的算法时间复杂度是ο(n),而且也是原地置换排序,空间上的要求可以满足(Ω(1)),但问题在于对于基数排序,要求其位排序必须是稳定排序,而快排划分显然不是稳定的。但如果我们能找到一种方法将这种不稳定带来的影响消除,使得其不影响最终结果,问题就解决了。那么而怎样让快排划分不影响最终结果呢?
我们知道基数排序有两种基本的形式,一种是从低位到高位进行排序,一种是从高位到低位进行,经过分析发现,如果采用从高位到低位的方式进行,是可以让快排划分不影响到最终结果的,我们考虑一般情况,设B(k),B(k-1)….,B(1)表示一个基数排序所有的位(对于32位整数k=32),对第i位进行排序,而前m位(m=k-i-1)位已经排好序B(k)…B(i+1),在进行i位排序时,如果我们的快排划分只针对前m位相同的情况进行,则快排划分的结果显然不会影响最终结果.这样对于第i位上的一次快排,就可以转换成若干个小区间的快排划分(用前m位数进行划分,前m位相同的为一个区间),而且由于前m位已经排好序,那么显然前m位相同的都必然紧挨在一起,这种情况下虽然一次快排划分变成了p次快排划分(p<n),但整体上的时间复杂度并没有增加,虽然在具体的算法技巧处理时会考虑索引回溯,但时间复杂度不会改变,因为最极端的回溯小于等于n,因此时间复杂度最多为2n.而对于整数而言,前m位的获取和比较都非常快,所以在进行时间复杂度分析时可以不考虑,所以整体上算法每位上排序时间复杂度还是为32n到64n之间,而回溯通过一定技巧处理也可以消除,那么算法的时间复杂度就可以小于32n.由于这种位算法空间复杂度为Ω(1),因此整个算法满足前面提到的算法目标。
下面是具体的C#语言下的算法实现(为了减少交换次数,这里位排序不是严格按照快排划分进行,而是针对0和1的特点,用一个指针i指向序列第1个1,遍历指针在前,遇到0就与i交换,i随后右移一位,这可以大大减少交换次数):
private void BitSortAndDelRepeatorsA(int[] A)
{
//获取数组长度
int theN = A.Length;
//从高位到低位开始排序,这里从31位开始,32位是符号位不考虑,
//或者单独考虑。
for (int i = 31; i >= 1; i--)
{
//当前排序之前的值,只有该值相同才进行快排分组,如果不相同,
//则重新开始另外一次快排
//这很关键,否则快排的不稳定就会影响最后结果.
int thePrvCB = A[0] >>(i) ;
//快排开始位置,会变化
int theS = 0;
//快排插入点
int theI = theS-1;
//2进制基数,用于测试某一位是否为0
int theBase = 1 << (i-1);
//位基元始终为0,
int theAxBit = 0;
//分段快排,但总体上时间复杂度与快排分组一样.
for (int j = 0; j < theN; j++)
{
//获取当前数组值的前面已拍过序的位数值。
int theTmpPrvCB = A[j]>> (i);
//如果前面已排过的位不相同,则重新开始一次快排.
if (theTmpPrvCB !=thePrvCB)
{
theS = j;
theI = theS - 1;
theAxBit = 0;
thePrvCB = theTmpPrvCB;
j--;//重新开始排,回朔一位.
continue;
}
//如果前面的数相同,则寻找第1个1,thI指向其
//如果相同,则按快排处理
int theAJ = (A[j] &(theBase)) > 0 ? 1 : 0;
//如果是重新开始排,则寻找第1个1,并人theI指向其.这可以
//减少交换,加快速度.
if (theI < theS)
{
if (theAJ == 0)
{
continue;
}
theI = j;//Continue保证J从theI+1开始.
continue;
}
//交换.
if (theAJ <= theAxBit)
{
int theTmp = A[j];
A[j] = A[theI];
A[theI] = theTmp;
theI++;
}
}
}
}
算法分析
时间复杂度虽然有32*n,但由于32是个常数,因此整个算法的时间复杂度还是ο(n),空间复杂度方面,算法中只是利用了有限的几个交换变量(<20),因此空间复杂度为Ω(1)。但算法的稳定性方面,由于其位算法是不稳定的,因此整个算法也是不稳定的。
该算法经过我大量测试,其复杂度符合算法分析结果。
分享到:
相关推荐
排序算法的讲述。有关线性排序算法的讲述。
算法作业的线性选择排序 算法作业的线性选择排序 算法作业的线性选择排序
给定一个包含n个元素的一维线性序列a[p:r],从这n个元素中找出第k小的元素,1。设a[0:14]={2,9,11,3,14,7,10,8,15,4,13,1,6,5,12},k = 8,采用线性时间选择算法解决该问题。 1)写出算法实现代码并截屏程序运行结果...
线性时间排序算法.pdf
合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为O(nlogn)。在本次实验中将数据量提到5万的时候,该类算法运行时间仍在几毫秒左右,而上面的3种算法运行时间已经到达十几秒左右,效率...
前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入...“定理:对于含n个元素的一个输入序列,任何比较排序算法在最坏情况下,都需要做Ω(nlgn)次比较。” 也就是说,比较排序算法的运行速度不会
本资源包含桶排序,基数排序与计数排序三种线性排序算法
最快的排序算法 最快的算法而且不用递归!运行时间是线性的!,排序算法数据结构
进一步证明了当n为奇数时, n元Keccak类非线性变换是一个置换; 当n为偶数时, 不是一个置换。最后, 证明了当n为奇数时, n元Keccak类非线性变换不是全向置换、全距置换和正形置换, 为进一步应用这类编码模型奠定了理论...
线性时间运行的算法: 1.7 CountingSort: 假设数据分布在0到k之间的。对于每个输入x,确定出小于x的数的个数。假设小于x的数有17个,那么x就应该在第18个输出位置。 1. 8 Radix sort(基数排序):从最低位开始,每...
十大经典排序算法 编程界里面比较公认的十大经典排序算法可以分为两⼤类: ⽐较类排序:通过⽐较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为⾮线性时间⽐较类排序。 ⾮⽐较类排序:不...
线性时间选择问题,采用不生成随机数的算法
算法之线性时间选择 文档包括详细的算法分析与代码示例
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
主要在VC6.0上用MFC完成的排序算法和搜索算法: 首先弹出一个对话框,上面有排序前和排序后的编辑框,在排序前编辑框中输入整型数组,然后选择排序的方法,点排序按钮即将排序好的数组呈现在排序后的编辑框中。 排序...
此外,书中还包含了一个对线性ARMA模型的简洁介绍,为了说明如何运用非参数技术来揭示高维数据的局部结构,《非线性时间序列》借助了很多源于实际问题的具体数据,并注重在这些例子的分析中体现部分的分析技巧和工具...
线性时间选择,中位数算法,利用按每5个元素分组,分别找出其中位数,再递归找出
在快速排序算法基础上,进一步完成线性时间选择算法,并且用不同数据量进行实验对比分析,要求分析算法的时间复杂性并且形成分析报告
【问题描述】每次都是优化选出一个元素(分组后的中位数)为划分基准,在线性时间内寻找第i小元素。提示:分组时的组的个数为n/5的向下取整;分组后的中位数取第(num_group/2向上取整)小的元素。 【输入形式】在...
3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。 4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。 5. 若i==k,返回x;若i,在...