What is the idea of ​​​​implementing the quick sort algorithm in java?

1. What is the quick sort algorithm?

In fact, quick sort (Quicksort) is an improvement on bubble sort.

2. The idea of ​​quick sorting algorithm

The data to be sorted is divided into two independent parts through one sorting. All the data in one part is higher than all the data in the other part. should be small, and then use this method to quickly sort the two parts of the data respectively. The entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.

(Video tutorial recommendation: java video tutorial)

3. Implementation ideas

(1) Use the first keyword K 1 as the control words, divide [K 1 ,K 2 ,…,K n ] into two sub-areas, so that all keywords in the left area are less than or equal to K 1 , all keywords in the right area are greater than or equal to K 1 , and finally the control word is located in the middle of the two sub-areas. proper location. The data in the subarea is still in an unordered state. ;

(2) Treat the left area as a whole and use the steps in (1) to process it, and perform the same processing on the right area. (i.e. recursion)

(3) Repeat steps (1) and (2) until the left area is processed.

4. Implementation code

static void quicksort(int n[], int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);
            quicksort(n, left, dp - 1);
            quicksort(n, dp + 1, right);
        }
    }
 
    static int partition(int n[], int left, int right) {
        int pivot = n[left];
        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right)
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right)
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }

Recommended tutorial: java entry program

The above is the detailed content of What is the idea of ​​​​implementing the quick sort algorithm in java?. For more information, please follow other related articles on the PHP Chinese website!