Java의 빠른 정렬의 간단한 예

이 글에서는 주로 Java의 간단한 퀵 정렬 예제를 소개하는데, 이는 어느 정도 참고할만한 가치가 있습니다. 관심 있는 친구들은 참고해 보세요.

1. 기본 개념

요소 찾기 (이론적으로는 부담없이 할 수 있습니다.) 피벗(pivot)으로 한 후, 피벗 왼쪽에 있는 요소의 값이 피벗 값보다 크지 않고, 피벗 오른쪽에 있는 요소의 값이 더 크지 않도록 배열을 분할합니다. 피벗 값보다 작지 않아야 합니다. 이러한 방식으로 위치 정렬 후 피벗 요소가 올바른 값으로 조정됩니다. 재귀적 빠른 정렬은 정렬 후 다른 n-1 요소를 올바른 위치로 조정합니다. 마지막으로 정렬 후 각 요소가 올바른 위치에 배치되어 정렬이 완료됩니다. 따라서 퀵 정렬 알고리즘의 핵심 알고리즘은 분할 연산, 즉 분할 정복 재귀를 위해 벤치마크의 위치를 ​​조정하고 반환된 벤치마크의 최종 위치를 조정하는 방법이다.

2. 벤치마크 요소 선택

1. 벤치마크 요소 수정

입력 순서가 무작위인 경우 처리 시간은 허용됩니다. 배열이 이미 정렬되어 있다면 이때의 나누기는 매우 잘못된 나누기입니다. 각 나눗셈은 정렬할 순서를 하나씩만 줄일 수 있기 때문에 이는 최악의 시나리오입니다. 빠른 정렬은 버블 정렬이 되며 시간 복잡도는 Θ(n^2)입니다. 더욱이, 입력 데이터가 순서대로 정렬되거나 부분적으로 정렬되는 것이 매우 일반적입니다. 따라서 첫 번째 요소를 기본 요소로 사용하는 것은 매우 좋지 않으며 즉시 폐기해야 합니다.

2. 랜덤베이스 위안

비교적 안전한 전략입니다. 참조 요소의 위치는 무작위이므로 결과 분할이 항상 품질이 낮은 분할은 아닙니다. 전체 배열 수가 모두 동일한 경우에도 여전히 최악의 경우이며 시간 복잡도는 O(n^2)입니다. 실제로 이론적으로 최악의 경우를 얻기 위해 퀵 정렬을 무작위로 수행할 확률은 1/(2^n)에 불과합니다. 따라서 무작위 퀵 정렬은 대부분의 입력 데이터에 대해 O(n×log(n))의 예상 시간 복잡도를 달성할 수 있습니다.

3. 세 숫자의 중간 찾기

가장 좋은 나눗셈은 정렬할 수열을 같은 길이의 부분 수열로 나누는 것입니다. 가장 좋은 상태에서는 수열의 중간 값인 N/2를 사용할 수 있습니다. 숫자. 그러나 이는 계산하기 어렵고 퀵 정렬 속도가 크게 느려집니다. 이러한 중앙값 추정치는 세 개의 요소를 무작위로 선택하고 해당 중앙값을 기본 요소로 사용하여 얻을 수 있습니다. 실제로 무작위성은 큰 도움이 되지 않으므로 일반적인 접근 방식은 왼쪽 끝, 오른쪽 끝 및 중앙 위치의 세 요소의 중앙값을 기본 요소로 사용하는 것입니다.

3. 파티션 알고리즘

퀵 정렬의 핵심은 파티션 알고리즘입니다. 코드는 아래와 같습니다:

  public int partition(int[] num,int left,int right){
    if(num==null || num.length<=0 || left<0 || right>=num.length){
      return 0;
    }
    int prio=num[left+(right-left)/2];  //获取数组中间元素的下标
    while (left<=right){         //从两端交替向中间扫描
      while (num[left]<prio)
        left++;
      while (num[right]>prio)
        right--;
      if (left<=right){
        swap(num,left,right);    //最终将基准数归位 
        left++;
        right--;
      }
    }
    return left;
  }

이 방법의 아이디어는 먼저 피벗 요소를 찾는 것입니다(첫 번째 요소는 이 방법의 구현에서 발견됩니다. 이에 대한 실제로 많은 기사가 있지만 이에 대해 설명하겠습니다. 여기에서 설명을 단순화한 다음 배열에서 시작합니다(구체적인 위치는 전달된 매개변수에 의해 결정됨). 왼쪽 요소가 요소보다 큰 것으로 확인될 때마다 왼쪽과 오른쪽에 두 개의 포인터가 생성됩니다. 피벗 요소인 경우 i가 정지하고 오른쪽 요소가 피벗 요소 j보다 작으면 정지하며 이를 교환합니다. 두 숫자의 위치. 왼쪽과 오른쪽 두 포인터가 만날 때까지. 그런 다음 피벗 요소를 있어야 할 왼쪽 위치에 삽입합니다.

이렇게 하면 최종 결과는 배열의 [왼쪽, 오른쪽] 부분이 두 부분으로 표시되도록 하는 것입니다. 왼쪽 피벗 요소의 최종 위치는 피벗 요소보다 작거나 같고, 오른쪽은 피벗 요소보다 크거나 같습니다. 피벗 요소는 완전히 정확한 위치에 삽입됩니다.

4. 정렬 알고리즘 구현

package sort;
/**
 * 快速排序
 * 快速排序采用了分治策略。就是在一个数组中取一个基准数字，把小的数放基准的左边，大的数放基准的右边。
 * 基准左边和右边分别是新的序列。在新的序列中再取一个基准数字，小的放左边，大的放右边。
 * 这个里面用到的递归。我们需要三个参数，一个是数组，另外两个是序列的边界
 * @author HJS
 */
public class QuickSort{

  void sort(int num[],int left,int right){
    if (left
로그인 후 복사

위 내용은 Java의 빠른 정렬의 간단한 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!