一、学习内容
快速排序使用分治的思想,从待排序序列中选取一个记录的关键字为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
二、实现结果