In depth explanation of quicksort and Java implementation

Quicksort is widely used as an efficient sorting algorithm, and the arrays.sort method in the SUN JDK USES quicksort.
Quicksort USES the classic idea of divide and conquer:

Divide: Select a primitive X (usually the first element of an array) and divide the array into Two parts: The left half is less than or equal to X, and the right half is greater than or equal to X.
Conquer: The left and right subarrays recursively call the Divide procedure.
Combine: Quicksort is an in place sort that does not require any merging
It can be seen that the core part of quicksort is partitioning. The following is an example to explain in detail how to divide arrays (the figure is taken from introduction to algorithms).
Initialization: I'm going to pick the primitive P=2, which is the first element of the array. I =1,j= I +1=2 (array index begins with 1)
Cyclic invariants: elements between 2 and I are less than or equal to P, and elements between I +1 and j are greater than or equal to P

Cyclic process: If j goes from 2 to n, if we look at the j position, if it's greater than or equal to P, we keep going. If the value is less than P, the element in position j (which should not appear in the interval between I +1 and j) and the element in the position I +1 (which is still in the interval between I +1 and j) are swapped, and I +1 is maintained. All the way to j is equal to n, the last loop.
Note that after completing the loop, we also need to swap the element at position I with the first element of the array to meet the requirements we set first (corresponding to step I in the diagram).

Careful readers might think of a more straightforward way of partitioning, which is to take the primitive and store it in another array of the same size. If you encounter elements smaller than the primitive, store them in the left half of the array, and if you encounter elements larger than the primitive, store them in the right half of the array. This is also linear, Theta of n. But the space complexity has doubled. This is also the advantage of quicksort in place.
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201307/20130701091432562.jpg ">

public class QuickSort {
    private static void QuickSort(int[] array,int start,int end)
    {
        if(start<end)
        {
            int key=array[start];//Initializes the save primitive
            int i=start,j;//Initialize the I, j
            for(j=start+1;j<=end;j++)

                if(array[j]<key)//If the element here is less than the primitive, the element is swapped with the element at I +1 and I is added to 1. If the element is greater than or equal to the primitive, the loop continues
                {
                    int temp=array[j];
                    array[j]=array[i+1];
                    array[i+1]=temp;
                    i++;
                }

            }
            array[start]=array[i];//Swap elements and primitives at I
            array[i]=key;
            QuickSort(array, start, i-1);//Recursive calls
            QuickSort(array, i+1, end);

        }

    }
    public static void main(String[] args)
    {
        int[] array=new int[]{11,213,134,44,77,78,23,43};
        QuickSort(array, 0, array.length-1);
        for(int i=0;i<array.length;i++)
        {
            System.out.println((i+1)+"th:"+array[i]);
        }
    }
}