Quicksort is an example of dive-and-conquer techniques, also known as partition-swapped sort. Quicksort, which uses recursive calls to sort elements, is a well-known algorithm among comparison-based sorting algorithms and is often tested in interviews.

The main ideas of this paper are as follows:

Colloquialism classical algorithms of six series Quick sort Quick fix blog.csdn.net/morewindows…

Time complexity:

  • Time complexity: O(nlogn)
  • Space complexity: O (1)

Performance:

Let’s assume that quicksort has complexity of T(n) and all the elements are different. T(n) depends on the size of the two subproblems, which in turn depends on the central point.

  • Best case: Each partition divides the array into two equal parts. The time complexity is (nlogn);
  • Worst case: Each partition divides the array into two unequal parts. The time complexity is (n^2), and the worst case occurs when the sequence has been sorted and the last element is selected as the pivot point. If the initial sequence is ordered, it will degenerate to selection sort.
  • The time complexity in the average case is the same as in the best case, which is also (nlogn);

Basic ideas:

According to the book, the algorithm consists of the following four steps:

  1. Returns if there is only one element in the array or no element to sort.
  2. Select an element of the array as the pivot point (usually the leftmost element of the array).
  3. Divide the array into two parts, one element greater than the central point and one element less than the central point.
  4. The algorithm is called recursively on a two-part array.

Here we translate it into this idea:

Dig holes and fill numbers, divide and conquer.

The operation process is as follows:

Suppose you have the following array, and I have an array A[4,6,2,9,1,17], subscript index, two Pointers left and right, and A variable temp that holds the central point.

Left = 0; left = 0; left = 0; right = 5; temp = A[left] = 4;

Since we have stored the numbers in A[0] in Temp, we can understand that we have dug A hole in the array A[0], and we can fill it with other data.

1, first from right to left, look for the first number smaller than temp, ready to fill the position A[0]. If right=4, then A[4] is removed and filled to A[0], and left++; Left =1; Right = 4; Temp = 4; Formation of new pit A[4].

2, start from left to right, looking for the first number larger than temp, ready to fill the position A[4]. Select * from ‘A’ where ‘1’ = ‘1’; select * from ‘A’ where ‘1’ = ‘1’; Left =1; Right = 3; Temp = 4; Formation of A new crater [1];

3, start from right to left, looking for the second number smaller than temp, ready to fill the position A[1]. If right=2, then A[2] is removed and filled to A[1], and left++; Left =2; Right = 2; Temp = 4; Formation of new pit A[2].

4. When left=right, the first sorting is finished and temp is filled to the central point index=2. It can be seen that the left side of 4 is smaller than 4 and the right side is larger than 4.

5. After getting the new central point, repeat the above process recursively to the left and right sides to complete the whole sorting.

To summarize the number of pit fills (quoted from the above reference article) :

1. I = L; j = R; The datum numbers are dug out to form the first pit A [I]. 2. J — look for the number smaller than it from the back to the front, dig out the number and fill the previous hole a[I]. 3. I++ find the number larger than it from the front to the back, and then dig the number to fill the previous pit a[j]. 4. Repeat step 2,3, until I ==j, and fill the base number in a[I].

Algorithm implementation (Java) :

public static void sort(int[] A,int l,int r){ int left=l; int right=r; Int index,temp; int index,temp; if(A.length==0 || A.length==1){return; } if(left>right){return; } temp=A[left]; While (left < right && A[right] > temp){right--; } if(left < right){left A[left]=A[right]; // Select * from left where left++; While (left < right && A[left] <= temp){left++; } if(left < right){// A[right]=A[left]; // Select * from 'right' where 'right' = 'left'; A[left]=temp; b [left]=temp; c [left]=temp; // index index=left; Sort (A,l,index-1); // Sort (A,l,index-1); sort(A,index+1,r); }Copy the code

Test procedure:

Public static void main(String[] arg){// TODO auto-generated method stub int[] A=new int[]{1,4,2,8,5,9,477,25,1}; long time=System.nanoTime(); sort(A, 0, A.length-1); System.out.println(" time: "system.nanotime ()-time); for (int i : A) { System.out.println(i); }}Copy the code

The print is as follows:

1, 1, 2, 4, 5, 8, 9, 25, 477Copy the code

QQ(skirt) : 985600592