Home > Java > JavaBase > body text

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

王林
Release: 2019-11-28 15:45:02
forward
1967 people have browsed it

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:

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

Output:

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

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();
    }
}
Copy after login

Running result:

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

## Recommended related learning tutorials:

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!

Related labels:
source:csdn.net
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template