빠른 정렬 알고리즘 원리 및 Java 재귀 구현

퀵 정렬은 버블 정렬을 개선한 것입니다. 초기 레코드 순서가 키워드별로 정렬되거나 기본적으로 정렬되면 버블 정렬로 변질됩니다. 재귀적 원리를 사용하며 동일한 크기 O(n longn)의 모든 정렬 방법 중에서 평균 성능이 가장 좋습니다. 평균 시간 측면에서 현재 가장 좋은 내부 정렬 방법으로 간주됩니다

기본 아이디어는 정렬할 데이터를 단방향 정렬을 통해 두 개의 독립적인 부분으로 분할하고 한 부분에 있는 모든 데이터를 다른 부분의 모든 데이터는 작아야 하며, 이 방법을 사용하면 데이터의 두 부분을 각각 빠르게 정렬할 수 있으므로 전체 정렬 프로세스를 반복적으로 수행할 수 있으므로 전체 데이터가 정렬된 시퀀스가 ​​됩니다.

세 개의 포인터: 첫 번째 포인터는 피벗키 포인터(피벗)라고 하며, 두 번째 포인터와 세 번째 포인터는 각각 왼쪽 포인터와 오른쪽 포인터로, 각각 가장 왼쪽 값과 가장 오른쪽 값을 가리킵니다. . 왼쪽 포인터와 오른쪽 포인터는 양쪽에서 중앙으로 동시에 접근하며, 접근하는 동안 지속적으로 피벗과 비교되어 피벗보다 작은 요소는 하단으로 이동하고 피벗보다 큰 요소는 이동합니다. 선택되면 절대 변하지 않고 중간에 있게 되며 앞부분은 작고 뒷부분은 커집니다.

두 가지 함수 필요:

① 재귀 함수 public static void QuickSort(int[]n ,int left,int right)
② 분할 함수(원패스 빠른 정렬 함수) public static int partition(int[]n ,int left,int right)

JAVA 소스 코드(성공적으로 실행됨):

package testSortAlgorithm;
public class QuickSort {
 public static void main(String[] args) {
  int [] array = {49,38,65,97,76,13,27};
  quickSort(array, 0, array.length - 1);
  for (int i = 0; i < array.length; i++) {
   System.out.println(array[i]);
  }
 }
 /*先按照数组为数据原型写出算法，再写出扩展性算法。数组{49,38,65,97,76,13,27}
  * */
 public static void quickSort(int[]n ,int left,int right){
  int pivot;
  if (left < right) {
   //pivot作为枢轴，较之小的元素在左，较之大的元素在右
   pivot = partition(n, left, right);
   //对左右数组递归调用快速排序，直到顺序完全正确
   quickSort(n, left, pivot - 1);
   quickSort(n, pivot + 1, right);
  }
 }

 public static int partition(int[]n ,int left,int right){
  int pivotkey = n[left];
  //枢轴选定后永远不变，最终在中间，前小后大
  while (left < right) {
   while (left < right && n[right] >= pivotkey) --right;
   //将比枢轴小的元素移到低端，此时right位相当于空，等待低位比pivotkey大的数补上
   n[left] = n[right];
   while (left < right && n[left] <= pivotkey) ++left;
   //将比枢轴大的元素移到高端，此时left位相当于空，等待高位比pivotkey小的数补上
   n[right] = n[left];
  }
  //当left == right，完成一趟快速排序，此时left位相当于空，等待pivotkey补上
  n[left] = pivotkey;
  return left;
 }
}

빠른 정렬 알고리즘 원리 및 Java 재귀 구현과 관련된 더 많은 기사를 보려면, PHP 중국어 웹사이트를 주목해주세요!