java快速排序算法与冒泡排序算法比较
首先看下,冒泡排序算法与快速排序算法的效率:
如下的是main方法
*
* @Description:
* @author:cuiyaonan2000@163.com
* @date 2014年11月5日 下午1:02:10
*/
public static void main(String[] args) {
//快速排序算法测试
int[] qArray = new int[100000];
for (int i = 0; i < 100000; i ){
qArray[i] = (int) (Math.random() * 100000);
}
long beforeQ = System.currentTimeMillis();
quickSort(qArray, 0, qArray.length-1);
System.out.println("快速排序运行时间:" (System.currentTimeMillis() - beforeQ));
//冒泡排序算法测试
int[] bArray = new int[100000];
for (int i = 0; i < 100000; i ){
bArray[i] = (int) (Math.random() * 100000);
}
long beforeB = System.currentTimeMillis();
bubble(bArray);
System.out.println("冒泡排序运行时间:" (System.currentTimeMillis() - beforeB));
}
在一个有100000 个数字的数组中排序结果如下:
如下的是大家耳熟能详的冒泡算法:
*
* @Description:
* @author:cuiyaonan2000@163.com
* @date 2014年11月5日 下午1:00:32
*/
public static void bubble(int[] data) {
for (int i = 0; i < data.length - 1; i ) {
for (int j = i 1; j < data.length; j )
if (data[i] > data[j]) {
int temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
}
先说下关于快速排序算法的思路:
选取数组第一个数字,作为key.并设置变量i为0,j为数组长度.
从数组最后一位开始向前找,找什么呢?找比key小的数字(不能等于),并记录下坐标j.限制条件是,在向前找的过程中如果一直没找到比key小的数值,就在i<j的时候停止(如果没有找到j就做减一操作继续找).如果找到了就将数组[j]与数组[i]的值对换并结束.
从数组第一位开始向后找,找什么呢?找比key大的数字(不能等于),并记录下坐标i.限制条件是,在向前找的过程中如果一直没找到比key大的数值,就在i<j的时候停止(如果没有找到i就做加一操作继续找).如果找到了就将数组[j]与数组[i]的值对换并结束.
完成如上的操作,打印输出数组发现:数据变得相对有序了,就是在数组中key值坐标前面的都是小于key的,key值坐标后面的都是大于key值得,
所以大家明白了:将以key值为坐标的数组拆分成2个数组,分别去执行123步骤操作,最终就会产生一个有序数组
算法如下
*
* @Description:
* @author:cuiyaonan2000@163.com
* @date 2014年11月5日 下午1:02:45
*/
public static void quickSort(int[] array,int begin,int end){
int theKey = array[begin]; //设置关键值
int i = begin;
int j = end;
while(true){
while(i<j && array[j] >= theKey) //从后面找到一个比关键之小的数字坐标
j-- ;
if(i<j){ //交换
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}else{
break;
}
while(i<j && array[i] <= theKey) //从前面找到一个比关键之大的数字坐标
i ;
if(i<j){ //交换
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}else{
break;
}
}
if(--i > begin ){//这个表示一直找到 被拆分的数组中只有一个值.否则递归调用
quickSort(array,begin,i);
}
if( j< end){ //这个表示一直找到 被拆分的数组中只有一个值.否则递归调用
quickSort(array,j,end);
}
}
您可能感兴趣的文章：
php 冒泡排序的实现代码
php 实现冒泡排序的简单例子
php 数组排序方法分享(冒泡排序、选择排序)
java排序算法
php排序算法 PHP版快速排序与冒泡排序
【PHP面试】面试必问的两个简单排序算法讲解：冒泡排序和快速排序
php冒泡排序算法实现代码
javascript排序算法代码解析
PHP实现几个排序和查找算法
javascript常见排序算法实现代码