Quick sort summary

The content and code of the article come from 《 Comics algorithm 》 And data structure textbook . Now let's practice coding .
1. Bilateral circular law

    /** *  Bilateral circular law , Compare and exchange data from the left and right ends to the middle   Recursive implementation  */
	void quickSortV1(int[] arr, int start, int end) {
    
		//  Recursion end condition 
		if (start >= end) {
    
			return;
		}
		//  Get the benchmark element pivot Location 
		int pivotIndex = partitionV1(arr, start, end);
		//  According to the reference elements , Recursion in two parts 
		quickSortV1(arr, start, pivotIndex - 1);
		quickSortV1(arr, pivotIndex + 1, end);
	}

	/** *  A round of comparison and Exchange divide and conquer * * @param arr * @param start * @param end * @return */
	private int partitionV1(int[] arr, int start, int end) {
    
		int pivot = arr[start];
		int left = start;
		int right = end;
		while (left != right) {
    
			//  control right Pointer compare and move left 
			while (left < right && arr[right] > pivot) {
    
				right--;
			}

			//  control left Pointer compare and move left 
			while (left < right && arr[left] <= pivot) {
    
				left++;
			}
			//  In exchange for left,right Pointing elements 
			if (left < right) {
    
				int p = arr[left];
				arr[left] = arr[right];
				arr[right] = p;
			}
		}

		// pivot Exchange with pointer coincidence point 
		arr[start] = arr[left];
		arr[left] = pivot;

		return left;
	}

	@Test
	public void fun1() {
    
		// int[] arr=new int[]{4,4,6,5,3,2,8,1};
		int[] arr = new int[] {
     49, 38, 65, 97, 76, 13, 27, 49 };
		quickSortV1(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}

2. Unilateral circulation method

	/** *  Unilateral circulation method , * 1. Set up a mark The pointer , Say less than pivot The boundary of the data area  * 2. Traverse from left to right and pivot Compare , If greater than or equal to pivot, Keep going backwards  * 3. If it is less than , be mark Move back one position , And less than pivot The positions of elements are exchanged  * 4. Until the end of a round of traversal , The final will be mark Location elements and pivot Location element exchange location . * * */
	void quickSortV2(int[] arr, int start, int end) {
    
		//  Recursion end condition 
		if (start >= end) {
    
			return;
		}
		//  Get the benchmark element pivot Location 
		int pivotIndex = partitionV2(arr, start, end);
		//  According to the reference elements , Recursion in two parts 
		quickSortV2(arr, start, pivotIndex - 1);
		quickSortV2(arr, pivotIndex + 1, end);
	}

	/** *  Divide and conquer  divide and conquer * * @param arr * @param start * @param end * @return */
	private int partitionV2(int[] arr, int start, int end) {
    
		//  Take the first position element as the reference element pivot
		int pivot = arr[start];
		int mark = start;

		for (int i = start + 1; i <= end; i++) {
    
			if (arr[i] < pivot) {
    
				mark++;
				int p = arr[mark];
				arr[mark] = arr[i];
				arr[i] = p;
			}
		}

		arr[start] = arr[mark];
		arr[mark] = pivot;
		return mark;
	}

	@Test
	public void fun2() {
    
		int[] arr = new int[] {
     49, 38, 65, 97, 76, 13, 27, 49 };
		quickSortV2(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}

3. Non recursive implementation

	/** *  Non recursive implementation  ( Most recursive logic , Can be replaced by stack ) * * @param arr * @param start * @param end */
	void quickSortV3(int[] arr, int start, int end) {
    
		Stack<Map<String, Integer>> stack = new Stack<>();
		Map<String, Integer> root = new HashMap<String, Integer>();
		root.put("start", start);
		root.put("end", end);
		stack.push(root);

		//  End the loop when the stack is empty 
		while (!stack.isEmpty()) {
    
			Map<String, Integer> item = stack.pop();
			int pivotIndex = partitionV3(arr, item.get("start"), item.get("end"));

			//  It is divided into 2 part , Put the start and end of each part on the stack 
			if (item.get("start") < pivotIndex - 1) {
    
				Map<String, Integer> left = new HashMap<>();
				left.put("start", item.get("start"));
				left.put("end", pivotIndex - 1);
				stack.push(left);
			}
			if (pivotIndex + 1 < item.get("end")) {
    
				Map<String, Integer> right = new HashMap<>();
				right.put("start", pivotIndex + 1);
				right.put("end", item.get("end"));
				stack.push(right);
			}
		}

	}

	private int partitionV3(int[] arr, int start, int end) {
    
		int pivot = arr[start];
		int mark = start;
		for (int i = start + 1; i <= end; i++) {
    
			if (arr[i] < pivot) {
    
				mark++;
				int p = arr[mark];
				arr[mark] = arr[i];
				arr[i] = p;
			}
		}
		arr[start] = arr[mark];
		arr[mark] = pivot;
		return mark;
	}

	@Test
	public void fun3() {
    
		int[] arr = new int[] {
     49, 38, 65, 97, 76, 13, 27, 49 };
		quickSortV3(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}

The algorithm of data structure textbook is transformed into C Language

#include<iostream>
using namespace std;

/*  data structure (C Language version )  YanWeiMin , Wei-min wu   The quick sort algorithm is converted into code  */

int Partition(int arr[], int low, int high){
    
	int pivot = arr[low];//  The first record is pivot
	while(low<high){
    
		while(low<high && arr[high]>=pivot){
    
			--high;
		}
		arr[low]=arr[high];
		while(low<high && arr[low]<=pivot){
    
			++low;
		}
		arr[high]=arr[low];
	}
	arr[low]=pivot;
	return low;
}

void Qsort(int arr[], int low, int high){
    
	if(low < high){
    
		int pivotLoc = Partition(arr, low, high);
		Qsort(arr, low, pivotLoc-1);
		Qsort(arr, pivotLoc+1,high);
		
	}
}

int main(int argc, char* argv[]) {
    
	int arr[]={
    49,38,65,97,76,13,27,49};
	Qsort(arr,0,7);
	for(int i=0;i<8;i++){
    
		cout<<arr[i]<<",";
	}
	
	return 0;
}

The division and treatment process is shown in the following figure ：

summary ： The average time complexity of quicksort is O(nlogn). There is a slight difference between the fast sorting algorithm of cartoon algorithm and that of data structure textbook , Mainly reflected in the way of data element exchange . For benchmark data pivot The choice of , The first element of the array is selected by default in the code , But if the initial record sequence is ordered by keywords or basically ordered , Fast sorting will degenerate into bubble sorting , Its time complexity is O(n²), For improvement , The pivot record is usually selected according to the rule of choosing the middle of the three pivot, That is, compare the first , the last one , The size of the middle element , Take the middle as pivot; The comic algorithm also mentions the random selection of an element as the benchmark element pivot, However, there is still a very small chance to choose the maximum or minimum value of the sequence , Affect the effect of partition .
In fact, after every round of data exchange , return pivot The current position , according to pivot Position divides an array into 2 Subarray , Continue to recursively process the subarray , Until the length of the subarray becomes 1.