JavaScript QuickSort对象

Question

假设我有以下Javascript结构：

[
  {
    "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
    "path": "/Users/justin/test/node-w.tar.gz"
  },
  {
    "hash": "b1adffc1988b7339c7d4c59310fb3a64ce89e776a4924d492e819a08a7dce3fd",
    "path": "/Users/justin/test/level-1/level-1-1/music.mp3"
  },
  {
    "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
    "path": "/Users/justin/test/level-1/level-1-1/node-z.tar.gz"
  },
  {
    "hash": "2e456c8de66a4ab6cf929d52bd6928b2d0096a8116891ade3dde9588c5f6b3c2",
    "path": "/Users/justin/test/logo_large.psd"
  },
  {
    "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
    "path": "/Users/justin/test/level-1/node-y.tar.gz"
  },
  {
    "hash": "fce57d4407e847c4c13cb2867d3f00f2aed4b5c569385d04765abe2fcae726bb",
    "path": "/Users/justin/test/level-1/install.dmg"
  }
]

这只是一个基本的例子，在现实中，它将是数千个，甚至数万个物体的长度。我想对hash上的重复项进行分组，所以基本上是按散列排序，所以排序速度最快。结果应该如下所示：

[
  {
    "hash": "2e456c8de66a4ab6cf929d52bd6928b2d0096a8116891ade3dde9588c5f6b3c2",
    "path": "/Users/justin/test/logo_large.psd"
  },
  {
    "hash": "b1adffc1988b7339c7d4c59310fb3a64ce89e776a4924d492e819a08a7dce3fd",
    "path": "/Users/justin/test/level-1/level-1-1/music.mp3"
  },
  {
    "hash": "fce57d4407e847c4c13cb2867d3f00f2aed4b5c569385d04765abe2fcae726bb",
    "path": "/Users/justin/test/level-1/install.dmg"
  }, 
  {
     "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
     "path": "/Users/justin/test/node-w.tar.gz"
   },
   {
     "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
     "path": "/Users/justin/test/level-1/level-1-1/node-z.tar.gz"
   },
   {
     "hash": "fe5642d26d04cc7e7d47daa426da2a79e244bdcbae1594a12578f0d6fe03082e",
     "path": "/Users/justin/test/level-1/node-y.tar.gz"
   }
 ]

Answer 1

标准的Javascript Array.sort()非常快：

myArray.sort(function(a,b) { 
    return a.hash == b.hash ? 0 : 
        a.hash > b.hash ? 1 : -1; 
});

编辑:正如@Aaron注意到的那样，使用.localeCompare会更清晰

myArray.sort(function(a,b) { 
    return a.hash.localeCompare(b.hash);
});

但是，如果您只是想通过重复的散列进行查找或分组，则可能需要在散列的关键字对象中进行收集：

var hashes = {},
    groups = [],
    i, hash;
for (i=0; i < myArray.length; i++) {
    hash = myArray[i].hash;
    if (hash in hashes) {
        hashes[hash].push(myArray[i]);
    } else {
        hashes[hash] = [myArray[i]];
    }
}
// now turn into an array
for (hash in hashes) {
    if (hashes.hasOwnProperty(hash)) {
        groups.push(hashes[hash]);
    }
}

groups数组现在将有一系列长度为1到n的数组，每个数组包含具有特定散列的所有对象。