1. 分区(partition)
快速排序是一种利用分区的思想来实现的一个不错的排序算法, 在弄懂快排之前,还得先弄清楚分区(partition)是怎么弄的。
对于给定的数组a,我们从中选择一个值作为中心点(pivot);
定义两个索引变量分别leftScan,rightScan分别指向数组a的第一个元素和最后一个元素;
定义一个while循环
leftScan从左向右扫描直到a[leftScan]>pivot;
rightScan从右向左扫描直到a[rightScan]<pivot;
如果leftScan>=rightScan,break退出循环
否则,交换a[leftScan]和a[rightScan],然后继续循环;
最后会返回leftScan最为pivot的索引。
这样一趟下来 , 就把给定的数组分成以pivot为中心的两个区,pivot左边的是小于pivot的,pivot右边的是大于pivot的。
public class ArrayParti {
private long[] a;
private int nElement;
public ArrayParti(int max) {
a = new long[max];
nElement = 0;
}
public int partition(int left,int right,long pivot){
int leftParti = left-1;
int rightParti = right+1;
while(true){
while(leftParti<right && a[++leftParti]<pivot);
while(rightParti>left && a[--rightParti]>pivot);
if(leftParti>=rightParti)break;
else
swap(leftParti,rightParti);
}
System.out.println("pivot index is:"+leftParti);
return leftParti;
}
private void swap(int one, int two) {
long temp;
temp = a[one];
a[one]=a[two];
a[two]=temp;
}
public void insert(long v){
a[nElement]=v;
nElement++;
}
public void display(){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+"\t");
}
System.out.print("\n");
}
}
2.递归实现快速排序
1)数组a中选一个element作为pivot
2)根据选定的pivot给数组分区,左边的都比pivot小,右边的都比pivot大
3)对pivot左边的数据和pivot右边的数据分别递归实现上面的步骤。
public class ArrayQuick1 {
private long[] a;
private int nElement;
public ArrayQuick1(int max) {
a = new long[max];
nElement = 0;
}
public void sort(){
quickSort(0,nElement-1);
}
private void quickSort(int left, int right) {
if(left-right>=0){
return;
}else{
long pivot = a[right];
int partition = partition(left,right,pivot);
quickSort(left,partition-1);
quickSort(partition+1,right);
}
}
private int partition(int left, int right, long pivot) {
int leftParti = left-1;
int rightParti = right;
while(true){
while(a[++leftParti]<pivot);
while(rightParti>0 && a[--rightParti]>pivot);
if(leftParti>=rightParti)break;
else
swap(leftParti,rightParti);
}
swap(leftParti,right);
return leftParti;
}
private void swap(int one, int two) {
long temp;
temp = a[one];
a[one]=a[two];
a[two]=temp;
}
public void insert(long v){
a[nElement]=v;
nElement++;
}
public void display(){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+"\t");
}
System.out.print("\n");
}
}
分享到:
相关推荐
快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中...
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例)
C# 常用经典算法,选择排序 冒泡排序 快速排序 插入排序 希尔排序
快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典...
在快速排序法(一)中,每次将最左边的元素设为轴,而之前曾经说过,快速排序法的加速在于轴的选择,在这个例子中,只将轴设定为中间的元素,依这个元素作基准进行比较,这可以增加快速排序法的效率。
递归求解(Conquer):通过递归对p..aq和aq+1..ar进行排序。 合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在ap..aq和aq+1..ar都排好序后不需要执行...因此,快速排序法是分治法的经典应用实例之一。
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...
程序中对经典的快速排序算法进行了书写,相信快速排序是大部分程序写作者的必备技能之一吧。
快速排序是一种经典的排序算法, 它的平均性能非常突出。针对快速排序在某些特殊情况下如数据已有序或重复数据较多时效率较低的问题进行了研究, 对三路快速排序进行改进, 使快速排序在特殊情况下也能保持较好的效率。...
1.先从数列中取出一个数作为基准数 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边 3.再对左右区间重复第二步,直到各区间只有一个
快速排序的改进算法,经典推荐
数据结构 经典的快速排序。C6.0调试通过。希望对大家有用。
利用python代码实现数据结构的经典算法——快速排序算法。
经典的快速排序算法。代码较少,容易读懂。
1、掌握快速排序随机算法的设计思想与方法。 2、熟练使用高级编程语言实现不同的快速排序算法。...快速排序是算法导论中的经典算法。在本实验中,给定一个长为 n 的整数数 组,要求将数组升序排序。
自己写的比较经典的快速排序算法,希望能对大家的学习起到一定的帮助
快速排序的经典算法大家给指点一下
快速排序是一个经典的快速排序方法,完整的快速排序,易懂这是根据快速排序思想,编写的精炼切易懂而完整的快速排
几种经典算法,方便大家在排序时不需花费太多时间,只需按不同的数据存储结构,稍微修改即可,主要是实用!