先推荐一篇关于排序算法的文章：http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html
本文思路部分来源于上篇文章，但测得的结果似乎不大相同，不知是因为java的缘故还是因为我算法的缘故，欢迎拍砖。
复习排序，顺便比下各种算法的速度，榜单如下：
1、冒泡排序
2、简单选择排序
3、直接插入排序
4、折半插入排序
5、希尔排序
6、堆排序
7、归并排序
8、快速排序
当然这是慢速排行，哈哈~~
直接上图：单位毫秒
|
数量
|
冒泡排序
|
简单选择排序
|
直接插入排序
|
折半插入排序
|
希尔排序
|
堆排序
|
归并排序
|
快速排序
|
|
10000个
|
1578
|
1250
|
672
|
250
|
0
|
15
|
16
|
0
|
|
15000个
|
3453
|
2765
|
1563
|
531
|
16
|
15
|
16
|
0
|
|
20000个
|
6140
|
4547
|
2453
|
828
|
16
|
16
|
15
|
16
|
|
25000个
|
10079
|
7171
|
3969
|
1313
|
31
|
16
|
15
|
16
|
|
30000个
|
14641
|
10313
|
5578
|
1906
|
31
|
31
|
16
|
31
|
|
35000个
|
20141
|
14328
|
7890
|
2563
|
31
|
31
|
32
|
15
|
|
40000个
|
25766
|
18359
|
10094
|
3422
|
47
|
31
|
31
|
32
|
|
45000个
|
32469
|
24063
|
13062
|
4359
|
47
|
47
|
31
|
47
|
由于"希尔排序","堆排序","归并排序","快速排序"太快，以至于在上图几乎是条直线，故有了下面转为他们准备的加强版
|
数量
|
希尔排序
|
堆排序
|
归并排序
|
快速排序
|
|
100000个
|
172
|
140
|
110
|
93
|
|
200000个
|
469
|
406
|
235
|
234
|
|
300000个
|
812
|
703
|
422
|
375
|
|
400000个
|
1125
|
1031
|
516
|
531
|
|
500000个
|
1406
|
1282
|
719
|
656
|
|
600000个
|
1828
|
1703
|
860
|
859
|
|
700000个
|
2531
|
2063
|
1000
|
968
|
|
800000个
|
2735
|
2453
|
1140
|
1188
|
|
900000个
|
3047
|
2843
|
1391
|
1266
|
|
1000000个
|
3375
|
3187
|
1516
|
1422
|
|
1100000个
|
3922
|
3500
|
1625
|
1609
|
|
1200000个
|
4421
|
3954
|
1969
|
1812
|
|
1300000个
|
4797
|
4422
|
2000
|
1953
|
|
1400000个
|
5391
|
4797
|
2547
|
2094
|
|
1500000个
|
5437
|
5219
|
2625
|
2328
|
|
1600000个
|
6203
|
5546
|
2469
|
2485
|
|
1700000个
|
6532
|
5953
|
2844
|
2672
|
|
1800000个
|
7125
|
6421
|
2984
|
2844
|
补上代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 插入排序:直接插入排序、折半插入排序和系尔排序
* 交换排序:冒泡排序和快速排序
* 选择排序:简单选择排序和堆排序
* 归并排序:归并排序
*
* 基本思想
* 插入排序:将第N个记录插入到前面(N-1)个有序的记录当中。
* 交换排序:按照某种顺序比较两个记录的关键字大小，然后根据需要交换两个记录的位置。
* 选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录，放到适当的位置。
*
* 排序方法比较
* 排序方法 平均时间 最坏时间 辅助存储
* 直接插入排序 O(N2) O(N2) O(1)
* 起泡排序 O(N2) O(N2) O(1)
* 快速排序 O(Nlog2N) O(N2) O(Nlog2N)
* 简单选择排序 O(N2) O(N2) O(1)
* 堆排序 O(Nlog2N) O(Nlog2N) O(1)
* 归并排序 O(Nlog2N) O(Nlog2N) O(n)
* 基数排序 O(d(n+radix)) O(d(n+radix)) O(radix)
*
*
*
* @author Administrator
*
*/
public class SortTest {
public static void main(String[] args)throws Exception {
//测试排序是否正确
//String[] testErr=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","系尔排序","堆排序","归并排序","快速排序"};
//new SortTest().testErr(testErr);
//排序1（全部）
String[] strs=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","希尔排序","堆排序","归并排序","快速排序"};
new SortTest().test(strs,10000,50000,5000);
//排序2（加强）
String[] strs2=new String[]{"希尔排序","堆排序","归并排序","快速排序"};
new SortTest().test(strs2,100000,1900000,100000);
}
private void testErr(String[] strings) throws Exception{
//System.out.println(Arrays.toString(old));
System.out.println(Arrays.toString(strings));
Number[] old=getRundom(50);
Integer[] oo={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21};
old=oo;
for(String s:strings){
Number[] testNum=Arrays.copyOf(old, old.length);
long begin=System.currentTimeMillis();
SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);
long end=System.currentTimeMillis();
System.out.println(s+":"+(end-begin)+"\t");
System.out.println(Arrays.toString(testNum));
}
System.out.println();
}
private void test(String[] strings,long begin,long end,long step) throws Exception{
System.out.print("数量\t");
for(String str:strings){
System.out.print(str+"\t");
}
System.out.println();
for(long i=begin;i<end;i=i+step){
System.out.print(i+"个\t");
Number[] old=getRundom(i);
for(String s:strings){
Number[] testNum=Arrays.copyOf(old, old.length);
long beginTime=System.currentTimeMillis();
SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);
long endTime=System.currentTimeMillis();
System.out.print((endTime-beginTime)+"\t");
//System.out.println(Arrays.toString(testNum));
}
System.out.println();
}
}
private static Integer[] getRundom(long num) {
List<Integer> list=new ArrayList<Integer>();
for(long i=0;i<num;i++){
int k;
if(Math.random()>0.5){
k=(int)(Math.random()*Integer.MAX_VALUE);
}else{
k=(int)(Math.random()*Integer.MIN_VALUE);
}
list.add(k);
}
return list.toArray(new Integer[list.size()]);
}
/**
* 插入排序————直接插入排序
* @param data
*/
public static void 直接插入排序(Number[] data)
{
Number tmp=null ;
for(int i=1;i<data.length;i++){
tmp = data[i];
int j=i-1;
while(j>=0 && tmp.doubleValue()<data[j].doubleValue()){
data[j+1]=data[j];
j--;
}
data[j+1]=tmp;
}
}
/**
* 插入排序————折半插入排序
* @param data
*/
public static void 折半插入排序(Number[] data)
{
Number tmp=null ;
for(int i=1;i<data.length;i++){
tmp = data[i];
int smallpoint=0;
int bigpoint=i-1;
while(bigpoint>=smallpoint){
int mid=(smallpoint+bigpoint)/2;
if(tmp.doubleValue()>data[mid].doubleValue()){
smallpoint=mid+1;
}else{
bigpoint=mid-1;
}
}
for(int j=i;j>smallpoint;j--){
data[j]=data[j-1];
}
data[bigpoint+1]=tmp;
}
}
/**
* 插入排序————希尔排序
* @param data
*/
public static void 希尔排序(Number[] data)
{
int span=data.length/7;
if(span==0)span=1;
while(span>=1){
for(int i=0;i<span;i++){
for(int j=i;j<data.length;j=j+span){
//组内直接插入排序
int p = j-span;
Number temp = data[j];
while( p >=0 && data[p].doubleValue() > temp.doubleValue()){
data[p+span] = data[p];
p -=span;
}
data[p + span] = temp;
}
}
span=span/2;
}
}
/**
* 交换排序————冒泡排序
*
* @param data
*/
public static void 冒泡排序(Number[] data)
{
for (int i = 0; i < data.length; i++) {
//将相邻两个数进行比较，较大的数往后冒泡
for (int j = 0; j < data.length - i-1; j++) {
if (data[j].doubleValue()> data[j + 1].doubleValue()) {
//交换相邻两个数
swap(data, j, j + 1);
}
}
}
}
/**
* 交换排序————快速排序
* @param data
*/
public static void 快速排序(Number[] data)
{
QuickSort(data,0,data.length-1);
}
private static void QuickSort(Number[] data, int begin, int end) {
// System.out.println(begin+":"+end);
if(begin<end){
//取中点
int mid=(begin+end)/2;
if(data[end].doubleValue()<data[begin].doubleValue()){
swap(data, end, begin);
}
if(data[end].doubleValue()<data[mid].doubleValue()){
swap(data, end, mid);
}
if(data[mid].doubleValue()<data[begin].doubleValue()){
swap(data, mid, begin);
}
swap(data, mid, begin);
// System.out.println(Arrays.toString(Arrays.copyOfRange(data, begin, end)) );
int min=begin+1;
int big=end;
while(true){
while(min<big && data[min].doubleValue()<data[begin].doubleValue()){min++;}
while(min<big && data[big].doubleValue()>=data[begin].doubleValue()){big--;}
if(min>=big){
break;
}
swap(data, min, big);
}
if(data[begin].doubleValue()>data[min].doubleValue()){
swap(data, begin, min);
}
if(min>1)
QuickSort(data,begin,min-1);
//if(min<end)
QuickSort(data,min,end);
}
}
/**
* 选择排序————简单选择排序
* @param data
*/
public static void 简单选择排序(Number[] data)
{
for (int i = 0; i < data.length-1; i++) {
int smallPoint=i;
for (int j = i+1; j < data.length; j++) {
if (data[smallPoint].doubleValue()> data[j].doubleValue()) {
smallPoint=j;
}
}
swap(data, i, smallPoint);
}
}
/**
* 选择排序————堆排序
* @param data
*/
public static void 堆排序(Number[] data)
{
int n = data.length;
for(int i=n/2;i>=0;i--){
keepHeap(data, n, i);
}
while (n > 0) {
swap(data, 0, n-1);
keepHeap(data, --n, 0);
}
}
private static void keepHeap(Number[] a, int n, int i) {
Number x = a[i];
int j = 2 * i + 1;
while (j <= n - 1) {
if (j < n - 1 && a[j].doubleValue() < a[j + 1].doubleValue())
++j;
if (a[j].doubleValue() > x.doubleValue()) {
a[i] = a[j];
i = j;
j = 2 * i ;
} else{
break;
}
}
a[i] = x;
}
/**
* 归并排序法————归并排序
* @param data
*/
public static void 归并排序(Number[] data)
{
Number[] result = merge_sort(data,0,data.length-1);
for(int i=0;i<result.length;i++){
data[i]=result[i];
}
}
private static Number[] merge_sort(Number[] array, int start, int end){
Number[] result = new Number[end-start+1];
if(start< end){
int mid= (start+end)/2;
Number[] left= merge_sort(array, start, mid);
Number[] right = merge_sort(array, mid+1, end);
result= merge(left,right);
} else if (start == end) {
result[0] = array[start];
return result;
}
return result;
}
private static Number[] merge(Number[] left, Number[] right) {
Number[] result = new Number[left.length+right.length];
int i=0;
int j=0;
int k=0;
while(i< left.length&&j< right.length){
if(left[i].doubleValue()< right[j].doubleValue()){
result[k++] = left[i++];
}else{
result[k++] = right[j++];
}
}
while(i< left.length){
result[k++] = left[i++];
}
while (j< right.length) {
result[k++]= right[j++];
}
return result;
}
/**
* 交换数组中指定的两元素的位置
* @param data
* @param x
* @param y
*/
private static void swap(Number[] data, int x, int y) {
Number temp = data[x];
data[x] = data[y];
data[y] = temp;
}
}
- 大小: 6.6 KB
- 大小: 6.6 KB
分享到：
一起交流啊
学习下
好，赞一个
相关推荐
排序算法java版，速度排行：冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
10种排序算法代码+综合比较代码（直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入排序、2路插入排序），其中不仅有各种排序算法的代码，还包含10种代码在关键字...
七种排序算法（包括直接插入排序，折半插入排序，希尔排序，冒泡排序，快速排序，简单选择排序，归并排序） 还有两道题 1./*设计并实现一个有效的对n个整数重排的算法，使得所有负数位于非负数之前，给出算法的性能...
老师留的算法作业包含了 冒泡，选择，快速，归并，插入，折半插入，希尔，堆排序，包括了每个排序的比较次数和交换次数
含有折半插入、交换冒泡、堆排序、直接插入、归并排序、快速排序、基数排序、简单选择、希尔排序等的算法实现
排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素（或记录）的任意序列，重新排列...算法主要包括：插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。
主要介绍了C++如何实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序,需要的朋友可以参考下
随机产生n个1~99的正整数序列，分别采用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序对其进行递增排序
各种常用的排序算法，c++泛型实现，对于学习排序算法以及c++泛型编程都是很好的材料
八大排序java实现版本，直接插入排序、折半插入排序、冒泡排序、简单选择排序、希尔插入排序、快速排序 、堆排序、2-路归并排序 、基数排序，并有时间比较，博文...
插入排序（直接插入排序、折半插入排序、希尔排序）； * 2.交换排序（冒泡泡排序、快速排序）； * 3.选择排序（直接选择排序、堆排序）； * 4.归并排序； * 5.基数排序。 * 关于排序方法的选择： * (1)...
对本章的各种排序方法（直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序和归并排序）的时间性能进行比较。 2、 基本要求 （1）设计并实现上述各种排序算法； （2）对正序和逆序的初始...
堆排序；归并排序；基数排序。 （2）待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次...
- 算法的种类：插入排序(直接插入排序，希尔排序，折半插入排序)，选择排序(直接选择排序，堆排序(升序/最大堆))，交换排序(冒泡排序，快速排序)，归并排序，分配排序(基数排序) - 算法的时间复杂度 - 算法的空间...
直接插入排序，折半插入排序，希尔排序，快速排序，冒泡排序，直接选择排序，堆排序，归并排序大合集
包含的九种内部排序有：直接插入排序、折半排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、链式基数排序（有简单介绍各个排序方法的时间复杂度）。 每一种排序算法，基本以 “小标题-算法...
此文件为数据结构中的九种排序算法，包含一些排序方法的过程，其九种排序包括：直接插入排序，折半插入排序，希尔排序，冒泡排序，快速排序，选择排序，堆排序，归并排序，基数排序！
各种内部排序比较，冒泡 折半 直接插入 折半插入 希尔排序 简单选择排序 堆排序 归并排序，包括比较次数和移动次数
插入排序（直接插入排序、折半插入排序、希尔排序）； * 2.交换排序（冒泡泡排序、快速排序）； * 3.选择排序（直接选择排序、堆排序）； * 4.归并排序； * 5.基数排序。 * * 关于排序方法的选择： * (1)若n...
插入排序（直接插入排序、折半插入排序、希尔排序）； * 2.交换排序（冒泡泡排序、快速排序）； * 3.选择排序（直接选择排序、堆排序）； * 4.归并排序； * 5.基数排序。 * * 关于排序方法的选择： * (1)若n...