新手报到——奉上一篇《快速排序算法详解》 - 黑马程序员技术交流社区

/**
*
*/
package com.heimablog;
/**
* 快速排序算法详解：
* 优点：快速算法是对冒泡排序的一种改进，在所有同数量级O(n log^n)的排序方法中
* ，其平均性能最好。就平均时间而言，是目前被认为最好的内部排序方法之一。
* 基本思想：使用的是递归原理。每次递归实现小于参考值的都在左边(右边)，大于参
* 考值的都在右边(左边)。多次递归直到脚标下界>=脚标上界。
* 具体实现：1、写排序函数设定初始参考值，左边的数依次和参考值比较，如果大于
* 参考值，则记录下来；右边的值和参考值比较，如果小于参考值，也记
* 录下来，然后交换这两个值。再次循环，把小于参考值的都放在左边，
* 大于参考值的都放在右边。
* 2、对左边的再次进行递归排序，对右边的再次进行递归排序。直至所有顺
* 序正确。
* 注意事项：1、通过指针，记录异常值(在左边大于参考值的值和在右边小于参考值的
* 值)，然后第一个左边的异常值和(倒着的)第一个右边的异常值元素互
* 换。依次往中间循环实现第一次排序。
* 2、排序函数返回的值应该是参考值应该在的位置的指针。
*
* 感觉有点说多了，具体看代码，就明白了。
* @author PDH
*
*/
public class QSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
QuickSort qs=new QuickSort();
int data[]={45,5,2,89,12,89,54,3,11,64,0};
qs.data=data;
qs.sort(0, qs.data.length-1);
qs.display();
}
}
//实现快速算法的类
class QuickSort{
// 把数组定义成自己的成员变量，便于工具类的使用
public int data[];
// 此方法完成从左到参考值和从最右边到参考值的一次排序
private int partition(int sortArray[],int low,int hight){
// 定义参考值
int key=sortArray[low];
// 循环排序实现，小于参考值的在左边，大于参考值的在右边
while(low<hight){
// 检查右边小于参考值的值，存在则放到左边
while(low<hight && sortArray[hight]>=key)
hight--; //右指针--
// 如果出现参考值右边的值小于了参考值，则把右异常值赋给sortArray[low],即把右边小于参考值的值放到左边
sortArray[low]=sortArray[hight];
// 检查左边大于参考值的值，存在则放到右边
while(low<hight && sortArray[low]<=key)
low++; //左指针++
// 如果出现参考值左边的值大于参考值，则把左异常值赋给sortArray[hight]
sortArray[hight]=sortArray[low];
/*这里有人会问，这样替换不是出现了覆盖了吗，原先的值不是被覆盖掉了吗
其实不会，是由于第一次把参考值赋值给了key，也就出现一个重复值，这样每次都可以
覆盖掉这个重复值*/
}
// 一次循环完毕了，把key值赋值给low=hight的位置，也就完成了左右两边相对参考值的有序
sortArray[low]=key;
// 返回low，即下一个递归的参考值
return low;
}
// 递归循环排序方法
public void sort(int low,int hight){
if(low<hight){
int result=partition(data,low,hight);
// 递归左边
sort(low,result-1);
// 递归右边
sort(result+1,hight);
}
}
// 打印数组方法
public void display(){
System.out.print("[");
for(int i=0;i<data.length;i++){
if(i==data.length-1)
System.out.print(data[i]+"]");
else
System.out.print(data[i]+",");
}
}
}

复制代码