Java의 분할 정복 방법에서 빠른 정렬을 사용하여 정렬 문제를 해결하는 방법

문제 설명:

숫자 N을 입력한 후 N개의 숫자를 입력하고 N개의 숫자를 정렬하여 출력합니다.

입력:

출력:

알고리즘 설계:

퀵 정렬의 기본 아이디어는 분할 정복 전략을 기반으로 하며, 알고리즘 아이디어는 다음과 같습니다.

(1) 분해: 먼저 배열에서 요소를 벤치마크 요소로 가져옵니다. 벤치마크 요소를 표준으로 사용하여 문제를 두 개의 하위 시퀀스로 분해하여 벤치마크 요소보다 작거나 같은 하위 시퀀스가 ​​왼쪽에 오도록 합니다. , 벤치마크 요소보다 큰 하위 시퀀스가 ​​오른쪽에 있습니다.

(2) 거버넌스: 두 개의 하위 시퀀스를 빠르게 정렬합니다.

(3) 병합: 원래 문제에 대한 솔루션을 얻기 위해 두 개의 하위 시퀀스를 병합합니다.

무료 동영상 튜토리얼 추천:

java 학습 동영상

현재 정렬할 시퀀스가 ​​R[low:high]라고 가정하고, 시퀀스의 크기가 충분히 작으면 직접 정렬하고, 그렇지 않으면 정렬합니다.

(1) 분해: R에서 [low:high]에서 R[pivot] 요소를 선택하고 이를 레이블로 사용하여 정렬할 시퀀스를 두 개의 시퀀스 R[low: ivot-1]과 R[pivot+1:high]를 만들고, 시퀀스를 R로 만듭니다. [low:pivot]에 있는 모든 요소의 값은 R[pivot]보다 작거나 같고, 시퀀스에 있는 모든 요소는 R입니다. [pivot+1:high]는 R[pivot]보다 큽니다. 이때 참조 요소는 이미 올바른 위치에 있으므로 나중에 정렬할 필요가 없습니다.

(2) 거버넌스: 둘을 위한 것입니다. 하위 시퀀스 R[low:pivot-1] 및 R[pivot+1:high], 빠른 정렬 알고리즘을 재귀적으로 호출하여 정렬합니다.

(3) 병합: R[low:pivot-1] 및 R[을 정렬하므로 Pivot:high]가 현장에서 수행되고 R[low:pivot-1] 및 R[pivot+1:high]가 모두 정렬된 후 병합 단계에서 아무 작업도 수행할 필요가 없습니다. low:high]가 이미 정렬되었습니다.

샘플 코드:

//程序目的:用分治法中的快速排序解决排序问题
import java.util.Scanner;
public class text2 {
     public static void swap(int array[],int a,int b){//交换函数
         int temp;
         temp=array[a];
         array[a]=array[b];
         array[b]=temp;
     }
   public  static int Partition(int r[],int low,int high){
        int i=low ;
        int j=high;
        int pivot=r[low];//基准元素
        while(i<j) {
            while (i < j && r[j] > pivot) //向左扫描
                j--;

                if (i < j) {
                    swap(r, i++, j);
                }
                while (i < j && r[i] <= pivot) {//向右扫描
                    i++;
                }
                if (i < j) {
                    swap(r, i, j--);
                }
            }

        return i;
    }
    public static void QuickSort(int R[],int low,int high){//快速排序递归算法
         int mid;
         if(low<high){
             mid=Partition(R,low,high);//基准位置
             QuickSort(R,low,mid-1);//左区间递归快速排序
             QuickSort(R,mid+1,high);//右区间递归快速排序
         }
    }
    public static void main(String args[]){
         Scanner sc=new Scanner (System.in);
         int i;
         int n;//数据的个数
        System.out.println("请先输入要排序元素的个数");
        n=sc.nextInt();
        System.out.println("请输入要排序的数据");
        int []a=new int[n];
         for (i=0;i<n;i++){
             a[i]=sc.nextInt();
         }
         QuickSort(a,0,n-1);
        System.out.println("排序后的数据");
        for (i=0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

실행 결과:

권장 관련 학습 튜토리얼:

java Getting Started Tutorial

위 내용은 Java의 분할 정복 방법에서 빠른 정렬을 사용하여 정렬 문제를 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!