We use a uniform grid with the cell size being as large as our largest object in the scene, then we only need to check each cell and its surrounding neighbours for possible collisions, and not loop through all objects and check all of them.
It does have a lot of overhead of keeping track of all the objects in the scene, but by balancing the choice of cell size, and the number of objects in the scene, we can usually get a few times faster than the naive O(n2) algorithm.
This app is comparing the performance of the trivial method against the grid based method.
If 2 balls collide we color them red, if not, they're black. This method can be used for collision detection and for a fast neighbour lookup.
We use this to create the node-garden effect.
Can be found on my GitHub.
The grid algorithm and basic idea is presented in AdvancED ActionScript Animation by Keith Peters.