几乎有序数组的排序方法

题目描述

已知一个几乎有序的数组，几乎有序指的是，如果把数组排好序的话，每个元素移送的距离不超过k，也就是说，所有元素都与它最终排序后的位置相距不到k，请选择一个时间复杂度最低的排序算法对此问题排序。

思路分析

排序算法，常见的效率比较高的，快排，不过，对于基本有序的数据，快排效率反而很低，排除掉。对于冒泡排序，有哨兵一说，如何已经有序，能直接返回，但是，此题只是在附近k的位置内，并不是说已经有部分有序，因此，也不符合。
因此，分析此题的特殊情况，每个数都在其最终位置k步以内，也就是说，最小值的话，最终排序后的位置肯定是第一个数，然后，它此时的位置，肯定在前k+1个数中，对吧？那么，前k+1个数中的最小值，是不是就是整个数组的最小值呢？然后，确定了最小值，那倒数第二小的值，是不是也是在它后面k+1个位置能确定呢？同理，我们也可以从后往前找k+1个区间内的最大值，就是整个数组的最大值。
相当于，题目说每个数的最终位置相距不超过k，那么，我们可以从头往后找k+1个位置内的最小值，就是整个数组的最小值，然后，依次往后维护一个k+1大小的范围，在里面依次找的最值，就是整个数组的最值。
想到了维护一个范围，并且范围内要每次都求出最值，想到了什么排序算法？什么数据结构？没错，就是堆嘛，大小根堆的维护最大最小值比较容易。

代码实现

    public static void process(int[] arr,int k){
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        int index=0;
        //把前k+1个放入小根堆
        for (; index <= k; index++) {
            queue.add(arr[index]);
        }
        int i=0;
        //依次向后维护k+1的区间
        for (; index<arr.length; i++) {
            arr[i]=queue.poll();
            queue.add(arr[++index]);
        }
        //将最后部分放入
        for (; i < arr.length; i++) {
            arr[i]=queue.poll();
        }
    }

最后

以上就是默默小兔子为你收集整理的几乎有序数组的排序方法的全部内容，希望文章能够帮你解决几乎有序数组的排序方法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。