算法基础04——堆、拓扑及其它基础排序

堆排序

堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

就是用带排序数据数组构建大顶堆或小顶堆(升序或降速)。堆结构见堆相关。

/**
 * 堆排序
 */
public class HeapSort {

    /**
     * 排序
     * <p>
     * 堆元素是从数组下标0开始
     *
     * @param arr
     */
    public static void sort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }

        // 1、建堆
        buildHeap(arr);

        // 2、排序
        int k = arr.length - 1;
        while (k > 0) {
            // 将堆顶元素(最大)与最后一个元素交换位置
            swap(arr, 0, k);
            // 将剩下元素重新堆化,堆顶元素变成最大元素
            heapify(arr, --k, 0);
        }
    }

    /**
     * 建堆
     *
     * @param arr
     */
    private static void buildHeap(int[] arr) {
        // (arr.length - 1) / 2 为最后一个叶子节点的父节点
        // 也就是最后一个非叶子节点,依次堆化直到根节点
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            heapify(arr, arr.length - 1, i);
        }
    }

    /**
     * 堆化
     *
     * @param arr 要堆化的数组
     * @param n   最后堆元素下标
     * @param i   要堆化的元素下标
     */
    private static void heapify(int[] arr, int n, int i) {
        while (true) {
            // 最大值位置
            int maxPos = i;
            // 与左子节点(i * 2 + 1)比较,获取最大值位置
            if (i * 2 + 1 <= n && arr[i] < arr[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            // 最大值与右子节点(i * 2 + 2)比较,获取最大值位置
            if (i * 2 + 2 <= n && arr[maxPos] < arr[i * 2 + 2]) {
                maxPos = i * 2 + 2;
            }
            // 最大值是当前位置结束循环
            if (maxPos == i) {
                break;
            }
            // 与子节点交换位置
            swap(arr, i, maxPos);
            // 以交换后子节点位置接着往下查找
            i = maxPos;
        }
    }

	private static void swap(int[] arr, int i, int maxPos) {
		int temp = arr[i];
		arr[i] = arr[maxPos];
		arr[maxPos] = temp;
		
	}

}

拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

拓扑排序存在的前提

当且仅当一个有向图为有向无环图(directed acyclic graph,或称DAG)时,才能得到对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。该论断可以利用反证法被证明如下:

假设我们有一由v_1到v_n这n个结点构成的有向图,且图中v_1,v_2,...,v_n这些结点构成一个环。这即是说对于所有1≤i<n-1,图中存在一条有向边从v_i指向v_i+1。同时还存在一条从v_n指向v_1的边。假设该图存在一个拓扑排序。

那么基于这样一个有向图,显然我们可以得知对于所有1≤i<n-1,v_i必须在v_i+1之前被遍历,也就是v_1必须在v_n之前被遍历。同时由于还存在一条从v_n指向v_1的边,v_n必须在v_1之前被遍历。这里出现了与我们的假设所冲突的结果。因此我们可以知道,该图存在拓扑排序的假设不成立。也就是说,对于非有向无环图而言,其拓扑排序不存在。

拓扑排序问题的线性时间解

若有向图中存在n个结点,则我们可以在O(n)时间内得到其拓扑排序,或在O(n)时间内确定该图不是有向无环图,也就是说对应的拓扑排序不存在。

我们可以用改进的深度优先遍历或广度优先遍历算法来完成拓扑排序。以广度优先遍历为例,改进的算法与普通的广度优先遍历唯一的区别在于我们应当保存每一个结点对应的入度,并在遍历的每一层选取入度为0的结点开始遍历(而普通的广度优先遍历则无此限制,可以从该吃呢个任意一个结点开始遍历)。这个算法描述如下:

  1. 初始化一个int[] inDegree保存每一个结点的入度。
  2. 对于图中的每一个结点的子结点,将其子结点的入度加1。
  3. 选取入度为0的结点开始遍历,并将该节点加入输出。
  4. 对于遍历过的每个结点,更新其子结点的入度:将子结点的入度减1。
  5. 重复步骤3,直到遍历完所有的结点。
  6. 如果无法遍历完所有的结点,则意味着当前的图不是有向无环图。不存在拓扑排序。
public class TopologicalSort {
    /**
     * Get topological ordering of the input directed graph 
     * @param n number of nodes in the graph
     * @param adjacencyList adjacency list representation of the input directed graph
     * @return topological ordering of the graph stored in an List<Integer>. 
     */
    public List<Integer> topologicalSort(int n, int[][] adjacencyList) {
        List<Integer> topoRes = new ArrayList<>();
        int[] inDegree = new int[n];
        for (int[] parent : adjacencyList) {
            for (int child : parent) {
                inDegree[child]++;
            }
        }
        
        Deque<Integer> deque = new ArrayDeque<>();
        
        // start from nodes whose indegree are 0
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) deque.offer(i);
        }
        
        while (!deque.isEmpty()) {
            int curr = deque.poll();
            topoRes.add(curr);
            for (int child : adjacencyList[curr]) {
                inDegree[child]--;
                if (inDegree[child] == 0) {
                    deque.offer(child);
                }
            }
        }
    
        return topoRes.size() == n ? topoRes : new ArrayList<>();
    }
}

其他基础排序算法

一. 稳定的排序

鸡尾酒排序(cocktail sort)—O(n²)

计数排序(counting sort)—O(n+k);需要 O(n+k)额外空间

二叉树排序(binary tree sort)— O(nlog n)期望时间;O(n²)最坏时间;需要 O(n)额外空间

鸽巢排序(pigeonhole sort)— O(n+k);需要O(k)额外空间

侏儒排序(gnome sort)—O(n²)

图书馆排序(library sort)— O(nlog n)期望时间;O(n²)最坏时间;需要(1+E)n额外空间

块排序(block sort)—O(nlog n)

二.不稳定的排序

clover排序算法(Clover sort)— O(n)期望时间,O(n²)最坏情况

梳排序 O(nlog n)

平滑排序(smooth sort)— O(nlog n)

内省排序(introsort)—O(nlog n)

耐心排序(patience sort)—O(nlog n+k)最坏情况时间,需要额外的O(n+k)空间,也需要找到最长的递增子序列(longest increasing subsequence)

更新时间:2020-02-15 15:13:57

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/算法基础04堆拓扑及其它基础排序
最后更新:2020-02-15 15:13:57

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×