如何在java中使用分治法中的快速排序來解決排序問題

問題描述:

#輸入一個數字N後,輸入N個數字,將N個數字排序後輸出。

輸入:

#輸出：

演算法設計:

快速排序的基本思想是基於分治策略的,其演算法思想如下：

(1)分解:先從數列中取出一個元素作為基準元素.以基準元素為標準,將問題分解為兩個子序列,使小於或等於基準元素的子序列在左側,使大於基準元素的子序列在右側.

(2)治理:對兩個子序列進行快速排序.

(3)合併:將排好序的兩個子序列合併在一起,得到原問題的解.

免費視訊教學推薦： java學習影片

設當前待排列的序列為R[low:high],其中low≤high,如果序列的規模足夠小,則直接進行排序,否則分3步處理：

(1)分解:在R[low:high]中選定一個元素R[pivot],以此為標註將要排序的序列劃分為兩個序列R[low: pivot-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]都已經排好序後,合併步驟無需做什麼,序列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入門教學

以上是如何在java中使用分治法中的快速排序來解決排序問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！