package sort;
import java.util.Random;
public class QuickSort {
private int[] input;
private int partition(int[] input,int p,int r){
int x = input[r];
int i = p -1;
for(int j = p; j< r;j++){
if(input[j] <= x){
i++;
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
int temp = input[i+1];
input[i+1] = input[r];
input[r] = temp;
return i + 1;
}
public void out(){
for(int i = 0;i< input.length; i++){
System.out.print(input[i] + " ");
}
System.out.println();
}
public QuickSort(int[] input){
this.input = input;
}
public void quickSort(){
sort(input,0,input.length -1 );
}
private void sort(int[] input,int p,int r){
if(p<r){
int q = partition(input, p, r);
sort(input, p, q-1);
sort(input, q+1, r);
}
}
public int randomPartition(int[] input,int p,int r){
int i = random(p, r);
int temp = input[i];
input[i] = input[r];
input[r] = temp;
return partition(input, p, r);
}
public void randomQuickSort(){
randomQuickSort(input, 0, input.length -1);
}
private void randomQuickSort(int[] input,int p,int r){
if(p < r){
int q = randomPartition(input, p, r);
randomQuickSort(input, p, q-1);
randomQuickSort(input, q+1, r);
}
}
public static int random(int p,int r){
return new Random().nextInt(r + 1 -p) + p;
}
private int hoarePartition(int input[],int p,int r){
int x = input[p];
int i = p;
int j = r;
while(true){
while(input[j] > x){
j-- ;
}
while(input[i] < x){
i++ ;
}
if(i < j){
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
else{
return j;
}
}
}
private void hoareSort(int input[],int p,int r){
if(p < r){
int q = hoarePartition(input, p, r);
hoareSort(input, p, q -1);
hoareSort(input, q +1, r);
}
}
public void hoareSort(){
hoareSort(input, 0, input.length -1);
}
public static void main(String[] args){
int[] input = {2,8,7,1,3,5,6,4};
for(int j = 0; j < input.length;j++){
System.out.print(input[j] + " ");
}
System.out.println();
QuickSort sort = new QuickSort(input);
// sort.quickSort();
// sort.randomQuickSort();
sort.hoareSort();
sort.out();
}
}
分享到:
相关推荐
选择排序算法、冒泡排序算法和插入排序算法的时间复杂度为O(n2),写法简单,逻辑易懂,但算力性价比不高,不适用于数据量较大时使用。 合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
排序算法排序算法排序算法排序算法排序算法排序算法排序算法
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档
第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种 算法因为涉及树与堆的概念,所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是...
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
看了看好像没有二维的排序算法,自己感兴趣做了个。大家随便看看,提提意见~
C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
2、单处理机上快速排序算法 3、快速排序算法的性能 4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的...
Verilog/C++实现排序算法:Verilog/C++实现排序算法:冒泡排序、选择排序、并行全比较排序、串行全比较排序。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
陕西科技大学学校的排序算法实验,最近小咲写的: 一、实验目的 1. 熟练运用冒泡排序、选择排序、插入排序、希尔排序、快速排序、合并排序、堆排序等七种常见的内排序算法 2. 使用不同的数据结合计算各种算法的运行...
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
文档包含:排序算法:选择排序排序算法,插入排序排序算法,对半插入排序排序算法,冒泡排序排序算法,堆排序排序算法。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
内部排序算法比较 【问题描述】 在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。 ...