Sorting algorithm Java code implementation (5)-quick sort

Sorting algorithm Java code implementation (5)-quick sort

Content of this article:

  • Quick sort

Quick sort

Algorithm idea:

Split the data to be sorted into two independent parts through a sorting pass,

All the data in one part is smaller than all the data in the other part,

Then use this method to quickly sort the two parts of data separately,

The entire sorting process can be carried out recursively, so that the entire data becomes an ordered sequence.

Code implementation: (recursive)

/**
 * 
 */
package com.cherish.SortingAlgorithm;

/**
 * @author acer
 *
 */
public class Chapter_6_QuickSorting extends ArrayBase{

   /**
     * 
     */
    public Chapter_6_QuickSorting() {
       //TODO automatically generated constructor stub
    }

   /**
     * @param args
     */
    public static void main(String[] args) {
       //TODO automatically generated method stub
        int[] array = new int[] {3,4,7,9,2,5,1,8,6};
        quickSorting(array,0,array.length-1);
        printArray(array);
    }
    
   /*
     * Split the data to be sorted into two independent parts through a sorting pass,
     * All data in one part is smaller than all data in the other part,
     * Then use this method to quickly sort the two parts of data separately,
     * The entire sorting process can be carried out recursively, so that the entire data becomes an ordered sequence.
     * */
    public static void quickSorting(int[] array,int low,int high)
    {
        if(low <high)
        {
           //Get the reference point
            int middle = getMiddle(array,low,high);
            quickSorting(array,low,middle-1);
            quickSorting(array,middle+1,high);            
        }
    }
    
   //Sort each partial array and give the array split point for the next round
    public static int getMiddle(int[] list,int low,int high)
    {
       //The first number of the array is the base element
        int temp = list[low];
        while(low<high)
        {
            while(low<high ​​&& list[high]>temp)
            {
                high--;//Find the number smaller than the benchmark from back to front
            }
           //Move the number smaller than the baseline to the low end
            list[low] = list[high];
            while(low<high ​​&& list[low] <temp)
            {
                low++;//Find the number larger than the benchmark from front to back
            }
           //Move the number larger than the benchmark to the high end
            list[high] = list[low];        
        }
        list[low] = temp;
        return low;
    }

}

Achieve results:

Reference: https://cloud.tencent.com/developer/article/1486381 Java Code Implementation of Sorting Algorithm (5)-Quick Sort-Cloud + Community-Tencent Cloud