最近,发现了一种新的阵列排序方法,初测其速度是快速排序法的近50倍,这算是一种发明吗?请各位大神赐教!
下面，为了便于区别说明将这个新方法暂且称之占位排序法；
用javascript指令码语言实现快速排序法和占位排序方法之后,然后在同一台（较老旧的，ｃｐｕ是AMD推土机）电脑上，用ie浏览器执行，样本1000时，快速排序法和占位排序法所耗时分别是：18毫秒、15毫秒；样本10000时，所耗时间分别是：95毫秒、80毫秒；样本100000时，耗时分别是：2405毫秒、407毫秒；样本1000000时，耗时分别是：190888毫秒、3962毫秒；占位方比快排法在对100万资料进行排序时,快了近50倍!!!当然,这还是小试牛刀,如果段内再次分段的话,在TB级别的可可以吊打传统的所有排序方法的实力。
占位排序法的理念是：一是，只对阵列全域性作一次遍历，以后每次只遍历阵列的一小部分；二是，把资料的迁移次数降至极致。
占位法的实现方法是：
分段处理、选取代表、萝卜占位、先乱后治、小马快跑、多看少动;
将一个大的阵列分割成多个段；首先，要在各段资料p内明确锚点位；其次，锚点位的确定要遵守一个预先明确的固定规范;
其特征还在于，在锚点位上储存的资料不仅要体现自身的资料特征,还要能体现所在段p共同的资料特征。
举例:如果在段p内,继续分段p_;假设一个索引地址m; m即是段p的锚点位,又是p_的锚点位,那么在索引m存放的资料,要求必须同时体现:自身的资料征、段ｐ的共同的资料特征、段p_的共同的资料特征；如果对锚点位的资料操作直接作用在需要排序的资料集合上，称之为内建锚点(以下所有例项如无特别说明均采用内建锚点的方式)；如果对锚点位的资料进行的操作,还需要额外的对映在另外一个数据集合上，则称之为外建锚点。
列举一个例项,做进一步说明:要从大到小重新排序一个数组A;阵列A有100个元素:资料d,规定从A[0]开始每5个数据为一组p_;同时,从A[0]开始每15个数据为一组p;这样一个p内就有3个p_;更进一步,规定每个段的第一个索引对应段的锚点位;那么,A[0]是p的锚点位,又是p_的锚点位;则,A[5]是p_的一个锚点位,而不是p的锚点位;假设初始状态：A[0]存放的资料为5、A[３]为6、A[７]为9、A[12]为8，其他资料均为2；为了在排序过程中,减少遍历和迁移资料的数量,选择最大值来表达每一段资料的共同属性;这样在p_内，A[0]和A[３]的资料值要进行交换；在p内，A[0]和A[7]的资料值还要进行交换，优选的，不仅交换A[0]和A[7]的资料值，还要对A[0]至A[4]与A[5]至A[9]，两个p_段内的资料进行整理,使A[0]至A[9]中最大的5个数迁移至A[0]至A[4]中,A[0]至A[9]中最小的5个数迁移至A[5]至A[9]中;最后的结果为:A[0]为9、A[5]为2、A[10]为8。
所述的萝卜占位,指的是“一个萝卜、一个坑”的占位理论在计算机资料整理和筛选过程中的运用;
一方面,更具体的,假设要从一个更大的资料集合中筛选出最小的n个数据,那么只要从资料集合中任意找出n个数据,然后再从这n个数据中找到最大的一个n_，据此就可以准确的进行以下推断：如果存在一个数据大于n_,那么该资料一定不是要选的资料;如果存在一个数据n_1，只要n_1小于n_,那么就又能证明了n_这个资料一定不是要选的,所以就可以安全的用n_1将n_替换掉了;接下来,对调整后的n个数据重新排查,再次找出n个数据中最大的那个,然后重复以上操作,直到将所有符合要求的资料都找出来;
另一方面,设定锚点存放的是每个资料段ｐ的最小的值，ｐ段里面还有ｐ＿段，要筛选出最小的n个数据;那么,就可以先遍历p的锚点,选择出锚点值最小的n个p段,再从这n个p段中出找出锚点值最小的n个p_段;再从这n个p_中找到锚点的值最大的p_1;最后遍历这n个p_资料段的资料,只有满足小于或等于p_1,同时又小于n_的值才有可能是要选取的值，所以可以安全的操作这些资料与n_的资料进行互换; 否则，一定不是，所以可以将它们安全的排除在目标之外;
而从一个更大的资料集合中筛选出最大的n个数据,与此逻辑相同,但取值相反;具体的, 只要从资料集合中任意找出n个数据,然后再从这n个数据中找到最小的一个n_，据此就可以准确的进行以下推断：如果存在一个数据小于n_,那么该资料一定不是我们要选的资料;如果存在一个数据n_1，只要n_1大于n_,那么就又能证明了n_这个资料一定不是我们要选的,所以就可以安全的用n_1将n_替换掉了;接下来,对调整后的n个数据重新排查,再次找出n个数据中最小的那个,然后重复以上操作,直到将所有符合要求的资料都找出来;
另一方面,更进一步,接上例,更具体的,设定锚点存放的是每个资料段ｐ的最大的值，ｐ段里面还有ｐ＿段，要筛选出最大的n个数据;那么,就可以先遍历p的锚点,选择出锚点值最大的n个p段,再从这n个p段中出找出锚点值最大的n个p_段;再从这n个p_中找到锚点的值最小的p_1;最后遍历这n个p_资料段的资料,只有满足大于或等于p_1,同时又大于n_的值才有可能是要选取的值,所以可以安全的操作这些资料与n_的资料进行互换;否则，一定不是,所以可以将它们安全的排除在目标之外；
通过这种方法有效的减少了资料的遍历数量和资料的交换次数；
