算法-堆排序扩展排序几乎有序数组

2022-4-1 diaba 算法 

package com.jiucaiyuan.net.algrithm.sort;

import java.util.PriorityQueue;

/**
 * <pre>
 * 堆排序扩展
 *   一个几乎有序的数组，
 *   几乎有序是指，如果把数组排好顺序的话，
 *   每个元素移动的距离可以不超过k，这个k相对于数组来说比较小，
 *   请选择合适的排序算法针对这个数组进行排序
 *
 * 	 时间复杂度O(N*logk)  空间复杂度O(k)
 *
 * </pre>
 * Created by jiucaiyuan on 2022/3/31.
 */
public class HeapSortExtension {
    /**
     * 堆排序算法
     *
     * @param arr
     * @return
     */
    public static void sortedArrDistanceLessK(int[] arr, int k) {
        //默认是小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        //把k个数放入小根堆
        int index = 0;
        for (; index <= Math.min(arr.length, k); index++) {
            heap.add(arr[index]);
        }
        //把数组剩下的数逐个放入小根堆，并逐个弹出小根堆头结点
        int i = 0;
        for (; index < arr.length; i++, index++) {
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }
        //如果堆不为空，全部弹出
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 5, 3, 7, 3, 8, 4, 3, 2, 2, 6, 8, 6, 0, 9, 5, 3};
        print(arr);
        sortedArrDistanceLessK(arr, 3);
        print(arr);
    }

    private static void print(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int a : arr) {
            System.out.print(a + "\t");
        }
        System.out.println();
    }
}

« 算法-基数排序 | 算法-堆排序»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022