如安在java中运用分治法中的疾速排序处理排序问题【JAVA教程】,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中运用分治法中的疾速排序处理排序问题的细致内容，更多请关注ki4网别的相干文章！

标签：java分治法快速排序