/**
* 快速排序
* <p>1、划分思想</p>
* <p>2、递归</p>
* @author WangYanCheng
* @version 2014-4-29
*/
public class QuickSort {
private int[] dataArr;
public QuickSort(int[] dataArr) {
this.dataArr = dataArr;
}
public void doSort() {
innerSort(0, dataArr.length - 1);
}
/**
* 排序
* <p>递归调用</p>
* @param left
* @param right
*/
private void innerSort(int left, int right) {
if (right - left <=0) {
return;
} else {
int pivot = dataArr[right];//取最右端值做为枢纽
System.out.println("划分:left:" + left + ",right:" + right + ",pivot:" + pivot);
int partition = partitionIt(left, right, pivot);//划分
System.out.println("左区域排序:left:" + left + ",right:" + (partition - 1));
innerSort(left, partition - 1);//左边区域排序
System.out.println("右区域排序:left:" + (partition + 1) + ",right:" + right );
innerSort(partition + 1, right);//右边区域排序
}
}
/**
* 划分
* @param left
* @param right
* @param pivot 枢纽
* @return
*/
private int partitionIt(int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while (true) {
while (dataArr[++leftPtr] < pivot) {
;
}
while (rightPtr > 0 && dataArr[--rightPtr] > pivot) {
;
}
if (leftPtr >= rightPtr) {
break;
} else {
swap(leftPtr, rightPtr);
}
}
swap(leftPtr, right);
doPrint();
return leftPtr;
}
/**
* 交换
* @param leftPtr
* @param rightPtr
*/
private void swap(int leftPtr, int rightPtr) {
int tmpValue = dataArr[leftPtr];
dataArr[leftPtr] = dataArr[rightPtr];
dataArr[rightPtr] = tmpValue;
}
/**
* 打印当前数组元素
*/
public void doPrint() {
System.out.println(java.util.Arrays.toString(dataArr));
}
/**
* 测试入口
* @param args 参数列表
*/
public static void main(String[] args) {
int[] dataArr = new int[10];
for (int i = 0; i < dataArr.length; i++) {
dataArr[i] = (int) (Math.random() * 100);
}
dataArr = new int[]{2, 61, 27, 21, 4, 1, 74, 40, 90, 33};
QuickSort qsInst = new QuickSort(dataArr);
qsInst.doPrint();
qsInst.doSort();
qsInst.doPrint();
}
}
输出:
[2, 61, 27, 21, 4, 1, 74, 40, 90, 33]
划分:left:0,right:9,pivot:33
[2, 1, 27, 21, 4, 33, 74, 40, 90, 61]
左区域排序:left:0,right:4
划分:left:0,right:4,pivot:4
[2, 1, 4, 21, 27, 33, 74, 40, 90, 61]
左区域排序:left:0,right:1
划分:left:0,right:1,pivot:1
[1, 2, 4, 21, 27, 33, 74, 40, 90, 61]
左区域排序:left:0,right:-1
右区域排序:left:1,right:1
右区域排序:left:3,right:4
划分:left:3,right:4,pivot:27
[1, 2, 4, 21, 27, 33, 74, 40, 90, 61]
左区域排序:left:3,right:3
右区域排序:left:5,right:4
右区域排序:left:6,right:9
划分:left:6,right:9,pivot:61
[1, 2, 4, 21, 27, 33, 40, 61, 90, 74]
左区域排序:left:6,right:6
右区域排序:left:8,right:9
划分:left:8,right:9,pivot:74
[1, 2, 4, 21, 27, 33, 40, 61, 74, 90]
左区域排序:left:8,right:7
右区域排序:left:9,right:9
[1, 2, 4, 21, 27, 33, 40, 61, 74, 90]
分享到:
相关推荐
数据结构_C语言_严蔚敏 吴伟民版_排序 课程源程序
C算法_基础_数据结构_排序和搜索
数据结构_讲义_,是一个关于数据结构的代码。
21%-数据结构_排序算法.doc
插入排序、交换排序、选择排序、归并排序、基数排序 各种内排序方法的比较和选择
严蔚敏版《数据结构》中的第八章中的 快速排序,有完整的程序
数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序
一、实验目的 (1)理解动态查找表的动态生成过程; (2)任意给出一组数(不...(1)定义二叉排序树的数据结构; (2)实现二叉排序树的插入算法与查找算法,并建立二叉排序树; (3)进行数据查找和建树过程的比较。
Java SE完整版精品优质课件 自学入门必看的优秀Java基础知识培训教案 数据结构_排序算法(共144页).rar
数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序
c语言版本的数据结构的快速排序算法,适用于新手学习
数据结构冒泡排序算法 数据结构冒泡排序算法
计算机数据结构PPT,数据结构线性表栈和队列数组广义表排序
这本书是用java讲数据结构和排序算法的,全书只有44页,但是讲的内容很不错,推荐学习或者复习数据结构的童鞋下在看看!
一个小型信息(可以是图书、人事、学生、物资、商品等任何信息)管理系统。实现插入、查找、删除、计数、排序、输出等功能。并能在屏幕上输出相应的结果。以把所学数据结构知识应用到实际软件开发中去。
数据结构课程设计_排序算法演示系统.doc
1、选择合适的算法和数据结构__ 4 2、使用尽量小的数据类型__ 5 3、减少运算的强度__ 5 (1)、查表(游戏程序员必修课)_ 5 (2)、求余运算__ 6 (3)、平方运算__ 6 (4)、用移位实现乘除法运算__ 6 ...
格式工厂PDF合并 00_课程介绍+01_数据结构和+02_算法分析+03_排序+04_线性表+0.pdf
排序方法是数据处理的最基本和最重要的操作。其目的是将一组“无序”的 记录序列调整为“有序”的记录序列。 实验题目:排序方法的实现与实验比较 实验内容: 实现一组经典的排序算法,通过实验数据的设计,考察...