/**
*
* @author SunnyMoon
*/
////////////////////////////////////////////////////////////////////////////////
/*******************************************************************************
* 概念介绍:
* *****************************************************************************
*
* 影响效率的最大障碍:
* 对枢纽数据的选择是影响排序的效率。上一篇文章选择枢纽数据为数组的最后一个元素,
* 这么选择只是为方便,然而却造成了特殊情况时效率极度下降,降到O(n2)。这种特情况就是当数据为逆序的时候。
* 如果改变特殊情况给快速排序带来的致命影响呢,这将在这一专题中简要介绍。
*
* 三数据项取中划分:
* 目前已经有很多选择更好的枢纽的方法,选择任意一个数据项作为枢纽是一种简单的方法,便是
* 正如前文看到的那样,在特殊情况下性能很低。从理论上讲实际使数组中值数据是最理想的枢纽
* 选择,是效率最高的方式,但实际上这个过程比排序本身需要更长的时间,因此这是不可行的。
* 一种折衷的方法,选择数组里的第一个,最后一个以及中间位置的数据中选择一个中间值,并设
* 置此数据项为枢纽,这种选择枢纽的方式为三数据项选中。
* 查找三个数据项的中值数据项比查找所有数据项中值快很多,在大多数通常情况下这种方法是又
* 快又有效的方法。但是有很特殊的数据排列命名三数据项先中的方法也很低效。
*
////////////////////////////////////////////////////////////////////////////////
/**
* 定义一个数组类,封装了对自身数据的排序。
*/
class ArrayIns {
private long[] theArray;
private int nElems;
public ArrayIns(int max) {
theArray = new long[max];
nElems = 0;
}
public void insert(long value) {
theArray[nElems] = value;
nElems++;
}
public void display() {
System.out.print("A=");
for (int j = 0; j < nElems; j++) {
System.out.print(theArray[j] + " ");
}
System.out.println("");
}
/**
* 快速排序主方法
*/
public void quickSort() {
recQuickSort(0, nElems - 1);
}
/**
* 递归调用快速的排序核心方法
* @param left
* @param right
*/
public void recQuickSort(int left, int right) {
int size = right-left + 1;
if (size <= 3) {
manualSort(left, right);
} else {
long median = medianOf3(left, right);//三数取中值
int partition=partitionIt(left,right,median);//三数据取中值作为枢纽进行划分
recQuickSort(left, partition - 1);//递归排序数组左子元素
recQuickSort(partition + 1,right);//递归排序数据左子元素
}
}
/**
* 三数据选中
* @param left
* @param right
* @return
*/
public long medianOf3(int left, int right) {
int center = (left + right) / 2;
if (theArray[left] > theArray[center]) {
swap(left, center);
}
if (theArray[left] > theArray[right]) {
swap(left, right);
}
if (theArray[center] > theArray[right]) {
swap(center, right);
}
swap(center, right - 1);
return theArray[right - 1];
}
/**
* 交换数据
* @param dex1
* @param dex2
*/
public void swap(int dex1, int dex2) {
long temp = theArray[dex1];
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
/**
* 根据三数据选中进行划分
* @param left
* @param right
* @param pivot
* @return
*/
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left;//定位到最左元素
int rightPtr = right-1;//定位到枢纽
while (true) {
while (theArray[++leftPtr] < pivot);//寻找大于枢纽元素
while (theArray[--rightPtr] > pivot);//寻找小于枢纽元素
if (leftPtr >= rightPtr) {//确定划分结束退出循环
break;
} else {
swap(leftPtr, rightPtr);//交换需划分的元素
}
}
swap(leftPtr, right-1);//恢复枢纽到正确位置
return leftPtr;//返回枢纽
}
/**
* 手动排序
* @param left
* @param right
*/
public void manualSort(int left, int right) {
int size = right-left + 1;
if (size <= 1) {//当元素为1时直接返回
return;
}
if (size == 2) {
if (theArray[left] > theArray[right]) {//当元素为2时排序
swap(left, right);
}
return;
} else {//当元素为3时排序
if (theArray[left] > theArray[right - 1]) {
swap(left, right - 1);
}
if (theArray[left] > theArray[right]) {
swap(left, right);
}
if (theArray[right - 1] > theArray[right]) {
swap(right - 1, right);
}
}
}
}
/**
* 主类
*/
public class QuickSort2 {
public static void main(String[] args) {
int maxSize = 15;
ArrayIns arr = new ArrayIns(maxSize);
for (int j = 0; j < maxSize; j++) {//随机生机数据插入数组中
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
System.out.println("显示排序前数据");
arr.display();
arr.quickSort();
System.out.println("显示排序后数据");
arr.display();
}
}
/**
*运行结果:
*显示排序前数据
*A=38 62 44 89 50 91 36 60 47 22 83 7 33 31 38
*显示排序后数据
*A=7 22 31 33 36 38 38 44 47 50 60 62 83 89 91
*/
/**
* 总结:
* 快速排序是常用排序中效率最高的一种排序方式。
* 但在应用中的一此特殊情况影响他的效率,这不是算法本身的问题,而是如果实现的问题。
* 三数据项选中方法很好的解决了这样的问题。
*/
分享到:
相关推荐
JAVA数据结构与算法课程第05课双端链表和双向链表.mp4JAVA数据结构与算法课程第06课递归的应用.mp4JAVA数据结构与算法课程第07课递归的高级应用.mp4JAVA数据结构与算法课程第08课希尔排序.mp4JAVA数据结构与算法课程...
《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
数据结构和算法能起到什么作用? 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将...
堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
中文名: 数据结构与算法分析_Java语言描述(第2版)作者: 韦斯译者: 冯舜玺资源格式: PDF版本: 扫描版出版社: 机械工业出版社书号: ISBN:9787111231837发行时间: 2009年01月01日地区: 大陆语言: 简体中文简介: 内容...
适用人群:本人文档是通过Java语言来编写数据结构中排序的算法,所以要具备一定Java编程基础。以及想要复习或者自学数据结构的小伙伴。 能学到什么:1.六个基础排序算法,分别是冒泡排序,选择排序,插入排序,希尔...
总结的不错,值得一看 * 1.插入排序(直接插入排序、折半插入排序、希尔排序);...交换排序(冒泡泡排序、快速排序); * 3.选择排序(直接选择排序、堆排序); * 4.归并排序; * 5.基数排序。
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
包含各种典型内排序的java算法,包括:...冒泡排序,堆排序,插入排序,合并排序,快速排序,Shell排序(代码未完成),直接选择排序。 各种排序效率对比参见: http://blog.csdn.net/tanggod/article/details/19149007
(1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结构之链表 (6)数据结构之二叉树 (7)数据结构之霍夫曼树 (8)数据结构之红黑树(一)——基础分析 ...
LZ4压缩算法Java实现 LZ4压缩算法是一种lossless压缩算法,提供了高达500 MB/s每个核心的压缩速度,支持多核心CPU,能根据需要动态调整压缩速度,从而在压缩速度和压缩比之间取得平衡。该算法不仅具有极快的压缩...
里面囊括了Java实用算法,如冒泡排序,快速排序,递归,矩阵算法等等
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
主要介绍了java数据结构与算法之快速排序,结合实例形式详细分析了快速排序的原理、实现步骤、相关操作技巧与注意事项,需要的朋友可以参考下
本项目主要使用Java实现各种经典常用数据结构及其算法,包括但不仅限于链表、栈,队列,树,图等经典数据结构。 八大排序算法及其实现,具体包括直接插入排序,希尔排序,直接选择排序,堆排序,冒泡排序,快速排序...
常见的算法包括排序算法(如冒泡排序、快速排序)、搜索算法(如二分查找)、图算法(如最短路径算法)等。掌握这些算法的思想和实现方式,可以提高代码的效率和性能。此外,算法设计中的一些基本思想,如递归、动态规划、...