希尔排序跟插入排序，哪个更快些

希尔排序和插入排序，哪个更快些
我的希尔排序代码

package sort;import static print.Print.printhh;import static print.Print.printsz;public class ShellSort {public static void main(String[] args) {int[] data = {9,8,7,6,5,4,3,2,1,0};ShellSort shellSort = new ShellSort();long begin = System.currentTimeMillis();for (int i = 0 ; i < 100000000 ; i++){shellSort.sort(data);}long end = System.currentTimeMillis();printhh ("希尔排序所用时间:"+(end-begin)/1000);printsz (data);}public void sort(int[] data){for (int i = data.length/2 ; i > 0 ; i/=2)for (int j = 0 ; j < i ; j++)insertSort (data,j,i);}public void insertSort(int[] data , int start , int inc){for (int i = start + inc ; i < data.length ; i += inc)for (int j = i ; (j >= inc) && (data[j] < data[j-inc]) ; j -= inc)swap(data,j,j-inc);}public void swap(int[] data , int i , int j){int temp = data[i];data[i] = data[j];data[j] = temp;}}

我的插入排序代码

package sort;import static print.Print.*;public class InsertSort {public static void main(String[] args){int[] data = {9,8,7,6,5,4,3,2,1,0};InsertSort insertSort = new InsertSort();long begin = System.currentTimeMillis();for (int i = 0 ; i < 100000000 ; i++){insertSort.sort(data);}long end = System.currentTimeMillis();printhh ("插入排序所用时间:"+(end-begin)/1000);printsz (data);}public void sort(int[] data){for (int i = 1 ; i < data.length ; i++)for (int j = i ; (j>0) && (data[j]<data[j-1]) ; j--)swap(data,j,j-1);}public void swap(int[] data , int i , int j){int temp = data[i];data[i] = data[j];data[j] = temp;}}

运行结果如下：
希尔排序所用时间:26
0123456789
===============
插入排序所用时间:5
0123456789

这结果真让我失望，因为希尔排序就是插入排序的改良版，怎么效率比插入排序还要低呢？是我的程序写错了吗？请指教

int[] data = new int [10000001];for (int i = 10000000 ; i >=0 ; i--)data[i] = i ;
然后把排序循环次数去掉
依然发现插入排序比希尔排序快
插入排序所用时间:0
希尔排序所用时间:3
data[i] = temp;
}
InsertSort insertSort = new InsertSort();
long begin = System.currentTimeMillis();
insertSort.sort(data);
long end = System.currentTimeMillis();
System.out.println("插入排序所用时间:" + (end - begin) / 1000);
}

public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
}

public void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}







/**
*希尔排序
**/
package com.util;

public class ShellSort {

public static void main(String[] args) {
int[] data = new int[100000];
for (int i = 0; i < 100000; i++) {
int temp = (int) (Math.random() * 100000);
//System.out.println("temp==" + temp);
data[i] = temp;
}
ShellSort shellSort = new ShellSort();
long begin = System.currentTimeMillis();
shellSort.sort(data);
long end = System.currentTimeMillis();
System.out.println("希尔排序所用时间:" + (end - begin) / 1000);

for(int i=0;i<data.length;i++){
System.out.println(data[i]);
}
}

public void sort(int[] data) {
for (int i = data.length / 2; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
insertSort(data, j, i);
}
}
}

public void insertSort(int[] data, int start, int inc) {
for (int i = start + inc; i < data.length; i += inc) {
for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
swap(data, j, j - inc);
}
}
}

public void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
data[i] = temp;
}
InsertSort insertSort = new InsertSort();
long begin = System.currentTimeMillis();
insertSort.sort(data);
long end = System.currentTimeMillis();
System.out.println("插入排序所用时间:" + (end - begin) / 1000);
}

public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
}

public void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}







/**
*希尔排序
**/
package com.util;

public class ShellSort {

public static void main(String[] args) {
int[] data = new int[100000];
for (int i = 0; i < 100000; i++) {
int temp = (int) (Math.random() * 100000);
//System.out.println("temp==" + temp);
data[i] = temp;
}
ShellSort shellSort = new ShellSort();
long begin = System.currentTimeMillis();
shellSort.sort(data);
long end = System.currentTimeMillis();
System.out.println("希尔排序所用时间:" + (end - begin) / 1000);

for(int i=0;i<data.length;i++){
System.out.println(data[i]);
}
}

public void sort(int[] data) {
for (int i = data.length / 2; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
insertSort(data, j, i);
}
}
}

public void insertSort(int[] data, int start, int inc) {
for (int i = start + inc; i < data.length; i += inc) {
for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
swap(data, j, j - inc);
}
}
}

public void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}

谢谢，的确要考虑数字的随机性
public void shellSort(Integer[] data, int group) {long start=System.currentTimeMillis();for (int inc = data.length / group; inc > 0; inc /= 2) {for (int i = inc; i < data.length; i++) {int temp = data[i];int j = i;for (; j >= inc && temp < data[j - inc]; j -= inc) {data[j] = data[j - inc];}data[j] = temp;}}long end=System.currentTimeMillis();System.out.println("shell:"+(end-start));}

Integer arr[]=new Integer[100000];for(int i=0;i<100000;i++){arr[i]=(int)(Math.random()*100000+1);}sSort.shellSort(arr,2);

怎么我的测了下shell明显快了很多，400毫秒左右，插入只支持到10000，否则慢得不行了。 16 楼 raojl 2011-06-01   典型得杀鸡有牛刀！

查看更多 下一篇