問題描述:

輸入一個數(shù)字N后,輸入N個數(shù)字,將N個數(shù)字排序后輸出。

輸入:

輸出：

算法設(shè)計:

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

(1)分解:先從數(shù)列中取出一個元素作為基準(zhǔn)元素.以基準(zhǔn)元素為標(biāo)準(zhǔn),將問題分解為兩個子序列,使小于或等于基準(zhǔn)元素的子序列在左側(cè),使大于基準(zhǔn)元素的子序列在右側(cè).

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

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

免費視頻教程推薦：java學(xué)習(xí)視頻

設(shè)當(dāng)前待排列的序列為R[low:high],其中l(wèi)ow≤high,如果序列的規(guī)模足夠小,則直接進行排序,否則分3步處理：

(1)分解:在R[low:high]中選定一個元素R[pivot],以此為標(biāo)注將要排序的序列劃分為兩個序列R[low:pivot-1]和R[pivot+1:high],并使序列R[low:pivot]中所有元素的值小于等于R[pivot],序列R[pivot+1:high]中所有的元素均大于R[pivot],此時基準(zhǔn)元素已經(jīng)位于正確的位置,它無需參加后面的排序.

(2)治理:對于兩個子序列R[low:pivot-1]和R[pivot+1:high],分別通過遞歸調(diào)用快速排序算法來進行排序.

(3)合并:由于對R[low:pivot-1]和R[pivot:high]的排序是原地進行的,所以在R[low:pivot-1]和R[pivot+1:high]都已經(jīng)排好序后,合并步驟無需做什么,序列R[low:high]就已經(jīng)排好序了.

示例代碼：

//程序目的:用分治法中的快速排序解決排序問題
import java.util.Scanner;
public class text2 {
     public static void swap(int array[],int a,int b){//交換函數(shù)
         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];//基準(zhǔn)元素
        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);//基準(zhǔn)位置
             QuickSort(R,low,mid-1);//左區(qū)間遞歸快速排序
             QuickSort(R,mid+1,high);//右區(qū)間遞歸快速排序
         }
    }
    public static void main(String args[]){
         Scanner sc=new Scanner (System.in);
         int i;
         int n;//數(shù)據(jù)的個數(shù)
        System.out.println("請先輸入要排序元素的個數(shù)");
        n=sc.nextInt();
        System.out.println("請輸入要排序的數(shù)據(jù)");
        int []a=new int[n];
         for (i=0;i<n;i++){
             a[i]=sc.nextInt();
         }
         QuickSort(a,0,n-1);
        System.out.println("排序后的數(shù)據(jù)");
        for (i=0;i<n;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

運行結(jié)果：

相關(guān)學(xué)習(xí)教程推薦：java入門教程

以上是如何在java中使用分治法中的快速排序解決排序問題的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！