閱讀(7.9k) 書簽贊(4) 我要糾錯

Java 集合算法

2020-08-18 16:58 更新

Java集合教程 - Java集合算法

列表排序

Collection類中的兩個靜態(tài)方法會對List進(jìn)行排序。

sort（List list）按照由元素實(shí)現(xiàn)的Comparable接口定義的順序?qū)ist中的元素進(jìn)行排序。
sort（List list，Comparator c）使用傳入的Comparator對象對元素進(jìn)行排序。

我們還可以使用List接口中的sort（Comparator c）對List進(jìn)行排序，而不使用Collections類。

以下代碼演示了如何對 List 進(jìn)行排序:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("J");
    list.add("R");
    list.add("C");
    list.add("X");

    System.out.println("List: " + list);

    // Uses Comparable implementation in String class
    // to sort the list in natural order
    Collections.sort(list);
    System.out.println("Sorted List:  " + list);

  }
}

上面的代碼生成以下結(jié)果。

例子

以下代碼使用List接口中的sort()方法按其元素長度的升序?qū)α斜磉M(jìn)行排序：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("Java");
    list.add("R");
    list.add("CSS");
    list.add("XML");

    System.out.println("List: " + list);

    // Uses List.sort() method with a Comparator
    list.sort(Comparator.comparing(String::length));

    System.out.println("Sorted List:  " + list);

  }
}

上面的代碼生成以下結(jié)果。

sort()方法使用修改的mergeesort算法，這是一個穩(wěn)定的排序。

在穩(wěn)定的排序中，相等的元素將在排序操作之后保持在它們當(dāng)前的位置。

排序提供了 n*log(n)性能，其中 n 是列表中元素的數(shù)量。

搜索列表

Collections類中的兩個靜態(tài)binarySearch()方法在List中搜索鍵。

該方法使用二分搜索算法執(zhí)行搜索。

int  binarySearch(List list,  T  key)
int  binarySearch(List list, T  key, Comparator c)

List 必須按升序排序，然后才能使用 binarySearch()方法。

如果在列表中找到該鍵，則該方法將在列表中返回其索引。

如果在列表中沒有找到鍵，它返回( - (insertion_index)-1)，其中 Math.abs(( - (insertion_index)-1))是我們可以插入這個鍵的索引仍然保持列表訂購。

在列表中找不到鍵時(shí)，返回值為負(fù)值。

以下代碼段顯示了如何使用此方法:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("Java");
    list.add("R");
    list.add("CSS");
    list.add("XML");

    Collections.sort(list);
    System.out.println("List: " + list);

    int index = Collections.binarySearch(list, "CSS");
    System.out.println("CSS in List  is at " + index);

    index = Collections.binarySearch(list, "Javascript");
    System.out.println("Javascript in List is  at " + index);

  }
}

上面的代碼生成以下結(jié)果。

由于“Javascript”不在列表中，二進(jìn)制搜索返回-3。這意味著如果在列表中插入“Javascript”，它將被插入索引2，使用表達(dá)式（ - （ - 2 + 1））計(jì)算。

隨機(jī)播放列表

Shuffle給我們一個列表中的元素的隨機(jī)排列。

來自Collections類的shuffle()方法的兩個版本如下：

void  shuffle(List list)
void  shuffle(List list, Random  rnd)

以下代碼顯示如何使用shuffle方法。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("Java");
    list.add("R");
    list.add("CSS");
    list.add("XML");

    Collections.sort(list);
    System.out.println("List: " + list);

    Collections.shuffle(list);
    System.out.println("List: " + list);

    Collections.shuffle(list);
    System.out.println("List: " + list);
  }
}

上面的代碼生成以下結(jié)果。

反向列表

我們可以使用 Collections 類的 reverse()的靜態(tài)方法來反轉(zhuǎn)列表中的元素。

void  reverse(List list)

以下代碼顯示如何使用 reverse()方法。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("Java");
    list.add("R");
    list.add("CSS");
    list.add("XML");

    Collections.sort(list);
    System.out.println("List: " + list);

    Collections.reverse(list);
    System.out.println("List: " + list);

  }
}

上面的代碼生成以下結(jié)果。

交換列表項(xiàng)

交換交換列表中的兩個元素。

Collections類的 swap()靜態(tài)方法執(zhí)行交換。

void  swap(List list, int i, int j)

i 和 j 是兩個元素的索引，它們必須在0和size-1之間，其中size是List的大小。

以下代碼顯示了如何使用這些方法對List的元素重新排序。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("Java");
    list.add("R");
    list.add("CSS");
    list.add("XML");

    Collections.sort(list);
    System.out.println("List: " + list);

    // Swap elements at indexes 1 and 3
    Collections.swap(list, 1, 3);
    System.out.println(list);

  }
}

上面的代碼生成以下結(jié)果。

旋轉(zhuǎn)列表

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("Java");
    list.add("R");
    list.add("CSS");
    list.add("XML");

    Collections.sort(list);
    System.out.println("List: " + list);

    // Rotate elements by 2
    Collections.rotate(list, 2);
    System.out.println("After  Rotating by  2: " + list);

  }
}

上面的代碼生成以下結(jié)果。

創(chuàng)建集合的不同視圖

我們可以使用Collections類的asLifoQueue()靜態(tài)方法創(chuàng)建Deque的LIFO隊(duì)列視圖：

<T> Queue<T> asLifoQueue(Deque<T>  deque)

要將Map的實(shí)現(xiàn)用作Set實(shí)現(xiàn)，請使用Collections類的 newSetFromMap()靜態(tài)方法:

<E> Set<E> newSetFromMap(Map<E, Boolean>  map)

只讀集合視圖

當(dāng)將集合傳遞到其他方法時(shí)，我們可以獲取集合的只讀視圖，并且我們不希望被調(diào)用的方法修改集合。

Collections類提供了以下方法來獲取不同類型集合的只讀視圖：

<T> Collection<T> unmodifiableCollection(Collection<?  extends T> c)
<T> List<T>  unmodifiableList(List<?  extends T> list)
<K,V> Map<K,V>  unmodifiableMap(Map<?  extends K,?  extends V>  m)
<K,V> NavigableMap<K,V> unmodifiableNavigableMap(NavigableMap<K,? extends  V>  m)
<T> Set<T> unmodifiableSet(Set<? extends T> s)
<T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T>  s)
static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T>  s)
<K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K,? extends  V>  m)

我們傳遞一個特定類型的集合，并獲得相同類型的只讀集合。

集合的同步視圖

我們可以使用Collections類的以下靜態(tài)方法之一獲取集合的同步視圖。

<T> Collection<T> synchronizedCollection(Collection<T>  c)
<T> List<T>  synchronizedList(List<T> list)
<K,V> Map<K,V>  synchronizedMap(Map<K,V> m)
<K,V> NavigableMap<K,V> synchronizedNavigableMap(NavigableMap<K,V> m)
<T> NavigableSet<T> synchronizedNavigableSet(NavigableSet<T>  s)
<T> Set<T> synchronizedSet(Set<T> s)
<T> SortedSet<T> synchronizedSortedSet(SortedSet<T>  s)
<K,V> SortedMap<K,V> synchronizedSortedMap (SortedMap<K,V> m)

檢查集合

泛型為集合提供編譯時(shí)類型安全。

下面的代碼有一個編譯時(shí)錯誤，因?yàn)槲覀冊噲D添加Integer類型值到一個只能有String值的Set。

Set<String> s = new HashSet<>();
s.add("Hello");
a.add(new Integer(1)); // A compile-time error

我們可以通過使用以下代碼繞過編譯器檢查:

Set<String> s = new HashSet<  >();
s.add("Hello");

Set s2 = s;
s2.add(new Integer(123)); // No  runtime exception

我們可以通過使用檢查的集合避免上述錯誤。Collection類的以下靜態(tài)方法返回特定類型的已檢查集合：

<E> Collection<E> checkedCollection(Collection<E>  c, Class<E>  type)
<E> List<E>  checkedList(List<E> list, Class<E>  type)
<K,V> Map<K,V> checkedMap(Map<K,V>   m, Class<K> keyType,  Class<V> valueType)
<K,V> NavigableMap<K,V> checkedNavigableMap(NavigableMap<K,V>  m, Class<K> keyType,  Class<V> valueType)
<E> NavigableSet<E> checkedNavigableSet(NavigableSet<E>  s, Class<E>  type)
<E> Queue<E> checkedQueue(Queue<E> queue, Class<E>  type)
<E> Set<E> checkedSet(Set<E> s, Class<E>  type)
<K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K,V>  m, Class<K> keyType, Class<V> valueType)
<E> SortedSet<E> checkedSortedSet(SortedSet<E>  s, Class<E>  type)

下面的代碼重寫了上面的代碼。

Set<String>  checkedSet = Collections.checkedSet(new HashSet<String>(),  String.class);
Set s2 = checkedSet;
s2.add(new Integer(1)); // Throws ClassCastException

創(chuàng)建空集合

Collections 類可以返回每種類型的不可變空集合對象。

它也可以返回一個空的迭代器。以下代碼在Collections類中列出了這些靜態(tài)方法：

<T> List<T>  emptyList()
<K,V> Map<K,V>  emptyMap()
<T> Set<T> emptySet()
<T> Iterator<T> emptyIterator()
<T> ListIterator<T> emptyListIterator()

Singleton集合

我們可以使用Collections類創(chuàng)建一個只有一個元素的集合。

我們必須創(chuàng)建這種集合對象，當(dāng)一個方法接受一個集合作為其參數(shù)，我們只有一個對象傳遞給該方法。

這些方法如下:

<T> Set<T> singleton(T o)
<T> List<T>  singletonList(T o)
<K,V> Map<K,V>  singletonMap(K key,  V  value)

以下代碼顯示了如何使用Collections.singleton()方法。

Set<String> singletonSet  = Collections.singleton("Lonely");
// Throws a  runtime exception since a singleton set is immutable singletonSet.add("Hello");

以上內(nèi)容是否對您有幫助：

← Java 特殊類型映射

寫筆記

我要補(bǔ)充

Java 集合算法

Java集合教程 - Java集合算法

列表排序

例子

搜索列表

隨機(jī)播放列表

反向列表

交換列表項(xiàng)

旋轉(zhuǎn)列表

創(chuàng)建集合的不同視圖

只讀集合視圖

集合的同步視圖

檢查集合

創(chuàng)建空集合

Singleton集合

推薦文章

推薦教程

推薦課程