[数据结构与算法]Day 46

一、学习内容

? ? ? ?快速排序使用分治的思想，从待排序序列中选取一个记录的关键字为key，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字不大于key，另一部分记录的关键字不小于key，之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。学习链接：数据结构-快速排序_3166375975@的博客-CSDN博客_数据结构快速排序

快速排序过程学习链接：快速排序法（详解）_小白的博客-CSDN博客_快速排序

/**
	 *********************
	 * Quick sort recursively.
	 * 
	 * @param paraStart The start index.
	 * @param paraEnd   The end index.
	 *********************
	 */
	public void quickSortRecursive(int paraStart, int paraEnd) {
		// Nothing to sort.
		if (paraStart >= paraEnd) {
			return;
		} // Of if

		int tempPivot = data[paraEnd].key;
		DataNode tempNodeForSwap;

		int tempLeft = paraStart;
		int tempRight = paraEnd - 1;

		// Find the position for the pivot.
		// At the same time move smaller elements to the left and bigger one to the
		// right.
		while (true) {
			while ((data[tempLeft].key < tempPivot) && (tempLeft < tempRight)) {
				tempLeft++;
			} // Of while

			while ((data[tempRight].key > tempPivot) && (tempLeft < tempRight)) {
				tempRight--;
			} // Of while

			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

	/**
	 *********************
	 * Quick sort.
	 *********************
	 */
	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);
	}// Of quickSortTest

二、实现结果