冒泡排序、选择排序和快速排序:
package com.fatedgar.other;
public class Sort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = { 12, 23, 435, 6, 2, 4, 543, 226, 595};
long startB=System.currentTimeMillis();
BubbleSort(a);
long endB=System.currentTimeMillis();
System.out.println("");
long startC=System.currentTimeMillis();
ChoiceSort(a);
long endC=System.currentTimeMillis();
System.out.println("");
long startQ=System.currentTimeMillis();
quick(a);
long endQ=System.currentTimeMillis();
System.out.println("");
//如果把上面的int[] a的内容复制个很多遍后,测试发现选择排序时间最快,冒泡排序第二,花时间最长的是快速排序
System.out.println("冒泡排序花的时间"+(endB-startB));//109
System.out.println("选择排序花的时间"+(endC-startC));//94
System.out.println("快速排序花的时间"+(endQ-startQ));
}
/**
* 冒泡排序
* 冒泡排序是一种简单的交换类排序。其基本思路是,从头开始扫描待排序的元素,
* 在扫描过程中依次对相邻元素进行比较,将关键字值大的元素后移。每经过一趟排序后,
* 关键字值最大的元素将移到末尾,此时记下该元素的位置,下一趟排序只需要比较到此位置为止,
* 直到所有元素都已有序排列。一般地,对n个元素进行冒泡排序,总共需要进行n-1趟。第1趟需要比较n-1次,
* 第2趟需要比较n-2次,......第i趟需要比较n-i次。
*
* 冒泡排序算法的运作如下:
* 1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
* 2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
* 3. 针对所有的元素重复以上的步骤,除了最后一个。
* 4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
*
* @param list
*/
public static void BubbleSort(int[] list){
int temp;
for(int i=0;i<list.length;i++){//趟数[n-1]
for(int j=0;j<list.length-i;j++){//次数
try {
if(list[j]>list[j+1]){
temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
}
} catch (ArrayIndexOutOfBoundsException e) {
// TODO: handle exception
}
}
}
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
/**
* 选择排序
* 选择排序是只有在确定了最小的数据之后,才会发生交换。
* 第i趟简单选择排序是指通过n-i次关键字的比较,
* 从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换。
* 先临时记录其位置,只有在一趟循环完以后确定了最小的数据,才会发生交换。
* @param list
*/
public static void ChoiceSort(int[] list){
for(int i=0;i<list.length;i++){
int min =i;//将当前下标定义为最小值下标
for(int j=i+1;j<list.length;j++){
if(list[min]>list[j]){//如果有小于当前最小值的关键字
min=j;//将此关键字的下标赋值给min
}
}
if(min!=i){//若min不等于i,说明找到最小值,交换
int temp=list[min];
list[min]=list[i];
list[i]=temp;
}
}
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
/**
* 快速排序是对冒泡排序的一种改进。
* 它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,
* 其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,
* 整个排序过程可以递归进行,以此达到整个数据变成有序序列。
* 三个指针: 第一个指针称为pivotkey指针(枢轴),
* 第二个指针和第三个指针分别为left指针和right指针,
* 分别指向最左边的值和最右边的值。left指针和right指针从两边同时向中间逼近,
* 在逼近的过程中不停的与枢轴比较,将比枢轴小的元素移到低端,将比枢轴大的元素移到高端,
* 枢轴选定后永远不变,最终在中间,前小后大。
* 最坏情况的时间复杂度为O(n2),最好情况时间复杂度为O(nlog2n)。
* @param list
* @param left
* @param right
*/
public static void quick(int[] list) {
if (list.length > 0) { //查看数组是否为空
QuickSort(list, 0, list.length - 1);
}
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
public static void QuickSort(int [] list,int left,int right){
if(left<right){
int low=left;
int high=right;
int temp=list[left];
while(low<high){
while (low<high && list[high]>temp){
high--;
}
list[low]=list[high];
while(low<high && list[low]<temp){
low++;
}
list[high]=list[low];
}
list[low]=temp;
QuickSort(list,left,low-1);
QuickSort(list,low+1,right);
}
}
}
分享到:
相关推荐
JAVA排序汇总JAVA排序汇总JAVA排序汇总
java排序算法使用及场景说明 文档后面有一些别人的链接,多在google上搜索Java排序算法,及维基百科上面也有很全的算法介绍。
java排序.txt
java排序 java 排序 排序大全 算法 java算法
JAVA排序汇总,java应用中一些比较经典的排序算法
java排序大全(含各种常用得排序算法),学习排序不错得资料
java排序算法大全 为了便于管理,先引入个基础类: 一 插入排序 二 冒泡排序 三,选择排序 四 Shell排序 五 快速排序 六 归并排序 等等
java排序,简单介绍了java的主要有那些排序方法。
Java排序算法代码.
java排序Comparator和Comparable
Java 中的一些重要排序,比如冒泡,直接插入排序
Java排序方法详解大全 Java排序 快速排序 冒泡排序
java实现的常用的几种基本排序算法,插入、交换、选择、归并
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
执行语句:java sort <输入方式> <图形界面/非图形界面选择> <待排序数列> 例: java sort 0 643 323 12 3 523 23 //命令行输入数据并排序 java sort 1 1 //非图形界面下手动输入数据并排序 java sort 1 2 //手动...
java排序方法 java排序方法 java排序方法 java排序方法
Java排序算法实现 Java排序算法实现 Java排序算法实现
java 排序方法 面试的时候会碰到 下载学习吧