Java는 빠른 정렬 알고리즘(Quicktsort)을 구현합니다.

퀵 정렬 알고리즘 소개
퀵 정렬과 병합 정렬은 모두 분할 정복 방법을 사용하여 알고리즘을 설계합니다. 차이점은 병합 정렬은 기본적으로 동일한 길이의 두 하위 배열로 분할한다는 것입니다. , 병합(병합) 작업이 필요하며 하위 배열을 분할할 때 빠른 정렬이 더 예술적입니다. 분할 후 벤치마크 요소의 왼쪽에 있는 요소는 벤치마크 요소보다 작습니다. 오른쪽은 벤치마크 요소보다 작지 않습니다. 이런 식으로 두 하위 배열을 분리하기만 하면 되며 더 이상 병합 정렬과 같은 병합 작업이 필요하지 않습니다. 참조 요소의 선택은 알고리즘의 효율성에 큰 영향을 미칩니다. 가장 좋은 경우는 두 하위 배열의 크기가 기본적으로 동일하다는 것입니다. 단순화를 위해 마지막 요소를 선택합니다. 보다 발전된 접근 방식에서는 먼저 중앙값을 찾아 중앙값을 마지막 요소와 교환한 다음 동일한 단계를 수행합니다. 분할은 퀵소트의 핵심입니다. 퀵 정렬의 최악의 경우 실행 시간은 O(n2)이지만 예상 실행 시간은 O(nlgn)입니다.

빠른 정렬 알고리즘의 Java 구현
1. 배열을 두 개의 하위 배열과 기본 요소로 분할합니다. 마지막 요소를 기본 요소로 선택하고 인덱스 변수는 가장 최근의 위치를 ​​기록합니다. 기본 요소보다 작은 요소의 위치는 start-1로 초기화됩니다. 기본 요소보다 작은 새 요소가 발견되면 인덱스가 1씩 증가합니다. 첫 번째 요소부터 두 번째 요소까지 순서대로 기본 요소와 비교하여 기본 요소보다 작으면 인덱스를 1 증가시키고 위치 인덱스와 현재 위치의 요소를 교환합니다. 루프가 끝난 후 index+1은 기본 요소가 있어야 하는 위치를 가져오고 index+1을 마지막 요소와 교환합니다.
2. 두 개의 하위 배열 [start, index] 및 [index+2, end]를 각각 정렬합니다.
"Insertsort의 Java 구현"과 마찬가지로 먼저 배열 도구 클래스를 구현합니다. 코드는 다음과 같습니다.

public class ArrayUtils {

     public static void printArray(int[] array) {
      System.out.print("{");
      for (int i = 0; i < array.length; i++) {
       System.out.print(array[i]);
       if (i < array.length - 1) {
        System.out.print(", ");
       }
      }
      System.out.println("}");
     }
     public static void exchangeElements(int[] array, int index1, int index2) {
      int temp = array[index1];
      array[index1] = array[index2];
      array[index2] = temp;
     }
    }

빠른 정렬의 Java 구현 및 테스트 코드는 다음과 같습니다.

public class QuickSort {

  public static void main(String[] args) {
   int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
   System.out.println("Before sort:");
   ArrayUtils.printArray(array);
   quickSort(array);
   System.out.println("After sort:");
   ArrayUtils.printArray(array);
  }
  public static void quickSort(int[] array) {
   subQuickSort(array, 0, array.length - 1);
  }
  private static void subQuickSort(int[] array, int start, int end) {
   if (array == null || (end - start + 1) < 2) {
    return;
   }
   int part = partition(array, start, end);
   if (part == start) {
    subQuickSort(array, part + 1, end);
   } else if (part == end) {
    subQuickSort(array, start, part - 1);
   } else {
    subQuickSort(array, start, part - 1);
    subQuickSort(array, part + 1, end);
   }
  }
  private static int partition(int[] array, int start, int end) {
   int value = array[end];
   int index = start - 1;
   for (int i = start; i < end; i++) {
    if (array[i] < value) {
     index++;
     if (index != i) {
      ArrayUtils.exchangeElements(array, index, i);
     }
    }
   }
   if ((index + 1) != end) {
    ArrayUtils.exchangeElements(array, index + 1, end);
   }
   return index + 1;
  }
 }

빠른 정렬 알고리즘(Quicktsort)의 Java 구현과 관련된 더 많은 기사를 보려면 비용을 지불하세요. PHP 중국어 웹사이트에 주목하세요!