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

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

문제 설명:

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

입력:

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

출력:

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

알고리즘 설계:

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

(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의 분할 정복 방법에서 빠른 정렬을 사용하여 정렬 문제를 해결하는 방법

권장 관련 학습 튜토리얼:

java Getting Started Tutorial

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

성명
이 기사는 CSDN에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제
Java (Serial, Parallel, CMS, G1, ZGC)의 다른 쓰레기 수집 알고리즘은 무엇입니까?Java (Serial, Parallel, CMS, G1, ZGC)의 다른 쓰레기 수집 알고리즘은 무엇입니까?Mar 14, 2025 pm 05:06 PM

이 기사에서는 다양한 Java Garbage Collection 알고리즘 (Serial, Parallel, CMS, G1, ZGC), 성능 영향 및 큰 힙이있는 응용 분야에 대한 적합성에 대해 설명합니다.

JVM (Java Virtual Machine)은 무엇이며 내부적으로 어떻게 작동합니까?JVM (Java Virtual Machine)은 무엇이며 내부적으로 어떻게 작동합니까?Mar 14, 2025 pm 05:05 PM

이 기사는 JVM (Java Virtual Machine)에 대해 설명하여 다양한 플랫폼에서 Java 프로그램을 실행하는 데있어 역할을 자세히 설명합니다. JVM의 내부 프로세스, 주요 구성 요소, 메모리 관리, 쓰레기 수집 및 성능 Optimizatio를 설명합니다.

JavaScript로 스크립팅하는 데 Java의 Nashorn 엔진을 어떻게 사용합니까?JavaScript로 스크립팅하는 데 Java의 Nashorn 엔진을 어떻게 사용합니까?Mar 14, 2025 pm 05:00 PM

Java의 Nashorn Engine을 사용하면 Java 앱 내에서 JavaScript 스크립팅이 가능합니다. 주요 단계로는 내슈런 설정, 스크립트 관리 및 성능 최적화가 포함됩니다. 주요 이슈에는 NASHORN의 감가 상기 거점으로 인한 보안, 메모리 관리 및 향후 호환성이 포함됩니다.

자동 리소스 관리에 Java의 Try-With-Resources 문을 어떻게 사용합니까?자동 리소스 관리에 Java의 Try-With-Resources 문을 어떻게 사용합니까?Mar 14, 2025 pm 04:59 PM

Java의 시도는 파일 스트림 또는 데이터베이스 연결과 같은 리소스를 자동으로 닫아 코드 가독성 및 유지 관리 가능성을 향상시켜 자원 관리를 단순화합니다.

Java의 열거를 사용하여 고정 된 값 세트를 나타내는 방법은 무엇입니까?Java의 열거를 사용하여 고정 된 값 세트를 나타내는 방법은 무엇입니까?Mar 14, 2025 pm 04:57 PM

Java 열거는 고정 된 값 세트를 나타냅니다. 고정 된 값 세트를 나타냅니다. 맞춤형 방법 및 생성자를 통해 유형 안전, 가독성 및 추가 기능을 제공합니다. 코드 조직을 향상시키고 효율적인 가치 처리를 위해 스위치 문에 사용할 수 있습니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

에디트플러스 중국어 크랙 버전

에디트플러스 중국어 크랙 버전

작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

WebStorm Mac 버전

WebStorm Mac 버전

유용한 JavaScript 개발 도구

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

Atom Editor Mac 버전 다운로드

Atom Editor Mac 버전 다운로드

가장 인기 있는 오픈 소스 편집기