Java教程
插入、归并、快速算法的比较以及拓扑排序的循环检测
本文主要是介绍插入、归并、快速算法的比较以及拓扑排序的循环检测，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
问题描述
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
分别使用插入排序和快速排序以及快速排序结合插入排序解决此问题
使用插入排序
//本人对于小数组的处理倾向于插入排序
class Solution {
private int[] res;
public int[] getLeastNumbers(int[] arr, int k) {
res = new int[k];
for(int i = 1; i < arr.length ; i++){
for(int j = i ; j > 0 && less(arr[j],arr[j-1]);j--){
exchange(arr,j,j-1);
}
}
for(int i = 0; i < k ; i++){
res[i] = arr[i];
}
return res;
}
private boolean less(int v,int w){
return v < w;
}
private void exchange(int[] a,int v,int w){
int t = a[v];
a[v] = a[w];
a[w] = t;
}
}
使用快速排序
//本人对于小数组的处理倾向于插入排序
//对于不重复主键的大数组，本人推荐使用快速排序加插入排序实现
//对于重复主键数组，本人推荐使用三切分的快速排序
class Solution {
private int[] res;
public int[] getLeastNumbers(int[] arr, int k) {
quickSort(arr,0,arr.length-1);
res = new int[k];
for(int i = 0; i < k ; i++){
res[i] = arr[i];
}
return res;
}
private void quickSort(int[] a,int lo,int hi){
if(hi <= lo) return;
int j = slice(a,lo,hi);
quickSort(a,lo,j-1);
quickSort(a,j+1,hi);
}
private int slice(int[] a,int lo,int hi){
int i = lo,j = hi + 1;
int v = a[lo];
while(true){
while(less(a[++i],v)) if(i == hi) break;
while(less(v,a[--j])) if(j == lo) break;
if(i >= j) break;
exchange(a,i,j);
}
exchange(a,lo,j);
return j;
}
private boolean less(int v,int w){
return v < w;
}
private void exchange(int[] a,int v,int w){
int t = a[v];
a[v] = a[w];
a[w] = t;
}
}
快速排序结合插入排序对小数组以及部分有序数组处理快的优点
与快速排序不同的地方在于,多了一个insertSort方法:
private void insertSort(int[] a,int lo,int hi){
for(int i = lo + 1; i <= hi ; i++){
for(int j = i ; j > lo && less(a[j],a[j-1]) ; j--){
exchange(a,j,j-1);
}
}
}
以及quickSort内部变成了:
private void quickSort(int[] a,int lo,int hi){
if(hi <= lo + 5){
insertSort(a,lo,hi);
return;
}
int j = slice(a,lo,hi);
quickSort(a,lo,j-1);
quickSort(a,j+1,hi);
}
运行完上述的三个实现，会发现插入排序用时是最多的，这是因为插入排序在最坏情况下为N^2/2, 一般情况下为N^2/4, 插入排序在部分有序，部分倒置，小数组的情况下处理处理速度是最快的。
快速排序在此问题要比插入排序快了20倍有余，快速排序的处理速度是NlogN,排序算法的下限便是NlogN，归并排序也达到了此点，但是快速排序好的地方便是快速排序所用的空间少，交换数组元素的次数也比归并排序扫了很多。
第三个算法便是结合了快速排序优点和插入排序对小数组处理快的优点，比原始的快速排序要优化了20%~30%。
问题描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
使用有向图的拓扑排序解决此问题
import java.util.NoSuchElementException;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
DiGraph digraph = new DiGraph(prerequisites,numCourses);
DirectedCycle topology = new DirectedCycle(digraph);
return !topology.hasCycle();
}
}
/**
* <h2>背包</h2>
* <p>博客地址:https://home.cnblogs.com/u/qzlzzz/</p>
* @since 2021/11/13
* @author qzlzzz
* @version 2.0
* @param <Item> {@code type parameter}
*/
class Bag<Item> implements Iterable<Item> {
//the first value in this bag
private Node<Item> first;
// all value in this bag
private int n;
private class Node<Item>{
//value
private Item item;
//next index
private Node<Item> next;
}
public Bag(){
this.first = null;
this.n = 0;
}
/**
* <h3>判断背包是否为空</h3>
* @return {@code true} else {@code false}
*/
public boolean isEmpty(){
return first == null;
}
/**
* <h3>向背包加入元素</h3>
* @param item {@code the value}
*/
public void add(Item item){
Node<Item> oldFirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldFirst;
}
/**
* <h3>迭代器</h3>
* @return
*/
@Override
public Iterator<Item> iterator() {
return new LinkedIterator(first);
}
private class LinkedIterator implements Iterator<Item> {
private Node<Item> current;
public LinkedIterator(Node first){
this.current = first;
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
if(!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}
class DiGraph{
private int V;
private int E;
private Bag<Integer>[] bags;
public DiGraph(int V){
this.V = V;
this.E = 0;
bags = new Bag[V];
for(int i = 0 ; i < V ; i++){
bags[i] = new Bag<Integer>();
}
}
public DiGraph(int[][] in,int V){
this(V);
int E = in.length;
for(int i = 0; i < E ; i++){
int v = in[i][0];
int w = in[i][1];
addEdg(v,w);
}
}
private void addEdg(int v,int w){
bags[v].add(w);
this.E++;
}
public Iterable<Integer> adj(int v){
return bags[v];
}
public int V(){
return this.V;
}
public int E(){
return this.E;
}
}
class DirectedCycle{
private int[] edgeTo;//记录路径
private boolean[] marked;//标记已访问过的点
private boolean[] onStack;
private Stack<Integer> cycle;//保留循环
public DirectedCycle(DiGraph digraph){
marked = new boolean[digraph.V()];
onStack = new boolean[digraph.V()];
edgeTo = new int[digraph.V()];
for(int v = 0 ; v < digraph.V(); v++){
if(!marked[v]){
dfs(digraph,v);
}
}
}
private void dfs(DiGraph digraph,int v){
marked[v] = true;
onStack[v] = true;
for(int w : digraph.adj(v)){
if(hasCycle()) return;
if(!marked[w]){
edgeTo[w] = v;
dfs(digraph,w);
}else if(onStack[w]){
cycle = new Stack<Integer>();
for(int t = v; t != w ; t = edgeTo[t]){
cycle.push(t);
}
cycle.push(w);
cycle.push(v);
}
}
onStack[v] = false;
}
public boolean hasCycle(){
return cycle != null;
}
}
参考
https://algs4.cs.princeton.edu/home/
这篇关于插入、归并、快速算法的比较以及拓扑排序的循环检测的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
RocketMQ底层原理资料详解：新手入门教程11-29
-
RocketMQ源码资料解析与入门教程11-29
-
[开源]6.1K star！这款电视直播源神器真的太赞啦！11-29
-
HTTP压缩入门教程：轻松提升网页加载速度11-29
-
JWT开发入门指南11-29
-
知识管理革命：文档软件的新玩法了解一下！11-28
-
低代码应用课程：新手入门全攻略11-28
-
哪些办公软件适合团队协作，且能够清晰记录每个阶段的工作进展？11-28
-
全栈低代码开发课程：零基础入门到初级实战11-28
-
拖动排序课程：轻松掌握课程拖动排序功能11-28
-
如何高效管理数字化转型项目11-28
-
SMART法则好用吗？有哪些项目管理工具辅助实现？11-28
-
深度剖析：6 款办公软件如何构建设计团队项目可视化管理新生态？11-28
-
HTTP缓存课程：新手入门指南11-28
-
实战丨证券 HTAP 混合业务场景的难点问题应对11-28
栏目导航
