为什么我的基于Java的冒泡排序优于我的选择排序和插入排序 [英] Why is my Java based Bubble Sort Outperforming my Selection Sort and my Insertion Sort
本文介绍了为什么我的基于Java的冒泡排序优于我的选择排序和插入排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
好的，所以我有一个冒泡排序，选择排序和插入排序的实现.我正在使用Java.Random对象创建三个相同的十万个数字数组.我将这些依次传递给每种排序方法.我正在使用System.nanotime计时结果.
Ok, so I have an implementation of a bubble sort, selection sort and insertion sort. I'm using Java.Random object to create three identical arrays of one hundred thousand numbers. I am passing these to each sort method in turn. I am timing the results using System.nanotime.
有关一些背景信息.我为选择和插入排序所遵循的排序算法来自Frank Carano的"Java 3rd Ed中的数据结构和抽象".冒泡排序是我的头等大事.
For some background information. The sort algorithms I followed for Selection and Insertion sort come from Frank Carano's "Data Structures and Abstraction's in Java 3rd Ed" The bubble sort, was off the top of my head.
下面，我提供一个自包含的类来执行所有这些操作. Carano的算法哪里出了问题，我看不到?
Below I provide a self contained class that performs all this. Where have Carano's algorithms gone wrong I do not see it?
在下面，您将看到我正在计算基本操作的周期并确定完成的时间.在运行时，循环数可以忽略不计.对于我来说，当看完时间时，Bubble为第一，Selection为第二，Insertion为第三.这与传统观点相去甚远.为什么.我做了一些相当愚蠢的事情吗?
Below you will see I am counting the cycles of the base operations and timing the completion. At run time the number of cycles is negligibly different. For me when looking at completion time, Bubble is 1st, Selection is 2nd and Insertion is 3rd. This flies in the face of conventional wisdom. Why. Have I done something rather daft?
顺便说一句，您应该能够编译并运行提供的代码，而无需进行任何更改.
BTW you should be able to compile and run the provided code without any changes.
import java.util.Random;
/**
*
* Performs sorts on generic data, here using Integers.
*/
public class GenSorts {
static int selectionCount = 0, bubbleCount = 0, insertionCount = 0;;
//=========================================================================
/**
* Do an insertion sort.
* @param data The array to sort
* @param first The index of the first element
* @param lasr The index of the last element
*/
//=========================================================================
public static <T extends Comparable<? super T>> void insertionSort(T[]array, int first, int last){
for(int untouch = first + 1; untouch < last; untouch++){
T nextToInsert = array[untouch];
insertInOrder(nextToInsert, array, first, untouch-1);
}//end for
}//=========================================================================
//=========================================================================
/**
* Performs the shuffle and insert part of the insertion sort.
* @param anEntry The value to insert
* @param array The target array
* @param begin The begin of the unsorted part.
* @param end The end of the unsorted part.
*/
//=========================================================================
public static <T extends Comparable<? super T>> void insertInOrder(T anEntry, T[]array, int begin, int end){
int index = end;
//Do a shunt while an entry is less than the value at the index
while( ( index >= begin ) && (anEntry.compareTo(array[index]) < 0) ){
array[index+1] = array[index];
index --;
insertionCount++;
}
array[index+1] = anEntry;//Insert
}//======================================================================
//======================================================================
/**
* BUBBLE SORT///////////////////////////////////////////////////////////
* Perform a bubble sort on the data.
* @param data The array to be sorted.
*/
//======================================================================
public static <T extends Comparable <? super T> >void bubbleSort (T[] data)
{
Boolean swapped = true;
int stop = data.length -1;
while (swapped) {
swapped = false;
for (int x = 0; x < stop ; x++ ) {
bubbleCount++;
//if x smaller than x +1 swap
if ( data[x].compareTo( data[x+1] ) > 0 ) {
swap(x, x+1, data );
swapped = true;
}//end if
stop --;
}//end for
}//end while
}//end method============================================================
//========================================================================
/**
* SELECTION SORT/////////////////////////////////////////////////////////
* A selection sort algorithm to sort data.
* @param data
* @return
*/
//========================================================================
public static <T extends Comparable<? super T> > void selectionSort(T[] data, int n){
for (int index = 0; index < n - 1; index++)
{
selectionCount++;
int min = getSmallestIndex( index, n,data);
swap( index, min, data);
//DISPLAYME
// displaySelectionArray(index, min, data);
}
}//========================================================================
//==========================================================================
/**
* Get the index of the smallest item in the array from start to end/
* @param start The place in the array to start looking.
* @param end The place in the array to end looking.
* @param array The array to inspect.
* @returnThe index of the smallest.
*/
//==========================================================================
private static <T extends Comparable<? super T>> int getSmallestIndex( int start, int end, T[] array)
{
T min = array[start];//value of smallest
int minIndex = start;//index of smallest
for (int i = start + 1; i < end; i++)
{
// System.out.print(array[i].toString() + ", ");
if (array[i].compareTo(min) < 0)
{
minIndex = i;
min = array[i];
}//end if
}//end for
// System.out.println("");
return minIndex;
}//========================================================================
//=========================================================================
/**
* Swap emelement numbers j and iMin in array data.
* @param j
* @param iMin
* @param data
*/
//=========================================================================
public static<T extends Comparable <? super T> > void swap(int j, int iMin, T[] data){
T temp = data[j];
data[j] = data[iMin];
data[iMin] = temp;
}//end swap================================================================
public static Integer[] largeRandom1, largeRandom2, largeRandom3;
//========================================================================
/**
* Generate large integers for sorting.
* @param n The value of n.
*/
//========================================================================
public static void genLargeRandom(int n){
Random r = new Random();
largeRandom1 = new Integer[n];
largeRandom2 = new Integer[n];
largeRandom3 = new Integer[n];
for(int i = 0; i < n; i++){
largeRandom1[i] = r.nextInt(100);
largeRandom2[i] = largeRandom1[i];
largeRandom3[i] = largeRandom1[i];
}//end for
}//end genLarge//==========================================================
//=========================================================================
/**
* Sort a large numvber.
* @param args
*/
//=========================================================================
public static void main(String[] args){
genLargeRandom(100000);//one hundred thousand
Integer[] data = largeRandom1;///{40, 3, 2, 7, 4};
Integer[] data2 = largeRandom2;
Integer[] data3 = largeRandom3;
System.out.println("BUBBLE SORT!!");
Long t1s = System.nanoTime();
bubbleSort(data);///////////////Bubble Sort
Long t1e = System.nanoTime();
System.out.println("SELECTION SORT!!");
Long t2s = System.nanoTime();
selectionSort(data2, data2.length);///////////////Selection Sort
Long t2e = System.nanoTime();
System.out.println("INSERTION SORT!!");
Long t3s = System.nanoTime();
insertionSort(data3,0, data3.length);////////////Insertion Sort
Long t3e = System.nanoTime();
System.out.println("Bubble Time: " + (t1e - t1s));
System.out.println("Selection Time: " + (t2e - t2s));
System.out.println("insertion Time: " + (t3e - t3s));
System.out.println("Bubble count: " + bubbleCount );
System.out.println("Selection ccount :" + selectionCount );
System.out.println("Insertion ccount :" + selectionCount );
}//========================================================================
}//############################################################################
推荐答案
您搞砸了气泡排序.尝试以简单的输入方式打印结果，您会清楚地看到这一点；例如，尝试对(3, 2, 1)进行排序会得到(2, 3, 1).您放错了stop--:
You've screwed up your bubble sort. Try to print the results for a simple input, and you'll see this clearly; for example, trying to sort (3, 2, 1) gives (2, 3, 1). You've misplaced the stop--:
public static <T extends Comparable <? super T> >void bubbleSort (T[] data)
{
Boolean swapped = true;
int stop = data.length -1;
while (swapped) {
swapped = false;
for (int x = 0; x < stop ; x++ ) {
bubbleCount++;
//if x smaller than x +1 swap
if ( data[x].compareTo( data[x+1] ) > 0 ) {
swap(x, x+1, data );
swapped = true;
}//end if
stop --; // needs to go outside the for
}//end for
}//end while
}//end method============================================================
这篇关于为什么我的基于Java的冒泡排序优于我的选择排序和插入排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
