Java Arrays和Collections库中常用的算法使用指南

x33g5p2x  于2个月前 转载在 Java  
字(10.9k)|赞(0)|评价(0)|浏览(87)

在本指南中,我们将学习ArraysCollections等Java内置类中使用的算法。
让我们讨论一下最常用的Java内置实用程序类Arrays```和Collections`的用法。
这里描述的多态算法是Java平台提供的可重用功能。它们都来自ArraysCollections类,并且都采用静态方法的形式,其第一个参数是要执行操作的数组或集合。
Java平台提供的绝大多数算法都是在List示例上操作的,但也有少数算法是在任意Collection示例上操作的。
我想介绍一下以下算法:

  • Sorting
  • Shuffling
  • Routine Data Manipulation
  • Searching
  • Composition
  • Finding Extreme Values

Arrays实用程序类

Java提供了一个Arrays实用类,它对数组元素的升序和降序排序非常有帮助。这个类还包含了一个静态工厂方法,允许将数组作为列表来查看。
JDK提供的这个实用程序类包含各种用于操作数组的方法(如排序和搜索)。
你可以参考这个链接来了解更多的数组实用程序类的API。
https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html
演示Arrays实用程序类的完整示例

import java.util.Arrays;
import java.util.Date;
import java.util.List;

public class AlgorithmsDemo {
    public static void main(String[] args) {
       sortArrayOfPrimitives();
       sortArrayOfString();
       convertArrayToList();
       binarySerachAlgorithm();
 }

 private static void binarySerachAlgorithm() {
     final String key = "abc";
     String[] strArray = { "abc", "cdf", "pqr" };
     Arrays.binarySearch(strArray, key);
     int[] intArray = { 1, 2, 3, 4 };
     Arrays.binarySearch(intArray, 3);

     byte k = 1;
     byte[] byteArray = { 1, 2, 3, 4, 5 };
     Arrays.binarySearch(byteArray, k);

     char charKey = 'a';
     char[] charArray = { 'a', 'b', 'c' };
     Arrays.binarySearch(charArray, charKey);

     double[] doubleArray = { 0.1, 0.2, 0.3 };
     Arrays.binarySearch(doubleArray, 0.2);

     long[] longArray = { 1, 2, 3, 4, 5 };
     Arrays.binarySearch(longArray, 1);

     float[] floatArray = { 1, 2, 3, 4, 5 };
     Arrays.binarySearch(floatArray, 2);
 }

 // Convert array to list
 private static void convertArrayToList() {
     List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
     for (String str : stooges) {
         System.out.println(" print list ----" + str);
     }
 }

 // Sort array of primitive elements
 private static void sortArrayOfPrimitives() {
     int[] intArray = { 1, 2, 3, 4 };
     Arrays.sort(intArray);

     byte[] byteArray = { 1, 2, 3, 4, 5 };
     Arrays.sort(byteArray);

     char[] charArray = { 'a', 'b', 'c' };
     Arrays.sort(byteArray);

     double[] doubleArray = { 0.1, 0.2, 0.3 };
     Arrays.sort(doubleArray);

     long[] longArray = { 1, 2, 3, 4, 5 };
     Arrays.sort(longArray);

     float[] floatArray = { 1, 2, 3, 4, 5 };
     Arrays.sort(floatArray);
 }

 // Sort array of string elements
 private static void sortArrayOfString() {
    // String internally implements Comparable interface.
     String[] strArray = { "abc", "cdf", "pqr" };
     Arrays.sort(strArray);
     // Date internally implements Comparable interface
     Date[] dates = { new Date("08-26-2016"), new Date("08-27-2016") };
  }
}

集合实用程序类

关于集合实用工具类的要点。

  • 此类是Java集合框架的成员。
  • 列表中的所有元素都必须实现**Comparable**接口,而且列表中的所有元素必须相互比较(即e1.compareTo(e2)不能对列表中的任何元素e1和e2抛出ClassCastException)。
  • 这种排序保证是稳定的:相等的元素将不会作为排序的结果而被重新排序。
  • 指定的列表必须是可修改的,但不必是可调整大小的。
  • 它包含对集合进行操作的多态算法、" Package 器"(返回由指定集合支持的新集合)以及其他一些零碎的东西。
  • 我们可以使用-Collections. sort(projects,Collections. reverseOrder())对元素进行降序排序;

您可以参考此链接以了解集合实用程序类的更多API。https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html
演示Collections实用工具类的完整示例
示例:根据指定列表元素的自然顺序,按升序对列表进行排序。

import java.util.Collections;
import java.util.LinkedList;

public class CollectionsDemo {

 public static void main(String[] args) {
     listSortingAlgorithmsDemo();
 }

 private static void listSortingAlgorithmsDemo() {
     LinkedList<String> list = new LinkedList<>();
     list.add("element 2");
     list.add("element 1");
     list.add("element 4");
     list.add("element 3");
     // Sorts the specified list into ascending order, according to
     // the natural ordering of its elements.
     Collections.sort(list);
     for (String str : list) {
       System.out.println(" sort elements in ascending order  --" + str);
     }
   }
}

按升序和降序对自定义对象列表进行排序
Java提供了两个接口来使用类的数据成员对对象进行排序:

Java Comparable接口用于对自定义类的对象进行排序,该接口位于java. lang包中,只包含一个名为compareTo(provides)的方法,它只提供单一排序序列,即只能基于单个数据成员对元素进行排序。public int compareTo(Object obj):用于比较当前对象和指定对象。我们可以对以下项的元素进行排序:

  • 字符串对象
  • Package 类对象
  • 用户定义的类对象

Java Comparator接口用于对用户定义类的对象进行排序。Collections类提供静态方法对集合的元素进行排序。Collections类的方法对List元素进行排序public void sort(List list,Comparator c):用于根据给定的比较器对List的元素进行排序。例如:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.concurrent.CopyOnWriteArrayList;

public class AlgorithmsDemo {
    public static void main(String[] args) {
     // sortingCustomObjectsByComparable();
     sortingCustomObjectsByComparator();
 }

 private static void sortingCustomObjectsByComparable() {
  // Sort Projects by project id in ascending order.
     List projects = new ArrayList<>();
     Project project = new Project();
     project.setProjectId(100);
     project.setProjectName("project 100");
     projects.add(project);

     Project project2 = new Project();
     project2.setProjectId(200);
     project2.setProjectName("project 200");
     projects.add(project2);

     Project project3 = new Project();
     project3.setProjectId(50);
     project3.setProjectName("project 50");
     projects.add(project3);
     Collections.sort(projects);
     printList(projects);
 }

 private static void sortingCustomObjectsByComparator()           
                 // Sort Projects by project id in ascending order.                 
                 List projects = new ArrayList<>();
                 Project project = new Project();
                 project.setProjectId(100);
                 project.setProjectName("project 100");
                 projects.add(project);
                 
                 Project project2 = new Project();
                 project2.setProjectId(200);
                 project2.setProjectName("project 200");
                 projects.add(project2);
                 Project project3 = new Project();
                 project3.setProjectId(50);
                 project3.setProjectName("project 50");
                 projects.add(project3);
                 
                 // Sorting project by project id in ascending order in Java
                 Collections.sort(projects);
                 printList(projects);
                 
                 // Sorting project by project id in descending order in Java
        Collections.sort(projects, Collections.reverseOrder());
        printList(projects);

        
     // Sorting project by project name in ascending order in Java
          Comparator comparator = new Comparator() {
               @Override
               public int compare(Project o1, Project o2) {
                   // TODO Auto-generated method stub
                   return o1.getProjectName().compareTo(o2.getProjectName());
               }
          };
           Collections.sort(projects, comparator);
           printList(projects);                 
         }

 private static void printList(List projects) {
  for (Project project : projects) {
   System.out.println(project.getProjectId());
   System.out.println(project.getProjectName());
  }
 }

}

class Project implements Comparable {
    private int projectId;
    private String projectName;

 public int getProjectId() {
    return projectId;
 }

 public void setProjectId(int projectId) {
    this.projectId = projectId;
 }

 public String getProjectName() {
    return projectName;
 }

 public void setProjectName(String projectName) {
     this.projectName = projectName;
 }

   @Override
   public int compareTo(Project o) {
    // TODO Auto-generated method stub
    return this.projectId - o.getProjectId();
  }
}

shuffle

  • shuffle 算法的作用与sort相反,它破坏了列表中可能存在的任何顺序痕迹。也就是说,该算法根据随机性来源的输入对列表重新排序,以便在假设随机性来源合理的情况下,所有可能的排列都以相等的可能性发生。

Collections实用程序类提供了shuffling方法示例:

private static void shuffleAlgorithmsDemo() {
  List list = new LinkedList<>();
  list.add("element 2");
  list.add("element 1");
  list.add("element 4");
  list.add("element 3");

  Collections.sort(list);
  for (String str : list) {
   System.out.println(" sort elements in ascending order  --" + str);
  }

  // randomly permutes the elements in a List.
  Collections.shuffle(list);
  printMessage(list, "shuffle elements ");
 }

常规数据操作

Collections类提供了五种算法,用于对List对象执行常规数据操作,所有这些算法都非常简单:

  • reverse-反转List中元素的顺序。
  • fill-用指定的值覆盖List中的每个元素。这个操作对于重新初始化List很有用。
  • copy-接受两个参数,一个目标List和一个源List,并将源的元素复制到目标,覆盖其内容。目标List必须至少与源一样长。如果目标List更长,则目标List中的其余元素不受影响。
  • swap-交换List中指定位置的元素。
  • addAll-将所有指定的元素添加到集合中。要添加的元素可以单独指定,也可以指定为数组。

示例:

private static void listAlgorithmsDemo(){      
         List list = new LinkedList<>();
         list.add("element 2");
         list.add("element 1");
         list.add("element 4");
         list.add("element 3");
                  // Sorts the specified list into ascending order, according to 
         //the natural ordering of its elements.
         // All elements in the list must implement the Comparable interface.
         // Furthermore, 
         //all elements in the list must be mutually 
         //comparable (that is, e1.compareTo(e2) 
         //must not throw a ClassCastException for any elements e1 and e2 in the list). 
         Collections.sort(list);
         for(String str : list){
                 System.out.println(" sort elements in ascending order  --" + str);
         }
         //reverses the order of the elements in a List.
         Collections.reverse(list);
         printMessage(list, "reverse  elements ");
         
         // rotates all the elements in a List by a specified distance.
         Collections.rotate(list, 1);
         printMessage(list, "rotate elements ");
         
         //swaps the elements at specified positions in a List.
         Collections.swap(list, 0, 1);
         printMessage(list, "swap elements ");
         
         //replaces all occurrences of one specified value with another.
         Collections.replaceAll(list, "element 3", "element 6");
         printMessage(list, "replaces all occurrences of one 
specified value with another "
                        specified value with another "
specified value with another ");
         
         List destList = new ArrayList<>();
         Collections.copy(destList, list);
         printMessage(destList, " copied elemets ");
}

private static void printMessage(List list, String message){
         for(String str : list){
                 System.out.println(message + " ---> " + str);       
         }
}

搜索

binarySearch算法在排序的List中搜索指定的元素。此算法有两种形式。第一种形式采用List和要搜索的元素("搜索关键字")。这种形式假设List根据其元素的自然顺序以升序排序。第二种形式除了List和搜索关键字之外还采用比较器,并假设List根据指定的Comparator按升序排序。排序算法可用于在调用binarySearch之前对List进行排序。

示例:

private static void searchingAlgorithmsDemo(){
         List list = new LinkedList<>();
         list.add("element 2");
         list.add("element 1");
         list.add("element 4");
         list.add("element 3");
         // Sorts the specified list into ascending order, according to the 
         // natural ordering of its elements.
         // All elements in the list must implement the Comparable interface.
         // Furthermore, 
         //all elements in the list must be mutually 
         //comparable (that is, e1.compareTo(e2) 
         //must not throw a ClassCastException for any elements e1 and e2 in the list). 
         Collections.sort(list);
         for(String str : list){
         System.out.println(" sort elements in ascending order  --" + str);
         }         
        // searches for an element in an ordered List using the binary search algorithm.
         Collections.binarySearch(list, "element 4"); 
}

Composition

  • frequencydisjoint算法测试一个或多个"集合"组成的某些方面:
  • frequency-计算指定元素在指定集合中出现的次数。
  • disjoint-确定两个集合是否不相交;即它们是否不包含共同的元素。

示例:

private static void compositionAlgorithmDemo(){
         List list = new LinkedList<>();
         list.add("element 2");
         list.add("element 1");
         list.add("element 1");
         list.add("element 3");
      //Returns the number of elements in the specified collection         
       //equal to the specified object.
         System.out.println(Collections.frequency(list, "element 1"));
         List list2 = new LinkedList<>();
         list2.add("element 2");
         list2.add("element 1");
         list2.add("element 1");
         list2.add("element 3");
         //Returns true if the two specified collections have no elements in common. 
         System.out.println(Collections.disjoint(list, list2));
}

寻找极值

minmax算法分别返回指定集合中包含的最小和最大元素。2这两种操作都有两种形式。3简单形式只接受一个集合,返回最小值(或最大值)元素。第二种形式除了Collection之外还接受Comparator,并返回最小值根据指定的Comparator返回(或最大)元素。

示例:

private static void findingExtremeValuesAlgorithm(){
         List list = new LinkedList();
         list.add(100);
         list.add(300);
         list.add(200);
         list.add(500);
         // Returns the minimum element of the given collection, 
         // according to the natural ordering of its elements.
         // All elements in the collection must implement the Comparable interface.
         System.out.println(Collections.min(list));
         //Returns the maximum element of the given collection,
         // according to the natural ordering of its elements. 
         //All elements in the collection must implement the Comparable interface. 
         System.out.println(Collections.max(list));
}

相关文章

微信公众号

最新文章

更多