package sort;
import java.util.Arrays;
/**
* 快速排序<br>
* 数组分三部分:<br>
* 1、<b>中轴</b> (取数组中第一个值为中轴)。<br>
* 2、<b>S1区域</b> (小于中轴的值)<br>
* 3、<b>S2区域</b> (大于中轴的值) <br>
* S1,S2排序,递归。
*
* @author Administrator
*
*/
public class QuerySort {
public static void main(String[] args) {
int[] array = { 12, 3, 4, 5, 11, 2, 7, 8, 6, 9, 0 };
sort(array, 0, array.length);
System.out.println(Arrays.toString(array));
}
public static void sort(int[] array, int b, int e) {
/** 取中轴的位置 **/
int m = getMid(array, b, e);
if (b < m) { // 基事件,终止条件
/** 对S1区域排序 **/
sort(array, b, m);
}
if (m + 1 < e) { // 基事件,终止条件
/** 对S2区域排序 **/
sort(array, m + 1, e);
}
}
public static int getMid(int[] array, int b, int e) {
int p = b; // 中轴索引
int s1e = b; // S1区域 末端索引
int temp = 0; // 临时空间
/** 目前结构,中轴|未知空间 **/
for (int i = b; i < e; i++) {
if (array[i] < array[p]) { // S1空间增加值, s1e++
s1e++;
temp = array[i];
array[i] = array[s1e];
array[s1e] = temp;
}
}
/** 目前结构,中轴|S1|S2 。将中轴值与S1末端互换位置,S1|中轴|S2 **/
temp = array[s1e];
array[s1e] = array[p];
array[p] = temp;
return s1e;
}
}
分享到:
相关推荐
编写程序实现归并排序算法 MergeSortL 和快速排序算法 QuickSort;
北大POJ2299-Ultra-QuickSort 解题报告+AC代码
资源名:quicksort_matlab_快速排序 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定经验的...
适用于大学数据结构的QuickSort实验提交
QuickSort快速排序的实现 [Qsort类] 使用C++模版,可实现自定义类型的排序方式 同时通过折半查找检索元素 附带控制台演示 欢迎指正和建议 程序详细描述可见:...
把非随机化的快排卡到平方级.A Killer Adversary for Quicksort. M. D. MCILROY
QuickSort java最快的排序 比冒泡快得不止一点 更nb 八大排序之一
代码中包含了快速排序这个经典算法的代码,并且给出了改进后的快速排序的代码,代码中同时包含了两个测试用例。测试命令:g++ quicksort.cpp -o quicksort ./quicksork
quicksort en c de la forma mas resumida posible
void quicksort(int A[],int p,int r) { int q; if(p) { q=partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } } /****************************************************/
然后定义了quickSort函数来实现快速排序算法。在main函数中,我们定义了一个数组并对其进行快速排序,并打印排序后的结果。 快速排序是一种高效的排序算法,它的实现相对简单但性能优秀。希望这个示例能帮助你理解...
可以快速排序,高效,资源类型,数据结构。。。。。。。。。
日本程序员norahiko,写了一个排序算法的动画演示,非常有趣...目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的
快速排序源代码,采用C++编写,经测试未发现BUG,供大家参考
JDK7的时候内置 的排序算法已经由经典快排变成了Dual-Pivot排序算法。那么Dual-Pivot到底是何方圣神,能 比我们学过的经典快排还要快呢?
一个ruby写的简单快速排序程序,一个快排搞定各种类型数据排序,默认的是随机生成随机长度的数组,输出排序后的结果。去掉注释符号“#”,并把随机函数注释掉也可以手动输入数组(注意ruby读取数据是按换行符,手动...
快速排序算法java实现,此程序所排序数组在程序中给出,没有输入。
在VS 2008中,用C语言写的快速排序算法。不用多余的数组,直接对原数组进行排序(in place)。同时在递归调用中,对于【数组组就是数组首地址】的理解会更加通透。
非递归方式的快速排序,使用堆栈和队列方式进行快速排序,有效降低程序的空间复杂度和时间复杂度。排序传入参数可以为float形式,是普通快速排序的升级版。
quicksort 快速排序伪代码(非随机) 下面的过程实现快速排序: QUICKSORT(A,p,r) 1 if p 2 then q ←PARTITION(A,p,r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A,q+1,r) 为排序一个完整的数组...