분할 정복 알고리즘을 사용하여 구현한 Java 정렬 인덱스 함수의 예

이 글에서는 주로 Java의 분할 정복 알고리즘을 사용하여 정렬 색인 기능을 구현하는 방법을 소개합니다. 정렬 색인을 위한 Java 분할 정복 알고리즘의 관련 운영 기술을 필요한 구체적인 예의 형태로 분석합니다. 그것은 그것을 참조할 수 있습니다

이 기사의 예는 Java의 사용을 설명합니다. 분할 정복 알고리즘은 정렬 색인 기능을 구현합니다. 참고용으로 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다:

/**
 * Find the first q and return the index
 * First method is brutal force
 * Second may
 * be pid and Conquer
 *
 * @author open201
 *
 */
public class Ono {
  /**
   * f(n) = s.length = n;
   *
   * @param s
   * @param q
   * @return
   */
  public static int BrutalForceSearch(int[] s, int q) {
    for (int i = 0; i < s.length; i++) {
      if (q == s[i])
        return i;
    }
    return -1;
  }
  /**
   * f(n) = log(n)
   *
   * @param s
   * @param q
   * @return
   */
  public static int DCSearch(int[] s, int q, int startIndex, int endIndex) {
    if (startIndex > endIndex)
      return -1;
    else {
      int mid = (startIndex + endIndex) / 2;
      if (s[mid] == q)
        return mid;
      else {
        if (s[mid] > q)
          return DCSearch(s, q, startIndex,mid-1);
        else
          return DCSearch(s, q, mid+ 1,endIndex);
      }
    }
  }
  public static void main(String[] args) {
    int [] s = new int[10000000];
    for(int i = 0;i<10000000;i++){
      s[i] = i;
    }
    int q = 10000000-1;
    long startTime = System.currentTimeMillis();
    System.out.println(BrutalForceSearch(s, q));
    long endTime = System.currentTimeMillis();
    System.out.println(endTime-startTime);
    startTime = System.currentTimeMillis();
    System.out.println(DCSearch(s, q, 0, s.length - 1));
    endTime = System.currentTimeMillis();
    System.out.println(endTime-startTime);
  }
}

위 내용은 분할 정복 알고리즘을 사용하여 구현한 Java 정렬 인덱스 함수의 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!