版权所有,转载请注明出处,谢谢!
一个线性时间下的原地置换排序算法
排序算法
现有的线性时间排序(时间复杂度为ο(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)。但算法的稳定性方面,由于其位算法是不稳定的,因此整个算法也是不稳定的。
该算法经过我大量测试,其复杂度符合算法分析结果。
分享到:
相关推荐
**计数排序**是一种特殊的线性时间排序算法,适用于输入数据范围较小的情况。该算法假设输入元素为m个整数,这些整数的范围在[1, k]之间。计数排序的主要步骤包括: 1. **初始化计数数组**:创建一个大小为k的计数...
1. **分组与排序:** 将所有元素按照每 5 个一组进行分组,并对每个小组内的元素使用简单的排序算法(如冒泡排序)进行排序,以找到每组的中位数。 2. **选取基准值:** 对所有分组的中位数再次应用线性时间选择...
这通常优于其他如排序算法(如快速排序或归并排序),它们虽然在平均或最好情况下具有较低的时间复杂度,但在最坏情况下可能达到O(n log n)。线性时间选择算法不依赖于排序,而是通过一系列迭代步骤直接找到目标元素...
给定一个包含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)写出算法实现代码并截屏程序运行结果...
本资源提供的Java实现包括了三种线性排序算法:桶排序(Bucket Sort)、基数排序(Radix Sort)和计数排序(Counting Sort)。这三种算法在特定条件下可以达到线性的平均或最好时间复杂度,效率相对较高。 1. **桶...
线性时间排序算法主要指的是那些能在输入数据规模为n的情况下,以O(n)的时间复杂度完成排序的算法。其中,计数排序(Counting Sort)是这类算法的一个典型代表,尤其适用于特定条件的数据集。 计数排序是一种非比较...
此外,还有一种名为 radix sort 的线性时间排序算法,适用于整数排序。基数排序基于位运算,将整数按位分割,然后从最低位到最高位依次进行排序。通过多轮排序,最终可以实现整体的线性时间复杂度。 在实际应用中,...
这一理论下界意味着在纯比较的基础上,无法找到一个在所有情况下都能在O(n)时间内完成的排序算法。然而,存在非比较排序算法,如计数排序,可以达到线性时间复杂度。 计数排序是一种适用于特定场景的排序方法,它不...
本次实验旨在基于快速排序算法实现线性时间选择算法,并通过对比不同数据量的实验分析算法的时间复杂性。线性选择问题要求在给定的n个元素中找出第k小的元素,其中1≤k≤n。该问题的基本思想是对快速排序的改进,...
线性时间排序是一种高效排序方法,主要关注在特定条件下能够达到线性时间复杂度的排序算法。本章重点讲解了四种线性时间排序算法:计数排序、基数排序、桶排序,以及在平均情况和最坏情况下的比较排序算法。 首先,...
计数排序算法是一种高效的排序算法,它的运行时间是线性的,不需要递归,且对系统资源的占用也较小。这种算法的基本思想是对每一个输入元素x,确定小于x的元素个数,然后根据这个信息,将x放到它在输出数组中的正确...
前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入...“定理:对于含n个元素的一个输入序列,任何比较排序算法在最坏情况下,都需要做Ω(nlgn)次比较。” 也就是说,比较排序算法的运行速度不会
这些是线性时间复杂度的排序算法,适用于特定类型的数据。计数排序适用于非负整数,基数排序用于数字的每一位进行排序,桶排序则将数据分配到多个桶中分别排序,然后再合并。它们都不是原地排序,且对输入有一定的...
快速排序是一种高效的排序算法,采用分治策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子序列。 **时间复杂度分析**: - 最好情况:当每次划分都非常均匀时,快速排序的时间复杂度为 \(O(n\log ...
7. 计数排序、桶排序和基数排序:这些是线性时间复杂度的非比较排序算法,适用于特定类型的数据,如整数排序。 三、排序算法的时间复杂度 时间复杂度是衡量排序算法效率的重要指标,常见排序算法的时间复杂度如下:...
在计算机科学领域,排序算法是数据处理的核心技术之一,它用于将一组无序的数据元素按照特定的顺序排列。本文将深入探讨排序算法及其在数组中的应用,特别关注"sort"这个关键字,它通常指的是排序的过程。 一、排序...
本合集包含多种经典的排序算法,每种算法都是通过继承自一个基类并实现其具体逻辑来实现的。下面,我们将详细讨论这些排序算法及其原理。 1. 冒泡排序(Bubble Sort):冒泡排序是最基础的排序算法之一,通过不断...
堆排序的时间复杂度为O(n log n),是原地排序,但不是稳定的排序算法。 4)**归并排序**:归并排序是分治策略的一种体现,将数组分为两半,分别进行排序,然后合并两个已排序的子数组。时间复杂度稳定在O(n log n)...
这个压缩包文件“排序算法大集合”显然包含了多种排序算法的详细说明和实例,旨在帮助我们理解和掌握这些算法的运作原理以及它们在不同情况下的性能差异。 1. **冒泡排序**:这是一种简单的排序算法,通过重复遍历...
桶排序是一种分布式排序算法,它将数据分到有限数量的桶里,每个桶再分别排序,最后把所有桶中的数据合并。桶排序假设输入数据服从均匀分布,如果数据均匀分布在各个桶中,那么桶排序的时间复杂度可以达到线性的O(n...