package algorithm.sort;
/**
* 快速排序:基于分治模式 分解: 划分为两个子数组(可能为空),A[left..mid-1]和A[mid+1..right]. 其中,前一个数组都小于等于A[mid],后一个数组都大于等于A[mid].mid下标在过程中划分得出。
* 解决:递归调用快速排序,对两个子数组排序 合并:因为子数组已经是排好序,所以合并不需要操作即可得到排好序的数组
*
* @author Administrator
*
*/
public class QuickSort {
//对数组指定元素进行排序
public void quickSort(int[] a, int from, int end) {
if (from < end) {
int mid = partition(a, from, end);
quickSort(a, from, mid - 1);
quickSort(a, mid + 1, end);
}
}
//整个数组排序
public void quickSort(int[] a) {
quickSort(a, 0, a.length-1);
}
//快速排序的关键过程是对partition过程,对子数组重排
public int partition(int[] a, int from, int end) {
int i = from - 1;
for (int j = from; j < end; j++) {
if (a[j] <= a[end]) { // 首先以最后一个元素作为中间分隔元素
i++;
exchange(a, i, j);
}
}
i++;
exchange(a, i, end);
return i;
}
// 交换元素
public void exchange(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// 打印数组
public void printArr(String str, int[] a) {
System.out.print(str + "\t");
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
//测试数据
public static void main(String[] args) {
QuickSort qs = new QuickSort();
int[] a = {2,5,78,56,43,9,23};
qs.printArr("原始数组为:", a);
qs.quickSort(a);
qs.printArr("快速排序后:", a);
}
}
//output~:
原始数组为: 2 5 78 56 43 9 23
快速排序后: 2 5 9 23 43 56 78
分享到:
相关推荐
快速排序 * 1.i=left,j=right,将基准数挖出形成第一个坑a[i]; * 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]; * 3.i++由前向后找比它大的数,找到后挖出此数填到前一个坑a[j]中 * 4.以i为中线,...
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
与本人博文《算法专项(1)——快速排序》相配套的工程源码,用JAVA实现
(1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
本文件讲了十种JAVA排序方法(冒泡(Bubble)排序——相邻交换 、选择排序——每次最小/大排在相应的位置 、插入排序——将下一个插入已排好的序列中 、壳(Shell)排序——缩小增量 、归并排序 、快速排序 、堆排序 ...
java代码-使用java解决快速排序的源代码 ——学习参考资料:仅用于个人学习使用!
冒泡排序实际上是将数据从右至左排序完成(从右至左、从大到小进行交换排序),而快速排序是将数据从左到右排序完成(从左至右、从小到大进行交换排序),虽然选择排序相对于冒泡排序将交换次数从O(n2)O(n^2)O(n2)...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单...快速排序的分析7.7.6 选择问题的线性期望时间算法7.8 排序算法的一般下界7.9 桶式排序7.10 外部排序7.10.1 为什么需要一些新的算法7.10.2 ...
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单...快速排序的分析7.7.6 选择问题的线性期望时间算法7.8 排序算法的一般下界7.9 桶式排序7.10 外部排序7.10.1 为什么需要一些新的算法7.10.2 ...
7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法...
9.6.1 计算最大公约数算法——搌转相除法 287 9.6.2 计算最大公约数算法一一Stein算法 288 9.6.3 计算最大公约数示例 289 9.7 最小公倍数 290 9.8 素数 292 9.8.1 素数概述 292 9.8.2 计算素数算法 292 9.9 ...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单...快速排序的分析7.7.6 选择问题的线性期望时间算法7.8 排序算法的一般下界7.9 桶式排序7.10 外部排序7.10.1 为什么需要一些新的算法7.10.2 ...
包括直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序,可以实现十个数的排序演示,有追踪数据变化的功能。 二叉树遍历 该模块实现了二叉树的三种遍历方式。用户可以对树的每一个节点输入值构造二叉树。 ...
- 快速排序 ###第八章 -不相交集 ###第九章 -邻接表(Versioni 1,2) -拓扑排序(Versioni 1,2) -单源最短路径算法 -最大网络流 -最小生成树 -深度优先搜索 -双连通性 -欧拉回路 ###第十章 -分治算法:最近点问题 -动态...
7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 7.10 外部排序 7.10.1 为什么需要一些新的算法 7.10.2 外部...