Java에서 QuickSort 빠른 정렬 알고리즘을 구현하는 방법에 대한 그래픽 설명

버블 정렬, 선택 정렬 등의 알고리즘에 비해 퀵 정렬의 구체적인 알고리즘 원리와 구현이 다소 어렵습니다. 퀵 정렬을 더 잘 이해하기 위해 퀵 정렬의 알고리즘 원리를 예제 형식으로 자세히 설명합니다. 이전 정렬 알고리즘에서는 5명의 선수의 키 정렬 문제를 예로 들어 설명했는데, 여기서는 퀵 정렬의 특성을 더 잘 반영하기 위해 3명의 선수를 추가합니다. 예시에 등장한 8명의 선수들의 상세정보와 키 정보는 다음과 같습니다. (F, G, H는 신규 선수입니다.) : A(181), B(169), C(187), D(172), E( 163), F(191), G(189), H(182)

이전 정렬 알고리즘에서는 이러한 정렬을 코치가 완료했습니다. 이제는 선수 수가 증가했기 때문에 코치도 원합니다. 휴식을 취하기 위해 코치는 보조원 2명을 불러 퀵 정렬 방식을 이용해 8명의 선수들의 키를 왼쪽에서 오른쪽으로, 낮은 곳에서 높은 곳으로 정렬해 달라고 요청했다.

빠른 정렬 방식의 알고리즘 원리에 따라 아래 그림과 같이 선수 배치 양쪽에 보조원 2명이 서 있습니다

먼저, 어시스턴트 1은 배열에서 선수를 선택합니다(보통 왼쪽의 첫 번째 선수 또는 가장 가운데 선수). 여기에서는 선수 A(181)를 선택합니다. 정렬은 왼쪽에서 오른쪽, 낮은 것에서 높은 순이므로 보조자 1은 비교를 위한 벤치마크로 키가 A(181)(선택된 A(181))보다 작은 선수가 필요합니다. 선수 A(181) 비교) :

계속해서 1차 퀵정렬 상세도를 참고해 보자.

두 명의 보조원이 정리해서 찾고 있을 때 진행 중 만난 후 현재 라운드의 비교를 중단하고 두 보조자가 만나는 빈 공간에 처음 선택한 선수 A(181)를 배치한다

퀵 정렬에서 두 보조자가 만나면 이번 라운드 정렬이 끝났습니다. 이때, 두 선수가 만나는 위치 A(181)를 분할점으로 하여 배열의 왼쪽에 있는 선수들은 모두 A(181)보다 키가 작은 선수들이고, 오른쪽에 있는 선수들은 A(181) 선수보다 키가 큰 모든 선수가 배치됩니다. 이때 A(181)의 왼쪽과 오른쪽 두 가지 정렬을 나누어서 살펴보도록 하겠습니다. 위에서 언급한 두 보조자의 정렬 방법을 계속해서 사용하여 양쪽 정렬을 하게 되면 여러 개의 정렬을 거친 후입니다. , 마침내 필요한 정렬 결과를 얻을 수 있습니다.

위는 퀵정렬의 전체 정렬 구현 과정이다. 퀵 정렬은 위의 정렬 규칙을 사용하여 하나의 배열을 두 개의 배열로, 두 개의 배열을 네 개의 배열로 나누어 분리할 배열이 없을 때까지 최종적으로 원하는 정렬 결과를 얻습니다.

이제 우리는 위의 8명의 선수의 키를 정렬하기 위해 빠른 정렬을 사용하도록 Java 코드를 프로그래밍합니다.

/**
 * 对指定的数组中索引从start到end之间的元素进行快速排序
 * 
 * @param array 指定的数组
 * @param start 需要快速排序的数组索引起点
 * @param end 需要快速排序的数组索引终点
 */
public static final void quickSort(int[] array, int start, int end) {
  // i相当于助手1的位置，j相当于助手2的位置
  int i = start, j = end;
  int pivot = array[i]; // 取第1个元素为基准元素
  int emptyIndex = i; // 表示空位的位置索引，默认为被取出的基准元素的位置
  // 如果需要排序的元素个数不止1个，就进入快速排序(只要i和j不同，就表明至少有2个数组元素需要排序)
  while (i < j) {
    // 助手2开始从右向左一个个地查找小于基准元素的元素
    while (i < j && pivot <= array[j])
      j--;
    if (i < j) {
      // 如果助手2在遇到助手1之前就找到了对应的元素，就将该元素给助手1的"空位"，j成了空位
      array[emptyIndex] = array[emptyIndex = j];
    }
     
    // 助手1开始从左向右一个个地查找大于基准元素的元素
    while (i < j && array[i] <= pivot)
      i++;
    if (i < j) {
      // 如果助手1在遇到助手2之前就找到了对应的元素，就将该元素给助手2的"空位"，i成了空位
      array[emptyIndex] = array[emptyIndex = i];
    }
  }    
  // 助手1和助手2相遇后会停止循环，将最初取出的基准值给最后的空位
  array[emptyIndex] = pivot;
   
  // =====本轮快速排序完成=====
   
  // 如果分割点i左侧有2个以上的元素，递归调用继续对其进行快速排序
  if (i - start > 1) {
    quickSort(array, 0, i - 1);
  }
  // 如果分割点j右侧有2个以上的元素，递归调用继续对其进行快速排序
  if (end - j > 1) {
    quickSort(array, j + 1, end);
  }
}
 
//主方法
public static void main(String[] args) {
  // =====使用快速排序法对表示8名运动员身高的数组heights进行从低到高的排序=====
  // A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
  int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182 };
  // 调用快速排序方法
  quickSort(heights, 0, heights.length - 1);
  // 输出排序后的结果
  for (int height : heights) {
    System.out.println(height);
  }
}

위 Java 코드의 출력은 다음과 같습니다.

163
169
172
181
182
187
189
191

참고: 지역적 사고 차이로 인해 위의 퀵 정렬의 코드 구현은 여러 변형이 있을 수 있습니다. 하지만 어떤 형태로 변형되더라도 퀵 정렬의 핵심 아이디어는 변하지 않습니다.

또 다른 구현: 단방향 스캔
빠른 정렬 배열 분할을 위한 또 다른 버전의 단방향 스캔이 있습니다. 구체적인 단계는 배열의 마지막 요소를 분할 요소로 선택하고 설정하는 것입니다. 동일한 두 포인터, 포인터 i는 배열의 첫 번째 요소 앞의 위치를 ​​가리키고 포인터 j는 배열의 첫 번째 요소를 가리킵니다. j는 앞에서 오른쪽으로, 왼쪽에서 오른쪽으로 스캔하고 분할 요소보다 작거나 같은 요소를 만나면 i를 1만큼 증가시킨 다음 i와 j가 가리키는 요소를 바꿉니다. 마지막으로 i+1 위치의 요소를 분할 요소와 교환하여 배열 분할을 완료합니다. 코드는 다음과 같이 구현됩니다.

int partition(int[] a, int lo, int hi) {
  int i = lo - 1, j = lo;
  int v = a[hi];
  while (j < hi) {
    if (a[j] <= v) {
      swap(a, ++i, j);
    }
    j++;
  }
  swap(a, i + 1, hi);
  return i + 1;
}

quickSort 빠른 정렬 알고리즘을 Java로 구현하는 방법을 설명하는 더 많은 그림과 텍스트를 보려면 PHP 중국어 웹사이트에서 관련 기사를 주목하세요!