相对有序排序算法

╰+攻爆jí腚メ 2022-06-06 12:08 30阅读 0赞

**使用场景：**  
当需要对一批数据进行逐个筛选，并将筛选后的数据存入一个容器中，当取出来进行第二次操作时，需要取出的数据是按一定的规则排序的时候。  
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次。