rob*_*bin 0 java sorting algorithm
我在链接(http://bigocheatsheet.com/)中看到,插入排序的复杂性与冒泡排序相同,并且堆排序也比这两者更好.但是当我创建一个示例程序并比较插入排序时间令人难以置信时.
类用于测试排序算法.
public class TestSorts {
public static void main(String[] args) {
System.out.println("starting");
Calendar startInstance = null;
Calendar endInstance = null;
//Getting the array to sort
startInstance= Calendar.getInstance();
//int[] arrayToSort = ArrayClass.getArray(1000);
int[] arrayToSort = ArrayClass.getWorstArray(10000000);
endInstance= Calendar.getInstance();
long timeTakenToGetArray = endInstance.getTimeInMillis()- startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("TimeTakenToGetArray : "+timeTakenToGetArray);
//Bubble Sort
startInstance= Calendar.getInstance();
int[] bubbleSorted = BubbleSort.sort(arrayToSort);
endInstance= Calendar.getInstance();
long timeTakenBubble = endInstance.getTimeInMillis() - startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("Bubble : "+timeTakenBubble);
//InsertionSort
startInstance= Calendar.getInstance();
int[] insertionSorted = InsertionSort.sort(arrayToSort);
endInstance= Calendar.getInstance();
long timeTakenInsertion = endInstance.getTimeInMillis() - startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("Insertion : "+timeTakenInsertion);
//HeapSort
startInstance= Calendar.getInstance();
int[] heapSorted = HeapSort.sort(arrayToSort);
endInstance= Calendar.getInstance();
long timeTakenHeap = endInstance.getTimeInMillis() - startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("Heap : "+timeTakenHeap);
startInstance= Calendar.getInstance();
arraysAreEqual(bubbleSorted, insertionSorted, heapSorted);
endInstance= Calendar.getInstance();
long timeTakenToCompare = endInstance.getTimeInMillis() - startInstance.getTimeInMillis();
System.out.println("StartTime : "+startInstance.getTimeInMillis());
System.out.println("EndTime : "+endInstance.getTimeInMillis());
System.out.println("TimeTakenToCompare : "+timeTakenToCompare);
}
//Method to compare whether the sorted arrays are equal
static void arraysAreEqual(int[] bubbleSorted,int[] insertionSorted,int[] heapSorted)
{
for(int i =0;i<bubbleSorted.length;i++)
{
if((bubbleSorted[i]!=insertionSorted[i])||(heapSorted[i]!=insertionSorted[i])||(heapSorted[i]!=bubbleSorted[i]))
{
System.out.println("Bubble : "+bubbleSorted[i]);
System.out.println("Insertion : "+insertionSorted[i]);
System.out.println("Heap : "+heapSorted[i]);
}
}
}
}
冒泡排序类
public class BubbleSort {
static int[] sort(int[] arrayToSort)
{
int length = arrayToSort.length;
for(int i = 0;i<length;i++)
{
for(int j = i+1;j<length;j++)
{
if(arrayToSort[i]>arrayToSort[j])
{
arrayToSort[i]+=arrayToSort[j];
arrayToSort[j] = arrayToSort[i] - arrayToSort[j];
arrayToSort[i] = arrayToSort[i] - arrayToSort[j];
}
}
}
return arrayToSort;
}
}
用于插入排序的类
public class InsertionSort {
static int[] sort(int[] arrayToSort)
{
for (int i = 0; i < arrayToSort.length; i++) {
int value = arrayToSort[i];
int j = i - 1;
while (j >= 0 && arrayToSort[j] > value) {
arrayToSort[j + 1] = arrayToSort[j];
j = j - 1;
}
arrayToSort[j + 1] = value;
}
return arrayToSort;
}
}
堆排序类
public class HeapSort {
static int a[];
static int[] sort(int[] arrayToSort)
{
a = arrayToSort;
heapsort();
return a;
}
static void heapsort()
{
int size = a.length;
maxHeapify(size);
for(int i =a.length-1;i>=1;i--)
{
swap(0,i);
size--;
maxHeapify(size);
}
}
static void maxHeapify(int size)
{
for(int i =size/2-1;i>=0;i--)
{
heapify(i,size);
}
}
static void heapify(int i,int size)
{
int left = 2*i+1;
int right = 2*i+2;
int max = i;
if(left<size&&a[left]>a[i])
{
max = left;
}
if(right<size&&a[right]>a[max])
{
max = right;
}
if(max!=i)
{
swap(i,max);
heapify(max,size);
}
}
static void swap(int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
用于创建数组的类
import java.util.Random;
public class ArrayClass {
public static int[] getArray(int size)
{
int array[] = new int[size];
for(int i =0;i<size;i++)
{
int s = randomInt(10,size);
array[i] = s;
}
return array;
}
private static int randomInt(int min,int max)
{
Random rn = new Random();
int randomNumber = rn.nextInt((max - min) + 1) + min;
return randomNumber;
}
public static int[] getBestArray(int size)
{
int array[] = new int[size];
for(int i =0;i<size;i++)
{
array[i]=i+1;
}
return array;
}
public static int[] getWorstArray(int size)
{
int array[] = new int[size];
for(int i =size-1;i>0;i--)
{
array[i]=i;
}
return array;
}
}
我尝试了所有场景,如最佳案例,最坏情况和平均情况.但是在所有情况下,与bubble和堆排序相比,Insertion排序要快得多.在最坏的情况下,理论上堆堆排序应该是最好的.
当我使用100000作为最坏情况的输入时,请找到以下测试结果.
starting
StartTime : 1413470225347
EndTime : 1413470225362
TimeTakenToGetArray : 15
StartTime : 1413470225362
EndTime : 1413470226894
Bubble : 1532
StartTime : 1413470226894
EndTime : 1413470226896
Insertion : 2
StartTime : 1413470226896
EndTime : 1413470233474
Heap : 6578
StartTime : 1413470233474
EndTime : 1413470233488
TimeTakenToCompare : 14
你能不能让我知道为什么插入排序比堆排序提供更快的输出？
有几个错误:
你BubbleSort对数组进行排序(就地!),然后将同一个数组传递给下一个方法(InsertionSort).
getWorstArray正在返回已排序的数组.沿另一个方向运行循环不会改变元素的顺序.无论如何,你正在使用一个角落案例(排序,反向排序,无所谓),你的结果将有偏见.
好的BubbleSort提前终止(如果在扫描期间没有进行交换,则进行排序).
此时,我会质疑其余的代码.错误通常是集群(糟糕的一天,没有经验的程序员,......).检查更多错误.做单元测试.