首页 > 编程语言 > 详细

算法基础二:渐增型算法---序列的划分

时间:2021-09-21 07:53:27      阅读:6      评论:0      收藏:0      [点我收藏+]

算法基础二:渐增型算法---序列的划分

一、算法的描述与分析

技术分享图片

技术分享图片

二、算法的伪代码描述

技术分享图片

三、代码实现

1、算法代码

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class LinearList {

    public static int partition(List<Comparable> a, int p, int r, Comparator comp){

        Comparable x;
        int i,j;
        x = a.get(r);
        i = p-1;

        for (j=p;j<r;j++){
            if (comp.compare(a.get(j),x)<=0){//a[i]<=x
                i++;
                Collections.swap(a,i,j);
            }
        }

        Collections.swap(a,i+1,r);

        return i+1;
    }

}

对应的Comparator

Greater

import java.util.Comparator;

public class Greater implements Comparator<Comparable> {
    public int compare(Comparable x, Comparable y){
        return x.compareTo(y);
    }
}

Less

import java.util.Comparator;

public class Less implements Comparator<Comparable> {
    @Override
    public int compare(Comparable o1, Comparable o2) {
        return o2.compareTo(o1);
    }
}

2、测试代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

public class Test {

    public static void main(String[] args) {
        Integer a[] = {1,2,5,8,9,0,3,4,6,7},i,j;
        String b[] = {"AoMen","BeiJing","ChongQing","TianJin","XiangGang","ShangHai"};
        Double c[] = {0.5,3.7,6.3,8.5,9.2,1.7,2.3,4.1,5.9,7.4};

        ArrayList<Integer> A = new ArrayList<>();
        for (Integer integer : a) {
            A.add(integer);
        }

        Vector<String> B = new Vector<>();
        for (String s : b) {
            B.add(s);
        }

        LinkedList<Double> C = new LinkedList<>();
        for (Double aDouble : c) {
            C.add(aDouble);
        }

        j = LinearList.partition((List)A,0,9,new Greater());
        System.out.println(A);
        System.out.println(j);

        j = LinearList.partition((List)B,0,5,new Less());
        System.out.println(B);
        System.out.println(j);

        j = LinearList.partition((List)C,0,9,new Greater());
        System.out.println(C);
        System.out.println(j);
    }

}

算法基础二:渐增型算法---序列的划分

原文:https://www.cnblogs.com/darkerg/p/15311054.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!