说明
闵老师的文章链接： 日撸 Java 三百行（总述）_minfanphd的博客-CSDN博客
自己也把手敲的代码放在了github上维护：https://github.com/fulisha-ok/sampledata
day46 快速排序
1.基本思路
快速排序需要一个基准值，在这个基准值右边的数都比这个基准值大，左边的数都比这个基准值小。一趟排序就可以确定一个数的最终位置
大致步骤如下：
- 选择基准值，一般选择数组第一个元素或者最后一个。
- 从右往左扫描数组，如果找到一个比基准值小的元素，则停止。
- 从左往右扫描数组，如果找到一个比基准值大的元素，则停止。
- 交换位置
- 重复上面的步骤 直到low和high相遇，这是low和high所在位置就是基准元素的最后位置
递归地对左半部分和右半部分进行快速排序（以下是根据代码思想模拟的一次快速排序结果）
2. 代码
- 快速排序，会在左右两边各设置一个指针low和hight，代码中基准值找的是最右边的数据，当tempLeft遇到比基准值小的就++，否则就会停下来；tempRight遇到比基准值大的就–，否则就会停下；然后交换位置；直到tempLeft和tempRight相遇
- 每一趟排序后就会有基准值的左右两边，对左右两边又进行同样的快速排序操作操作，所以这个是有递归思想在里面的，用递归算法解决。
/**
* Quick sort recursively.
* @param paraStart The start index.
* @param paraEnd The end index
*/
public void quickSortRecursive(int paraStart, int paraEnd) {
if (paraStart >= paraEnd) {
return;
}
int tempPivot = data[paraEnd].key;
DataNode tempNodeForSwap;
int tempLeft = paraStart;
int tempRight = paraEnd;
//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++;
}
while ((data[tempRight].key) > tempPivot && tempLeft < tempRight) {
tempRight--;
}
if (tempLeft < tempRight) {
//swap
System.out.println("Swapping " + tempLeft + " and " + tempRight);
tempNodeForSwap = data[tempLeft];
data[tempLeft] = data[tempRight];
data[tempRight] = tempNodeForSwap;
}else {
break;
}
System.out.print("From " + paraStart + " to " + paraEnd + ": ");
System.out.println(this);
quickSortRecursive(paraStart, tempLeft - 1);
quickSortRecursive(tempLeft + 1, paraEnd);
}
}
public void quickSort() {
quickSortRecursive(0, length-1);
}
/**
* 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);
}
文章来源：https://www.toymoban.com/news/detail-437953.html
对比昨天学习的冒泡排序，冒泡排序是从一边开始，并且交换的是相邻两个元素，他也会确定一个最终位置，但是这个最终位置是从下到上依次确定（或从上到下），而快速排序，他也是交换数据，但是他是两边同时开始比较，每次也会确定一个数的最终位置，但是这个位置并不是有规律的，需要结合排序的数据来看，相比冒泡，快速排序的基准值要选好才是关键。文章来源地址https://www.toymoban.com/news/detail-437953.html
到了这里，关于日撸 Java 三百行day46的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
