Java:快速排序算法与冒泡算法
首先看下,冒泡排序算法与快速排序算法的效率:
/**
*
* @Description:
* @author:cuiyaonan2000@163.com
* @date 2014年11月5日 下午1:00:32
*/
public static void main(String[] args) {
//快速排序算法测试
int[] qArray = newint[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 = newint[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:00:32
*/
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);
}
}
相关推荐
JAVA冒泡排序和快速排序算法,符合实验报告要求哦
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
java算法,快速排序、冒泡排序、选择排序 快速排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51822361 冒泡排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51819045
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
使用java实现的4种排序算法(冒泡、快速、插入、选择),采用随机生成一个数组,然后进行排序。
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
idea项目:一个主类选择调用6个排序类,记录了学习排序算法的过程,可以自己更改优化,每一种排序是一个类,有需要可以copy走,可重用性强
快速排序
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
直接插入排序,希尔排序,简单选择排序,堆排序,冒泡排序,快速排序,归并排序,基数排序
该工具包含有Java一些比较常见的排序算法和...排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契(黄金分割法)、
java实现插入排序,交换排序。插入排序包括直接插入排序,折半插入排序和希尔排序。交换排序包括冒泡排序。
Java的算法 排序算法 冒泡排序 堆排序 插入排序 合并排序 快速排序 选择排序 希尔排序
Java中常见的排序算法有以下几种: 冒泡排序(Bubble Sort):通过比较相邻元素的大小,将较大的元素逐渐向后移动,直到整个序列有序。 选择排序(Selection Sort):每次遍历数组,找到最小(或最大)的元素,将其...
Java数据挖掘18大算法实现和10大常见排序算法以及其他相关经典DM算法集合。...稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
java语言实现排序算法:包括冒泡排序、选择排序、快速排序、插入排序。
各类排序算法java的实现,as 插入排序:冒泡排序:选择排序:Shell排序:快速排序:改进后的快速排序:归并排序:改进后的归并排序: 堆排序:SortUtil
java写的基于比较的各种排序算法,都是一个一个的小函数。简单排序包括:选择排序,插入排序,折半插入排序,冒泡排序。 分治思想的排序包括:归并排序,快速排序,堆排序。 程序把随机生成的整数进行排序,开始时用...