So lösen Sie Sortierprobleme mithilfe der Schnellsortierung in der Divide-and-Conquer-Methode in Java

Problembeschreibung:

Nachdem Sie eine Zahl N eingegeben haben, geben Sie N Zahlen ein und sortieren Sie dann die ausgegebenen N Zahlen .

Eingabe:

Ausgabe:

Algorithmusentwurf:

Die Grundidee der schnellen Sortierung basiert auf der Divide-and-Conquer-Strategie. Die Algorithmusidee lautet wie folgt:

(1) Zerlegung: Erstens. Nehmen Sie ein Element aus dem Array als Referenzelement und zerlegen Sie das Problem in zwei Teilsequenzen, sodass sich die Teilsequenz, die kleiner oder gleich dem Benchmark-Element ist, auf der linken Seite befindet und die Teilsequenz größer als das Benchmark-Element ist Element befindet sich auf der rechten Seite.

(2) Governance: Sortieren Sie die beiden Teilsequenzen schnell.

(3) Zusammenführen: Führen Sie die beiden sortierten Teilsequenzen zusammen, um die Lösung des ursprünglichen Problems zu erhalten.

Kostenlose Video-Tutorial-Empfehlung: Java-Lernvideo

Angenommen, die aktuell zu sortierende Sequenz ist R[low:high], wobei low≤high, if Die Größe der Sequenz ist klein genug, direkt sortieren, andernfalls in 3 Schritten fortfahren. Verarbeitung:

(1) Zerlegung: Wählen Sie ein Element R[pivot] in R[low:high] aus und verwenden Sie es Dies dient als Markierung, um die zu sortierende Sequenz in zwei Sequenzen R[low:pivot-1] und R[pivot+1:high] zu unterteilen und die Werte aller Elemente in der Sequenz R[low:pivot] festzulegen. kleiner oder gleich R[pivot] und machen Sie alle Elemente in der Sequenz R[pivot+1:high] größer als R[pivot], zu diesem Zeitpunkt befindet sich das Referenzelement bereits an der richtigen Position und ist nicht erforderlich um an der anschließenden Sortierung teilzunehmen.

(2) Governance: Für die beiden Teilsequenzen R[low:pivot-1] und R[pivot+ 1:high] erfolgt die Sortierung durch rekursiven Aufruf des Schnellsortierungsalgorithmus.

(3) Zusammenführen: Da die Sortierung von R[low:pivot-1] und R[pivot:high] an Ort und Stelle durchgeführt wird, also nach R[low:pivot-1] und R[pivot+ 1:high] wurden sortiert, es besteht keine Notwendigkeit, im Zusammenführungsschritt etwas zu tun, und die Sequenz R[low:high] wurde bereits sortiert.

Beispielcode:

//程序目的:用分治法中的快速排序解决排序问题
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();
    }
}

Laufergebnisse:

Verwandte Lerntutorials Empfohlen: Java-Einführungs-Tutorial

Das obige ist der detaillierte Inhalt vonSo lösen Sie Sortierprobleme mithilfe der Schnellsortierung in der Divide-and-Conquer-Methode in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!