1. Quick sort

The idea of quick sort is based on divide and conquer . After each sorting , Will determine the position of a number , Then the left element of this number , All less than this number . And of all the elements on the right , All greater than this element , After determining the position of this element , Sort the two subsequences in the same way , This forms a recursive process . The jump out condition is that the left is greater than or equal to the right , At this time, it means that the sub sequence sorting is completed .

2. Code

/**
	 * 
	 ***********************************
	 * @Title: quickSortRecursive   
	 * @Description:  
	 * @param: @param paraStart
	 * @param: @param paraEnd      
	 * @return: void       
	 ***********************************
	 */
	public void quickSortRecursive(int paraStart, int paraEnd) {
		//null
		if(paraStart >= paraEnd)
			return;
		
		int tempPivot = data[paraEnd].key;
		DataNode tempNodeForSwap;
		
		int tempLeft = paraStart;
		int tempRight = paraEnd - 1;
		
		while(true) {
			while((data[tempLeft].key < tempPivot)&&(tempLeft <tempRight)) {
				tempLeft++;
			}//Of while
			while((data[tempRight].key >= tempPivot) && (tempLeft < tempRight)) {
				tempRight--;
			}//Of while
			
			// The conditions for recursion to jump out  
			if(tempLeft < tempRight) {
				// Swap.
				System.out.println("Swapping " + tempLeft + " and " + tempRight);
				tempNodeForSwap = data[tempLeft];
				data[tempLeft] = data[tempRight];
				data[tempRight] = tempNodeForSwap;
			}
			else {
				break;
			}//of if
		}//of while
		// Swap
				if (data[tempLeft].key > tempPivot) {
					tempNodeForSwap = data[paraEnd];
					data[paraEnd] = data[tempLeft];
					data[tempLeft] = tempNodeForSwap;
				} else {
					tempLeft++;
				} // Of if
				System.out.print("From " + paraStart + " to " + paraEnd + ": ");
				System.out.println(this);

				quickSortRecursive(paraStart, tempLeft - 1);
				quickSortRecursive(tempLeft + 1, paraEnd);
	}// Of quickSortRecursive
	
	
	public void quickSort() {
		quickSortRecursive(0, length - 1);
	}// Of quickSort

	/**
	 *********************
	 * Test the method.
	 *********************
	 */
	public static void quickSortTest() {
		int[] tempUnsortedKeys = { 1, 3, 12, 10, 5, 7, 9 };
		String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
		DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);

		System.out.println(tempDataArray);

		tempDataArray.quickSort();
		System.out.println("Result\r\n" + tempDataArray);
	}// ofquickSortTest
	/**
	 * 
	 ***********************************
	 * @Title: main
	 * @Description:
	 * @param: @param args
	 * @return: void
	 ***********************************
	 */
	public static void main(String args[]) {
		System.out.println("\r\n-------quickSortTest-------");
		quickSortTest();
	}// Of main

3. summary

Quick sorting is recursive , You need to use a recursive work stack to save the necessary information of recursive calls at each layer , In the best case O(log2n); In the worst case , Because there's going to be n-1 Recursive calls , So the depth of the stack is O(n); On average , The depth of the stack is O(log2n). The running time of quick sort is related to whether the partition is symmetrical , The worst case of fast platoon occurs when two areas contain n-1 Elements and 0 Element time , If this maximum asymmetry occurs at each level of recursion , In other words, when the initial sort table is basically in order or basically in reverse order , The worst-case time complexity is obtained . Fast sorting should be the best sorting algorithm with the best average performance among all internal sorting algorithms .