Javaの分割統治法でクイックソートを使用してソート問題を解決する方法

問題の説明:

数字 N を入力した後、N 個の数字を入力し、出力された N 個の数字を並べ替えます。 。

入力:

出力:

アルゴリズム設計:

#クイック ソートの基本的な考え方は、分割統治戦略に基づいており、アルゴリズムの考え方は次のとおりです:

(1) 分解: まず、シーケンスから要素を参照要素として取得し、ベンチマーク要素を標準として、問題を 2 つのサブシーケンスに分解し、ベンチマーク要素以下のサブシーケンスを左側に、ベンチマークより大きいサブシーケンスを配置します。要素は右側にあります。

(2) ガバナンス: 2 つのサブシーケンスをすばやく並べ替えます。

(3) マージ: 並べ替えられた 2 つのサブシーケンスをマージして、元の問題の解決策を取得します。

無料のビデオ チュートリアルの推奨事項:

Java 学習ビデオ

ソート対象の現在のシーケンスが R[low:high] (low≤high) であると仮定します。シーケンスのサイズが十分に小さい場合は、直接ソートします。そうでない場合は、3 つのステップで処理します。 処理:

(1) 分解: R[low:high] 内の要素 R[pivot] を選択し、これを使用します。ソート対象の配列を R[low:pivot-1] と R[pivot 1:high] の 2 つの配列に分割し、配列 R[low:pivot] 内のすべての要素の値が以下になるようにするためのマークとしてR[pivot] または R[pivot] に等しく、シーケンス R[pivot 1:high] 内のすべての要素が R[pivot] より大きい場合、この時点でベンチマーク要素はすでに正しい位置にあり、ベンチマーク要素はベンチマーク要素に参加する必要はありません。

(2) ガバナンス: 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] の後ソートされているため、マージ ステップでは何もする必要はなく、シーケンス R[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 中国語 Web サイトの他の関連記事を参照してください。