/*** * 快速排序简单实现 * * @author bobo * */ public class QuickSort { public static void main(String[] args) { /** * 快速排序的逻辑是:在所有元素中取一个标尺(一般是第一个)将待排序序列分成两组 一组的元素 都小于这个标尺,另一组都大于或等于这个标尺 * 然后对每个部分再进行递归调用,直到全部完成 */ int[] a = { 9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9}; show(a); quickSort(a, 0, a.length - 1); show(a); } /*** * 快速排序的核心方法 * * @param a * 待排序的序列 * @param begin * 待排序列子序列起始位置索引 * @param end * 待排序列子序列结束位置索引 */ private static void quickSort(int[] a, int begin, int end) { System.out.println(begin + ">" + end); // 若没有必要进行排序则返回 if (end - begin <= 1) { return; } // 定义此次排序的标尺元素 此处选择开始位置为标尺元素 不要些a[0] 因为要多次递归调用 int x = a[begin]; // 定义左右的指针 int p1 = begin;// 左指针 int p2 = end;// 右指针 // 定义比较方向 true表示向右 false表示向左 boolean dr = true; // 进行循环操作,条件是两个指针不相撞 L1: while (p1 < p2) { // 如果方向向右 if (dr) { // 从p2>p1之间进行循环查找可以进行替换的数值 for (int i = p2; i > p1; i--) { if (a[i] <= x) { a[p1] = a[i]; p1++;// 进行自增 左指针右移 dr = !dr;// 转换方向 p2 = i;// 右指针指向i continue L1; // 下一步循环 } } // 如果能执行到这一步 说明没有找到小于标尺的元素,则说明序列本身就ok 则进行如下赋值 p2 = p1; } else { // 如果方向向左 // 从p1>p2之间进行循环查找可以进行替换的数值 for (int i = p1; i < p2; i++) { if (a[i] > x) { a[p2] = a[i]; p2--;// 右指针自减 dr = !dr;// 转换方向 p1 = i; continue L1; } // 如果能执行到这一步 说明没有找到小于标尺的元素,则说明序列本身就ok 则进行如下赋值 p1 = p2; } } } // 进行递归调用 a[p1] = x;// 填充空白处 show(a, begin, end,p1); quickSort(a, begin, p1 - 1); quickSort(a, p1 + 1, end); } private static void show(int[] a, int begin, int end, int p1) { for (int i = begin; i < end + 1; i++) { if (i==p1) { System.out.print("["+a[i]+"]" + " "); }else { System.out.print(a[i]+" "); } } System.out.println(); } /** * 显示 数组元素 * * @param a */ private static void show(int[] a) { for (int i : a) { System.out.print(i + " "); } System.out.println(); } }
相关推荐
java 快速排序 折半查找的界面实现 (递归与分治法)
软件工程、快速排序法。绝顶的好东西。快速排序.Java快速排序.Java快速排序.Java
java 编写的快速排序程序递归形式我做的课堂作业,,希望能帮助大家。。。
快速排序方法...给新手一点指引,内置快速排序方法,有详细解析的链接地址,免费的
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
之前做的四种排序动画,快排比较快,所以为快排专门做一个动画
java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码
java快速排序算法和案例
java 快速排序 折半查找 的界面实现(并附有递归分治法PPT)
清楚明确的代码书写,让你轻易学懂快速排序法
用Java对整型一维数组实现快速排序,pivot值默认为数组第一个值。
JAVA快速排序法.pdf
详细解释了快速排序的java实现.里面有代码,还有注释说明
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。
基础编程:Java快速排序实例详解
两种方法: 传统的递归快速排序 采用非递归堆栈模拟
包括所有算法分析设计的实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)
快速排序是一个知名度极高的排序算法,其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。这里采用简单的小例子实现快速排序。