相对有序排序算法

使用场景：
当需要对一批数据进行逐个筛选，并将筛选后的数据存入一个容器中，当取出来进行第二次操作时，需要取出的数据是按一定的规则排序的时候。
drools加载并执行规则的时候，会去创建执行网络（Rete算法），用的排序方式就是这个算法。

public class RelativeOrderAlgorithm {

    private static Integer[] elements = new Integer[11];
    private static int size = elements.length - 1;

    public static void percolateUpMaxHeap(int index) {
        int hole = index;
        int element;
        int next;
        for (element = elements[index]; hole > 1
                && element - elements[hole / 2] > 0; hole = next) {
            next = hole / 2;
            elements[hole] = elements[next];
        }
        elements[hole] = element;
    }

    public static void percolateDownMaxHeap(int index) {
        int element = elements[index];
        int hole;
        int child;
        for (hole = index; hole * 2 <= size; hole = child) {
            child = hole * 2;
            if (child != size && elements[child + 1] - elements[child] > 0) {
                ++child;
            }
            if (elements[child] - element <= 0) {
                break;
            }
            elements[hole] = elements[child];
        }
        elements[hole] = element;
    }

    public static Integer doRemove(int index) {
        if (index >= 1 && index <= size) {
            int result = elements[index];
            elements[index] = elements[size];
            elements[size] = null;
            --size;
            if (size != 0 && index <= size) {
                int compareToParent = 0;
                if (index > 1) {
                    compareToParent = elements[index] - elements[index / 2];
                }

                if (index > 1 && compareToParent > 0) {
                    percolateUpMaxHeap(index);
                } else {
                    percolateDownMaxHeap(index);
                }
            }
            return result;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 0, 2, 43, 12, 4356, 54, 23, 231, 32, 554, 67 };
        for (int i = 1; i < arr.length; i++) {
            elements[i] = arr[i];
            percolateUpMaxHeap(i);
        }
        for (int i = 1; i < arr.length; i++) {
            System.out.println(doRemove(1));
        }
    }
}

效率比较：
例如，我们要处理的数据量为10，使用快速排序的方式：

int[] arr = { 1,2,3,4,5,6,7,8,9,10 };
for (int i = 0; i < arr.length-1; i++) {
    for (int j = i+1; j < arr.length; j++) {
        if(arr[i]<arr[j]){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        count++;
    }
}

我们发现最坏的这种情况需要循环45次，而是用相对有序排序算法只要需要29次，而且，相对有序的算法的优势不仅如此，传统的排序不管是什么情况都需要循环那么多次，而相对有序的算法在是乐观的，很多时候循环的次数是不需要29次的，例如数据本来就是有序的，那么只需要循环12次，而传统排序还是45次。