Comment résoudre le problème de tri en utilisant la méthode de tri rapide diviser pour régner en Java

Description du problème :

Après avoir entré un nombre N, entrez N nombres, puis triez la sortie des N nombres .

Entrée :

Sortie :

Conception de l'algorithme :

L'idée de base du tri rapide est basée sur la stratégie diviser pour régner. L'idée de l'algorithme est la suivante :

(1) Décomposition : Premièrement, prenez un élément du tableau comme élément de référence. En prenant l'élément de référence comme standard, décomposez le problème en deux sous-séquences, de sorte que la sous-séquence inférieure ou égale à l'élément de référence soit à gauche et la sous-séquence supérieure au repère. l'élément est à droite.

(2) Gouvernance : Droite Triez rapidement les deux sous-séquences

(3) Fusionner : Fusionnez les deux sous-séquences triées ensemble pour obtenir la solution au problème d'origine.

Recommandation de didacticiel vidéo gratuit : vidéo d'apprentissage Java

Supposons que la séquence actuelle à trier soit R[low:high], où low≤high, si la taille de la séquence est assez petite, triez directement, sinon procédez en 3 étapes Traitement :

(1) Décomposition : Sélectionnez un élément R[pivot] dans R[low:high], et utilisez ceci comme une marque pour diviser la séquence à trier en deux séquences R[low: pivot-1] et R[pivot+1:high], et faire les valeurs de tous les éléments de la séquence R[low:pivot] inférieur ou égal à R[pivot], et rendre tous les éléments de la séquence R[pivot+1:high] supérieurs à R[pivot], à ce moment l'élément de référence est déjà dans la position correcte, et il n'a pas besoin pour participer au tri ultérieur.

(2) Gouvernance : Pour les deux sous-séquences R[low:pivot-1] et R[pivot+ 1:high], le tri est effectué en appelant récursivement l'algorithme de tri rapide.

(3) Fusion : Puisque le tri de R[low:pivot-1] et R[pivot:high] est effectué sur place, donc après R[low:pivot-1] et R[pivot+ 1:high] ont été triés, il n'est pas nécessaire de faire quoi que ce soit lors de l'étape de fusion et la séquence R[low:high] a déjà été triée.

Exemple de code :

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

Résultats d'exécution :

Tutoriels d'apprentissage associés Recommandé : Tutoriel d'introduction à Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!