Java 빠른 정렬 알고리즘 구현(Quicktsort)

빠른 정렬 알고리즘은 빠른 정렬과 병합 정렬을 모두 분치법으로 설계하는 알고리즘을 소개한다. 병합 정렬은 수조를 두 개의 기본 같은 길이의 서브 그룹으로 나누어 각각 정렬한 후에 병합(Merge) 조작을 해야 한다. 빠른 정렬은 분자 수조를 분리할 때 더욱 예술적이다. 하나의 기준 원소를 취하고 분리한 후 기준 원소의 왼쪽 원소는 모두 기준 원소보다 작다.오른쪽의 원소는 모두 기준 원소보다 작지 않다. 이렇게 하면 두 개의 하위 그룹에 대해 각각 정렬하기만 하면 된다. 더 이상 병합 정렬처럼 병합 작업이 필요하지 않다.기준 요소의 선택은 알고리즘의 효율에 큰 영향을 미치는데 가장 좋은 상황은 두 개의 서브 그룹의 크기가 기본적으로 비슷하다는 것이다.간단하게 말하자면, 우리는 마지막 원소를 선택한다. 더 높은 방법은 먼저 중위수를 찾고 중위수를 마지막 원소와 교환한 다음에 같은 조작 절차를 진행할 수 있다.버스트는 빠른 정렬의 핵심입니다.빠른 정렬의 최악의 운행 시간은 O(n2)이지만, 기대하는 운행 시간은 O(nlgn)입니다.
빠른 정렬 알고리즘 자바 구현 1.수조를 두 개의 하위 수조로 나누어 하나의 기준 요소를 추가한다. 마지막 원소를 기준 원소로 선택하고 index 변수는 최근 기준 원소보다 작은 원소가 있는 위치를 기록한다. start-1로 초기화하여 기준 원소보다 작은 원소를 발견하고 index 더하기 1을 발견한다.첫 번째 원소부터 마지막 두 번째 원소까지 순서대로 기준 원소와 비교하면 기준 원소보다 작고 index 더하기 1, 교환 위치 index와 현재 위치의 원소입니다.순환이 끝난 후 index+1은 기준 요소가 있어야 할 위치를 얻어 index+1과 마지막 요소를 교환합니다.2. [start, index], [index+2,end] 두 개의 하위 그룹을 정렬합니다. 예를 들어 는 하나의 하위 그룹 도구 클래스를 먼저 실현합니다.코드는 다음과 같습니다.

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;
  }
 }