Quick sort is widely used as an efficient sorting algorithm. The Arrays.sort method in SUN's JDK uses quick sort.
Quick Sort adopts the classic divide and conquer idea:
Divide: Select a primitive X (usually the first element of the array), and divide the array into two parts through some partitioning operation: 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 call the Divide process recursively.
Combine: Quick sort is used as an in place sort algorithm and does not require any merge operations.
It can be seen that the core part of quick sort is the partitioning process. The following is an example to explain in detail how to partition the array (picture taken from "Introduction to Algorithms")
Initialization: Select the primitive P=2, which is the first element of the array. i=1,j=i+1=2 (array subscript starts with 1)
Loop invariant: The elements between 2~i are all less than or equal to P, and the elements between i+1~j are all greater than or equal to P.
Loop process: j goes from 2 to n, examine the element at position j, and if it is greater than or equal to P, continue the loop. If it is less than P, swap the elements at position j (which should not appear in the range i+1~j) with the elements at position i+1 (still in the range i+1~j after the exchange), and at the same time change i+1 .This maintains loop invariants (see the description of loop invariants above). Until j=n, the last loop operation is completed.
It should be noted that after completing the loop, the element at position i needs to be exchanged with the first element of the array to meet the requirements we first set (corresponding to the i-th step in the figure).
Careful readers may think of another more straightforward partitioning method, that is, taking out the primitives and storing them in another array of the same size. When encountering elements smaller than the primitives, they are stored in the left half of the array. When encountering elements larger than the primitives, they are stored in the left half of the array. The elements are stored in the right half of the array. The complexity of such operations is also linear, namely Theta(n). But the space complexity is doubled. This is also the advantage of quick sorting in place.
Copy the code code as follows:
public class QuickSort {
private static void QuickSort(int[] array,int start,int end)
{
if(start<end)
{
int key=array[start];//Initialize and save primitives
int i=start,j;//Initialize i,j
for(j=start+1;j<=end;j++)
if(array[j]<key)//If the element here is less than the primitive, exchange this element with the element at i+1, and add 1 to i. If it is greater than or equal to the primitive, continue the loop.
{
int temp=array[j];
array[j]=array[i+1];
array[i+1]=temp;
i++;
}
}
array[start]=array[i];//Exchange elements and primitives at i
array[i]=key;
QuickSort(array, start, i-1);//recursive call
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]);
}
}
}