How to solve sorting problem using quick sort in divide and conquer method in java

Problem description:

After entering a number N, enter N numbers, and then sort the N numbers output.

Input:

Output:

Algorithm design:

The basic idea of ​​quick sort is based on the divide-and-conquer strategy. The algorithm idea is as follows:

(1) Decomposition: First, take an element from the sequence as the reference element. Taking the benchmark element as the standard, decompose the problem into two subsequences, so that the subsequence less than or equal to the benchmark element is on the left, and the subsequence greater than the benchmark element is on the right.

(2) Governance: Quickly sort the two subsequences.

(3) Merge: Merge the two sorted subsequences together to get the solution to the original problem.

Free video tutorial recommendation: java learning video

Suppose the current sequence to be sorted is R[low:high], where low≤high, if the size of the sequence is small enough, sort directly, otherwise proceed in 3 steps Processing:

(1) Decomposition: Select an element R[pivot] in R[low:high], and use this as a mark to divide the sequence to be sorted into two sequences R[low: pivot-1] and R[pivot 1:high], and make the values ​​of all elements in the sequence R[low:pivot] less than or equal to R[pivot], and all elements in the sequence R[pivot 1:high] are greater than R[ pivot], at this time the benchmark element is already in the correct position, and it does not need to participate in the subsequent sorting.

(2) Governance: For the two subsequences R[low:pivot-1] and R[pivot 1:high ], sorting is performed by recursively calling the quick sort algorithm.

(3) Merge: Since the sorting of R[low:pivot-1] and R[pivot:high] is performed in place, so After R[low:pivot-1] and R[pivot 1:high] have been sorted, there is no need to do anything in the merging step, and the sequence R[low:high] has been sorted.

Sample 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();
    }
}

Running result:

java Getting Started Tutorial

The above is the detailed content of How to solve sorting problem using quick sort in divide and conquer method in java. For more information, please follow other related articles on the PHP Chinese website!