quicksort
Quicksort is an improvement of bubble sort algorithm. Like bubble sort, quicksort also belongs to swap sort, which is achieved by comparing elements and swapping positions. Bubble sort, in each round of the elements of a bubble to one end of the sequence, and the quick sort a benchmark element in each round of selection, and let the other move the element to the sequence, bigger than it than it moving to the other side of the sequence of elements, and disassembled into two parts, the sequence of this approach is called partition method.
2. Sorting
Sorting algorithms are designed to turn disordered combinations of data into ordered combinations of data. Orderly combination of data is the biggest advantage of when you positioning and the data will be very convenient, because the data is ordered In code design will let you avoid a lot of unnecessary trouble, because you in disorderly data extrapolating data before and after the relationship will show very complicated Quick sort is one of the sort, At worst, it’s pretty much the same sort as the others and at best, in general, it’s going to be more time efficient than the usual sort methods: bubble, hill, insert, etc
If you randomly generate tens of millions of numbers on your machine, sort them in various ways, then you can see the advantages of this thing
3, the characteristics
- Stability: Quicksort is an unstable sort. For example, if there are elements that are the same as the base value before and after the base value, the same value will be put aside, thus disrupting the previous relative order
- Comparison: Compare sort because elements need to be compared to each other
- Time complexity: The time complexity of fast sorting is O(nlogn).
- Space complexity: Additional space needs to be applied for when sorting, and it increases with the increase of the size of the sequence, and its complexity is O(nlogn).
- Merge sort and quicksort: Both merge sort and quicksort are divide-and-conquer, but they decompose and merge differently: Merge will be divided into two series, straight from the middle and fast after the row is put on the left side of the small big put on the right, so at the time of merger merge sort still needs to be two series to sort again, and the fast line is directly combined no longer need to sorting, so fast parallelism merge sort more efficient, you can compare the difference between them from the map.
- One disadvantage of quicksort is that it does not perform very well for small data sets.
Quicksort principle
Quicksort is based on the principle of “divide-and-conquer”. The so-called divide-and-conquer method is to continuously split the original array sequence according to a certain rule, and then implement sorting until the split sequence only has one keyword left. Quicksort firstly selects a keyword as a flag bit (keyword selection affects sorting efficiency), then moves the keyword smaller than the flag bit to the left, and the keyword larger than the flag bit to the right. After a comparison, the whole sequence is bounded by the selected flag bits, with the left side smaller than the flag bits and the right side larger than the keywords. But the left and right sides are not orderly (the number of keywords on the left and right sides is not necessarily the same). Then continue to sort the left and right sides respectively in this way, until the sequence split the remaining one keyword, the entire sequence is ordered.
1. First, generate ten random numbers.
Random rd = new Random();
int[] num = new int[10];
for (int i = 0; i < num.length; i++) {
num[i] = rd.nextInt(100) +1;
}
System.out.println(Arrays.toString(num));
Copy the codeThe results are as follows:
We use these ten numbers to illustrate the idea of quicksort.
We need to pick the base number, so in this case, we pick the first number as the base number, which is 15.
We use L to store the subscript of the first element and R to store the subscript of the last element, as shown:
So let’s go ahead and start with R, find the first number less than val, put it at L, L++.
We find that 8 is less than val, then the change is shown in the following figure:
And then we go back from L, find the first number greater than val, and put it at R, R- -.
We find that if 46 is greater than val, the change is shown in the figure below:
2. Then repeat these two steps until L and R are equal and we place the base numbers at their subscripts
As shown below:
In this way, we put all the numbers less than the base number to the left, and all the numbers greater than the base number to the right.
We take the numbers to the left of the base number and the numbers to the right of the base number and do all of the above steps as shown below, until one branch has only one element.
The next step is a repeat of the previous step, I will not describe
The final figure is given as follows:
4, the sorting results are: 8 15 36 46 51 55 82 86 89 96
The quicksort code is shown below for reference only:
public class testSort {
public static void main(String[] args) {
Random rd = new Random();
int[] num = new int[10];
for (int i = 0; i < num.length; i++) {
num[i] = rd.nextInt(100) +1;
}
System.out.println(Arrays.toString(num));
quickSort(num,0,num.length-1);
System.out.println(Arrays.toString(num));
}
/** * implement quicksort *@param num
* @param i
* @param j
*/
public static void quickSort(int[] num,int i,int j){
if(i >= j){// Only one element is left.
return;
}
// Select the base number
int val =num[i];
int l = i;
int r = j;
while(l < r){// When l == r, the adjustment is complete
// Find the first number less than val from the back
while (l < r && num[r] > val){
r --;
}
if(l < r){// Find the number
num[l++] = num[r];
}
// Look back for the first number greater than val
while (l < r && num[l] < val){
l ++;
}
if(l < r){// Find the numbernum[r--] = num[l]; }}//l==r
num[l] = val;
quickSort(num,i,l-1);
quickSort(num,l+1,j); }}Copy the code