一个线性时间下的原地置换排序算法

版权所有，转载请注明出处，谢谢！

一个线性时间下的原地置换排序算法

排序算法

现有的线性时间排序(时间复杂度为ο(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)。但算法的稳定性方面，由于其位算法是不稳定的，因此整个算法也是不稳定的。

该算法经过我大量测试，其复杂度符合算法分析结果。