我无法理解比较的工作原理以及冒泡排序(或任何与此相关的任何排序)中进行的比较。在我的冒泡排序示例代码中:
public class BS
{
public static void main (String[] args)
{
int[] Array = {5,1,4,2,8};
System.out.println("Array Before Bubble Sort:");
for (int element : Array)
System.out.print(element + " ");
bubbleSort(Array);
System.out.println("Array After Bubble Sort:");
for (int element : Array)
System.out.print(element + " ");
System.out.print("\n");
}
public static void bubbleSort(int[] array)
{
int lastPos;
int index;
int temp;
int comp = 0;
int swap = 0;
for(lastPos = array.length - 1; lastPos >= 0; lastPos--)
{
for(index = 0; index <= lastPos - 1; index++)
{
comp++;
if(array[index] > array[index + 1])
{
swap++;
temp = array[index];
array[index] = array[index + 1];
array[index + 1] = temp;
}
}
}
System.out.println("\nComparisons: " + comp);
System.out.println("Swaps: " +swap;
}
}
输出是这样的:
Array Before Bubble Sort:
5 1 4 2 8
Comparisons: 10
Swaps: 4
Array After Bubble Sort:
1 2 4 5 8
据我所知,交换次数是正确的,但比较次数不应该是 12 吗?无论我在数组中放入什么数字,比较的次数始终是 10。对于不同的数组,冒泡排序比较不是不同吗?还是取决于数组的大小?我找不到对此的任何见解,我真的很困惑。我希望得到一些帮助,如果需要,我将编辑更多信息。
最佳答案
如果不检查数组是否已排序,它将始终根据数组的大小执行恒定数量的检查。
在 for 循环中,如果您检查是否在没有任何交换的情况下完成了整个传递,那么您可以提前退出,这意味着对包含 5 个元素的已排序数组进行排序只需要 4 次比较。
在测试算法时,您应该始终向它们抛出边缘情况,例如算法的结果是什么
{}
{1}
{0,0,0,0}
{1,1,3,1,1}
{1,2,3,4,5,6}
{10,9,8,7,6,5,4,3,2,1,}
{1,5,1,5,1,5,1,5,1,5,1}
以及一些真正随机的序列。
关于java - 冒泡排序比较计数始终相同,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46773166/