病理分选

Question

病理分类

您的老板要求您开发一个排序算法，以提高您公司的应用程序的性能。然而，在编写了应用程序之后，您知道不太可能使它变得更快。不想让你的老板失望，你已经决定开发一种新的算法，比对某些数据集进行排序更有效。当然，您不能明显地表明该算法只适用于某些情况，因此您希望尽可能地使其模糊不清。

这个竞赛的目的是用你所选择的语言写一个排序例程，它在某些数据集上表现得比其他数据更好，结果是可重复的。决定速度的分类越具体，越好。该算法必须进行某种排序，因此依赖于已被完全排序的数据的算法(例如，不做任何操作的算法)或依赖于完全反向排序的数据的算法都是无效的。排序算法必须正确排序任何数据集。

在介绍您的例程之后，请说明为什么它只在某些数据集上工作，并包括至少一组好(快速)数据和一组坏(慢)数据的测试运行。这里的要点是能够向你的老板证明你偶然发现了一种更好的分类方法，所以更多的测试数据更好。当然，您只会向老板展示好数据的测试结果，因此所需测试数据中的缺陷不会太明显。如果适用于您的语言，请显示您的算法比您的语言内置排序算法更快。

例如，可以提交插入排序算法，好的数据是已经接近排序的数据，而坏的数据是完全随机的数据，因为插入排序接近O(n)对几乎排序的数据。然而，这并不是很好，因为我的老板可能会注意到，所有的测试数据几乎都是从一开始就排序的。

这是一个人气-竞赛，所以7天后(5月21日)投票最多的答案获胜。

如果没有人比我强，我想提交一个利用均匀分布的数据集的社区wiki答案。

Answer 1

这是很长一段时间了，但我记得在算法101中，我们学到了一些使用随机化的排序算法。我不是一个很好的学生，所以我不记得它是怎么进行的，也不记得为什么它平均运行得很快。

尽管如此，我还是认为这个问题需要一个使用随机化的解决方案，希望这对我有利。

import random

def arrayIsSorted (arr) :
    for i in range(len(arr)-1) :
        if arr[i]>arr[i+1] : return False
    return True

def rSort (arr) :
    random.seed (42)
    counter = 0
    while not arrayIsSorted(arr) :
        random.shuffle (arr)
        counter+=1
    print ("Sorted in %d iterations." % counter)
    return arr

因为真正的随机化是很重要的，所以我确保给RNG播下生命、宇宙和一切的答案。经过一些测试，结果证明这是一个聪明的举动！查看这两个完全任意的列表排序的速度：

rSort ([6,1,4,2,3,7,5])
rSort ([8,9,6,1,4,7,2,3,5])

这两种方法只在一个迭代中得到排序--您不可能要求一个比这更快的函数！

现在，无可否认，其他一些名单产生了稍微更糟的结果..。

rSort ([5,1,4,2,3,7,6])
rSort ([8,9,6,1,4,7,2,5,3])

它们分别在4,176和94,523个迭代中进行排序，这实际上需要超过一秒钟的时间.但是，让我们把这个事实告诉我们自己，以免分散任何人对这个算法多么神奇的注意力！

编辑：

我被要求在一个100项列表中证明我的算法的效率，所以你可以这样做：

rSort ([70, 6, 52, 97, 85, 61, 62, 48, 30, 3, 11, 88, 39, 91, 98, 8, 54, 92, 44, 65, 69, 21, 58, 41, 60, 76, 27, 82, 93, 81, 20, 94, 22, 29, 49, 95, 40, 19, 55, 42, 43, 1, 0, 67, 35, 15, 51, 31, 16, 25, 5, 53, 37, 74, 86, 12, 13, 72, 56, 32, 47, 46, 59, 33, 80, 4, 45, 63, 57, 89, 7, 77, 14, 10, 34, 87, 18, 79, 9, 66, 24, 99, 64, 26, 78, 38, 90, 28, 83, 75, 68, 2, 17, 73, 96, 71, 23, 84, 36, 50])

即使这个长而又完全任意的列表也会立即被排序！真的，我一定是偶然发现了世界上最好的排序算法！

Answer 2

如果您可以创建您自己的数据，那么它是非常简单的-获取数据看起来是随机的，但包括一个键，以加快排序。所有其他数据都使用原始排序方法，因此平均次数更好。

一种简单的方法是确保每个数据项都有一个唯一的键，然后只对键进行散列。例如，一个列表，其数字为1-10,000，全部乘以16，并添加了0-15的随机数(请参见下面的fillArray() )。它们看起来是随机的，但是每一个都有一个唯一的顺序键。对于排序，除以16 (在C中，>>4非常快)，然后使用结果键作为索引将数字放入数组中。一关就完蛋了。在测试中，我发现快速排序比1000万个数字慢30倍。

void fillArray(int *a,int len)
{
  for (int i=0;i<len;++i)
    a[i]=(i<<4)|(rand()&0xF);
  // shuffle later
}
void sortArray(int *a,int len)
{
  int key=0;
  int *r=new int[len];
  for (int i=0;i<len;++i)
  {
    key=a[i]>>4;
    r[key]=a[i];
  }
  memcpy(a,r,len*sizeof(int));
  delete[] r;
}
void shuffleArray(int *a,int len)
{
  int swap=0, k=0;
  for (int i=0;i<len;++i)
  {
    k=rand()%len;
    swap=a[k];
    a[k]=a[i];
    a[i]=swap;
  }
}
int qCompare(const void*a,const void*b)
{
  int result=*((int*)a)-*((int*)b);
  return result;
}
void main()
{
  int aLen=10000;
  int *a=new int[aLen];
  srand (time(NULL));
  fillArray(a,aLen);
  // time them
  long t0=0, d0=0, d1=0;
  // qsort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  qsort(a,aLen,sizeof(int),&qCompare);
  d0=::GetTickCount()-t0;
  // oursort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  sortArray(a,aLen);
  d1=::GetTickCount()-t0;
  delete[] a;
}

任何有唯一键的东西都可以这样排序--当然，如果你有存储它的内存的话。例如，许多数据库使用唯一的数字客户id --如果列表很小/顺序足够大，则可以将其保存在内存中。或者用其他方法把一个记录转换成一个唯一的数字。想了解更多信息，研究哈希排序，因为这就是.