package boke.sort;
/**
* 快速排序
*
* @since jdk1.5及其以上
* @author 毛正吉
* @version 1.0
* @date 2010.05.24
*
*/
public class QuickSort {
/**
* @param args
*/
public static void main(String[] args) {
int maxSize = 10000;
QuickSort bs = new QuickSort(maxSize);
for(int i = 1; i <= 1000; i++) {
int v = (int) (Math.random()*1000);
bs.insert(v);
}
bs.output(); // 原始输出
bs.quickSort(); // 排序
bs.output(); // 排序输出
}
private long[] a; // 整型数据容器
private int nElems; // 元素个数
/**
* 构造方法
*
* @param maxSize
*/
public QuickSort(int maxSize) {
a = new long[maxSize];
nElems = 0;
}
/**
* 容器放入数据
*
* @param value
*/
public void insert(long value) {
a[nElems++] = value;
}
/**
* 输出容器数据
*/
public void output() {
for (int j = 0; j < nElems; j++) {
System.out.print(a[j] + " ");
}
System.out.println("");
}
/**
* 快速排序
*/
public void quickSort() {
recQuickSort(0, nElems - 1);
}
/**
* 快速排序
*
* @param left
* @param right
*/
private void recQuickSort(int left, int right) {
if (right - left <= 0) {
return;
} else {
long pivot = a[right]; // 最右边的元素
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition - 1); // 左段排序
recQuickSort(partition + 1, right); // 右段排序
}
}
/**
* 快速排序
*
* @param left
* @param right
* @param pivot
* @return
*/
private int partitionIt(int left, int right, long pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while (true) {
while (a[++leftPtr] < pivot) {
;
}
while (rightPtr > 0 && a[--rightPtr] > pivot) {
;
}
if (leftPtr >= rightPtr) {
break;
} else {
swap(leftPtr, rightPtr);
}
}
swap(leftPtr, right);
return leftPtr;
}
/**
* 交换
*
* @param leftPtr
* @param rightPtr
*/
private void swap(int leftPtr, int rightPtr) {
long temp = a[leftPtr];
a[leftPtr] = a[rightPtr];
a[rightPtr] = temp;
}
}
分享到:
相关推荐
文档包含以下内容: 一 插入排序 二 冒泡排序 三 选择排序 四 Shell排序 五 快速排序 六 归并排序 七 堆排序 八 桶式排序 九 基数排序
九种排序算法及其测试程序(java版)本人耗时三天整理而成,绝对精典。记忆技巧:"冒择路(入)兮(希)快归堆+桶基" 冒泡、选择、插入、希尔、快速、归并、堆、桶式、基数。
网上关于快速排序的算法原理和算法实现都比较多,不过java是实现并不多,而且部分实现很难理解,和思路有点不搭调。所以整理了这篇文章。如果有不妥之处还请建议。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
快速排序是最快的通用排序算法,它的内循环的指令很少,而且它还能利用缓存,因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN,这里的 c 比其他线性对数级别的排序算法都要小。使用三向切分快速排序,实际...
基本类型数据使用快速排序法,对象数组使用归并排序。 String,StringBuffer和StringBuilder的区别; 解答: Object的方法有哪些:比如有wait方法,为什么会有; 解答: wait和sleep的区别,必须理解!!! 解答: 强...
无论使用冒泡排序还是快速排序,排序的核心是比较两个元素的大小。如果是数字,我们可以直接比较,但如果是字符串或者两个对象呢?直接比较数学上的大小是没有意义的,因此,比较的过程必须通过函数抽象出来。通常...
根据官网和网上分享的代码自己整理了一个阿里云OSS工具类,自动创建标准公开权限的存储空间,支持上传图片,音频,视频,PDF各种文件,批量上传,上传后支持在线预览,文件路径处理,浏览器文件下载(支持源文件中文...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
关于java程序员发展需要学习的路线整理集合 技术 应用技术 计算机基础知识 cpu mem disk net 线程,进程 第三方库 poi Jsoup zxing Gson 数据结构 树 栈 链表 队列 图 操作系统 linux 代码控制...
并根据自己的理解重新进行了整理本文持续更新中本文收录于一、计算机基础1、数据结构(1)基本数据结构数据结构基本概念(时间复杂度和空间复杂度的计算方法)数组链表集合队列栈关联数组跳表倒排索引BitSet(2)树...
快速排序: 随机枢纽元快排、三路快排、三数中值快排 归并排序: 自顶向下归并、自底向上归并、链表的归并排序 堆排序: 下沉构建堆、赋值确定位置下沉 二分查找: 查找第一次后最后一次出现位置、查找大于小于给定值...
算法练级计划以面试算法过渡为线索,总结归纳面试涉及的算法知识点,整理LeetCode以及“剑指要约”出现的面试转换,在大量的LeetCode过渡中梳理一个刷题脉络,让大家能够在有限的频率,通过面试算法回归的练习,提高...
此外,还包括了常用的数据结构算法,如查找、排序和遍历等。该资源以简明易懂的方式呈现,旨在帮助读者快速掌握数据结构的基本理论和实际运用。 适用人群: 该资源适用于计算机科学、软件工程、数据科学等相关专业的...
ASP.NET2.0 快速入门 ----默认中的主题外观 数据库开发 ADO.NET 通过DataTable获得表的主键 ADO.NET 2.0 操作实例 ADO.NET 2.0 大批量数据操作和多个动态的结果集 ADO.NET 2.0 异步处理 在ASP.NET中使用WINDOWS验证...
则需要进行全表扫描, 以便将数据按照所定义的语言排序进行整理。 值范围: BINARY 或有效的语言定义名。 默认值: 从 NLS_LANGUAGE 中获得 nls_territory: 说明: 为以下各项指定命名约定, 包括日期和星期的编号, ...
重新整理所有官方支持库的静态库,有望彻底解决链接时可能出现的符号冲突 5. 全面取消静态编译中的人为功能限制(此前有最多5个支持库同时参与静态链接等功能限制) 6. 公开易语言静态编译技术文档(参见sdk\...