在本指南中，我们将学习Arrays和Collections等Java内置类中使用的算法。
让我们讨论一下最常用的Java内置实用程序类Arrays```和Collections`的用法。
这里描述的多态算法是Java平台提供的可重用功能。它们都来自Arrays和Collections类，并且都采用静态方法的形式，其第一个参数是要执行操作的数组或集合。
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提供了两个接口来使用类的数据成员对对象进行排序：

Comparable
Comparator

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

frequency和disjoint算法测试一个或多个"集合"组成的某些方面：
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));
}

寻找极值

min和max算法分别返回指定集合中包含的最小和最大元素。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));
}

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

`Arrays`实用程序类

集合实用程序类

shuffle

常规数据操作

搜索

Composition

寻找极值

相关文章

热门标签

最新文章

目录